Java Collections Framework - Building Java Programs: A Back to Basics Approach - page 680

01234

array
list:
linked
list:

a b c d e

front back

a b c d e

One major advantage of using a linked list is that elements can generally be added at
the front of the list quickly, because rather than shifting all the elements in an array, the
list just creates a new node object and links it with the others in the list. We don't have to
do this ourselves; we simply call methods on the list, which takes care of it for us inter-
nally. Figure 11.2 shows what happens inside a linked list when an element is added at
the front.
To use a linked list in Java, create an object of type LinkedList instead of type
ArrayList . A LinkedList object has the same methods you've used when working
with ArrayList :

LinkedList<String> words = new LinkedList<String>();
words.add("hello");
words.add("goodbye");
words.add("this");
words.add("that");

We could write a version of our removeEvenLength method that accepts a
LinkedList<String> as its parameter rather than an ArrayList<String> .
However, this change alone won't have much impact on performance. Since the
removeEvenLength method examines each element of the list in sequential order,
we can make the code more efficient by employing another type of object called an
iterator.

1. Make a new node to hold the new element.

x

2. Connect the new node to the other nodes in the list.

x

front back

a b c d e

3. Change the front of the list to point to the new node.

front back

x a b c d e

Figure 11.2

Adding an element to the front of a linked list