Java Programming Interviews Exposed

Chapter 5

Data Structures

Every application uses data structures—lists of usernames, maps of query parameters, and so on. They are unavoidable, and are a core part of all of the Java APIs and most third-party APIs, as well.

This chapter examines the four most commonly used data structures: lists, trees, maps, and sets. You learn how they are implemented in Java, and how to use them depending on how you intend to read and write your data. If you only ever write to the front element of your list, you will find your application will perform much better with one list implementation over another.

Throughout the book, and for any serious development in Java, you will use the implementations discussed here. In any interview, you will be expected to understand the Java Collections API data structures, so make sure you fully understand the classes and interfaces presented in this chapter.

Lists

Lists are sequential, ordered collections of values of a certain type. In Java, you will generally work with either LinkedLists or ArrayLists.

Lists differ from Java’s built-in primitive collection type of arrays in that they are unbounded, so you do not need to specify the size of the array before using it.

At times it is more appropriate to use an ArrayList than a LinkedList, and vice versa. The use case for which of the lists to use will vary, but make sure you think it through, because it can have serious implications on your application’s performance or its memory usage.

Whenever you are working ...