14.6. CLASS LINKEDLIST

Java collection classes differ in how you can retrieve and insert objects. If you need to work with a sequential list of objects and often insert the object into the list, the data structure called linked list can fit the bill. Java has a class called LinkedList that stores elements so that each contains a reference to the next (aka node). Each element in a doubly linked list also contains a reference to the previous element. These features of the doubly-linked class LinkedList allow you to create queues (FIFO), and stacks (last-in-first-out or LIFO).

Insertion of a new object inside the list comes down to a simple update of two references: The previous element of the list has to be pointed to the newly inserted object, which will have to include a reference to the next element, if any. Compare this to the complexity of lots of memory allocations and object moving in memory to increase the size of an ArrayList or Vector, and you'll appreciate the value that linked lists bring to the table. On the other hand, collections that use arrays for the underlying data storage offer random access to the data elements, while linked lists can be processed only sequentially.