Using the LinkedList Class

The ArrayList class, which I cover in the previous chapter, is a collection class that's based on an array. Arrays have their strengths and their weaknesses. The strength of an array is that it's very efficient-at least until you fill it up or try to reorganize it by inserting or deleting elements. Then it suddenly becomes very inefficient.

Over the years, computer scientists have developed various alternatives to arrays that are more efficient for certain types of access. One of the oldest of these is the linked list. A linked list is less efficient than an array for tasks such as directly accessing an element based on its index number. However, linked lists run circles around arrays when you need to insert or delete items in the middle of the list.

In this chapter, you find out how to use Java's LinkedList class, which provides a collection that's based on a linked list rather than an array. You'll find that although the LinkedList class provides many of the same features as the ArrayList class, it also has some tricks of its own.

The LinkedList Class

A linked list is a collection in which every object in the list maintains with it a pointer to the next object in the list and to the previous object in the list. No array is involved at all in a linked list. Instead, the list is managed entirely by these pointers.

Tip 

Don't worry-you don't have to do any of this pointer management yourself. It's all taken care of for you by the LinkedList class.

This arrangement has some compelling advantages over arrays:

• Because the ArrayList class uses an array to store list data, the ArrayList class frequently has to reallocate its array when you add items to the list. Not so with the LinkedList class. Linked lists don't have any size issues. You can keep adding items to a linked list until your computer runs out of memory.
• Like the ArrayList class, the LinkedList class lets you insert items into the middle of the list. However, with the ArrayList class, this is a pretty inefficient operation. It has to copy all the items past the insertion point one slot over to free up a slot for the item you're inserting. Not so with the LinkedList class. To insert an item in the middle of a linked list, all you have to do is change the pointers in the previous and the next objects.
• With an array list, removing items from the list is pretty inefficient. The ArrayList class has to copy every item after the deleted item one slot closer to the front of the array to fill in the gap left by the deleted item. Not so with the LinkedList class. To remove an item from a linked list, all that's necessary is to update the pointers in the items that were before and after the item to be removed.

  For example, if you want to remove the third item from a list that has 10,000 items in it, the ArrayList class has to copy 9,997 items. In contrast, the LinkedList class does it by updating just two of the items. By the time the ArrayList class is done, the LinkedList class has had time to mow the lawn, read a book, and go to Disneyland.

• Linked lists are especially well suited for creating two common types of lists:
  • Stacks: A stack is a list in which items can only be added to and retrieved from the front of the list.
  • Queues: A queue is a list in which items are always added to the back of the list and always retrieved from the front.

  Arrays are terribly inefficient for the sort of processing required by stacks and queues. (You see examples of how to use linked lists to create stacks and queues in Book IV, Chapter 5.)

• TECHNICAL STAUFF 

  The ArrayList class actually uses an array internally to store the data you add to the array list. The ArrayList class takes care of managing the size of this array. When you add an item to the array list and the underlying array is full, the ArrayList class automatically creates a new array with a larger capacity and copies the existing items to the new array before it adds the new item.

There's no such thing as a free lunch, however. The flexibility of a linked list comes at a cost: Linked lists require more memory than an array, and are slower than arrays when it comes to simple sequential access.

Like the ArrayList class, the LinkedList class has several constructors and a ton of methods. For your reference, Table 4-1 lists the constructors and methods of the LinkedList class.

Table 4-1: The LinkedList Class

Open table as spreadsheet

Constructor	Explanation
LinkedList()	Creates an empty linked list.
LinkedList(Collection c)	Creates a linked list and copies all the elements from the specified collection into the new linked list.

Open table as spreadsheet

Method	Explanation
add (Object element)	Adds the specified object to the end of the linked list. If you specified a type when you created the linked list, the object must be of the correct type.
add(int index, Object element)	Adds the specified object to the linked list at the specified index position. If you specified a type when you created the linked list, the object must be of the correct type.
addAll (Collection c)	Adds all the elements of the specified collection to this linked list.
addAll(int index, Collection c)	Adds all the elements of the specified collection to this linked list at the specified index position.
addFirst (Object element)	Inserts the specified object at the beginning of the list. If you specified a type when you created the linked list, the object must be of the correct type.
addLast (Object element)	Adds the specified object to the end of the list. This method performs the same function as the add method. If you specified a type when you created the linked list, the object must be of the correct type.
clear ()	Deletes all elements from the linked list.
clone ()	Returns a copy of the linked list. The elements contained in the copy are the same object instances as the elements in the original.
contains (Object elem)	Returns a boolean that indicates whether the specified object is in the linked list.
containsAll (Collection c)	Returns a boolean that indicates whether this linked list contains all the objects that are in the specified collection.
descendinglterator ()	Returns an iterator that steps backward, from the end to the beginning of the linked list.
element ()	Retrieves the first element from the list. (The element is not removed.)
get (int index)	Returns the object at the specified position in the list.
getFirst ()	Returns the first element in the list. If the list is empty, throws NoSuchElementException.
getLast ()	Returns the last element in the list If the list is empty, throws NoSuchElementException.
indexOf (Object elem)	Returns the index position of the first occurrence of the specified object in the list. If the object isn't in the list, returns −1.
isEmpty ()	Returns a boolean value that indicates whether the linked list is empty.
iterator ()	Returns an iterator for the linked list.
lastlndexOf (Object elem)	Returns the index position of the last occurrence of the specified object in the linked list. If the object isn't in the list, returns −1.
offer (Object elem)	Adds the specified object to the end of the list. This method returns a boolean value, which is always true.
of ferFirst (Object elem)	Adds the specified object to the front of the list. This method returns a boolean value, which is always true.
of ferLast (Object elem)	Adds the specified object to the end of the list. This method returns a boolean value, which is always true.
peek ()	Returns (but does not remove) the first element in the list. If the list is empty, returns null.
peekFirst ()	Returns (but does not remove) the first element in the list. If the list is empty, returns null.
peekLast ()	Returns (but does not remove) the last element in the list. If the list is empty, returns null.
poll()	Retrieves the first element and removes it from the list. Returns the element that was retrieved or, if the list is empty, returns null.
pollFirst ()	Retrieves the first element and removes it from the list. Returns the element that was retrieved or, if the list is empty, returns null.
pollLast ()	Retrieves the last element and removes it from the list. Returns the element that was retrieved or, if the list is empty, returns null.
pop()	Pops an element from the stack represented by this list.
push (Object elem))	Pushes an element onto the stack represented by this list.
remove ()	Retrieves the first element and removes it from the list. Returns the element that was retrieved. If the list is empty, throws NoSuchElementException.
remove (int index)	Removes the object at the specified index. Returns the element that was removed.
remove (Object elem)	Removes an object from the list. Note that if more than one element refers to the object, this method removes only one of them. Returns a boolean that indicates whether the object was in the list.
removeAll (Collection c)	Removes all the objects in the specified collection from this linked list.
removeFirst ()	Retrieves the first element and removes it from the list. Returns the element that was retrieved. If the list is empty, throws NoSuchElementException.
removeFirstOccurrence (Object elem)	Finds the first occurrence of elem in the list, and removes this occurrence from the list. Returns false if the list has no such occurrence.
removeLast ()	Retrieves the last element and removes it from the list. Returns the element that was retrieved. If the list is empty, throws NoSuchElementException.
removeLastOccurrence (Object elem)	Finds the last occurrence of elem in the list and removes this occurrence from the list. Returns false if the list has no such occurrence.
retainAll (Collection c)	Removes all the objects that are not in the specified collection from this linked list.
set(int index, Object elem)	Sets the specified element to the specified object. The element that was previously at that position is returned as the method's return value.
size ()	Returns the number of elements in the list.
toArray ()	Returns the elements of the linked list as an array of objects (Object []).
toArray (type [ ] array)	Returns the elements of the linked list as an array whose type is the same as the array passed via the parameter.

TECHNICAL STAUFF 

As you look over these methods, you'll find several that seem to do the same thing. These similar methods usually have subtle differences. For example, the getFirst and peek methods both return the first element from the list without removing the element. The only difference is what happens if the list is empty. In that case, getFirst throws an exception, but peek returns null.

In some cases, however, the methods are identical. For example, the remove and removeFirst methods are identical. In fact, if you're crazy enough to look at the source code for the LinkedList class, you'll find that the remove method consists of a single line: a call to the removeFirst method.

Creating a LinkedList

Like any other kind of object, creating a linked list is a two-step affair. First, you declare a LinkedList variable, and then you call one of the LinkedList constructors to create the object, as in this example:

LinkedList officers = new LinkedList();

Here a linked list is created and assigned to the variable officers.

Tip 

If you're using Java 1.5 or later, you can specify a type when you declare the linked list. For example, here's a statement that creates a linked list that holds strings:

LinkedList officers = new LinkedList();

Then you can only add String objects to this list. If you try to add any other type of object, the compiler balks. (Base runners advance.)

Adding Items to a LinkedList

The LinkedList class has many different ways to add items to the list. The most basic is the add method, which works pretty much the same way it works for the ArrayList class. Here's an example:

LinkedList officers = new LinkedList();
officers.add("Blake");
officers.add("Burns");
officers.add("Houlihan");
officers.add("Pierce");
officers.add("McIntyre");
for (String s : officers)
 System.out.println(s);

The add method adds these items to the end of the list. So the resulting output is this:

Blake
Burns
Houlihan
Pierce
McIntyre

The addLast method works the same. However, the addFirst method adds items to the front of the list. Consider these statements:

LinkedList officers = new LinkedList();
officers.addFirst("Blake");
officers.addFirst("Burns");
officers.addFirst("Houlihan");
officers.addFirst("Pierce");
officers.addFirst("McIntyre");
for (String s : officers)
 System.out.println(s);

Here the resulting output shows the officers in reverse order:

McIntyre
Pierce
Houlihan
Burns
Blake

To insert an object into a specific position into the list, specify the index in the add method, as in this example:

LinkedList officers = new LinkedList();
officers.add("Blake");
officers.add("Burns");
officers.add("Houlihan");
officers.add("Pierce");
officers.add("McIntyre");
officers.add(2, "Tuttle");
for (String s : officers)
 System.out.println(s);

The console output from these statements is this:

Blake
Burns
Tuttle
Houlihan
Pierce
McIntyre

Here are some other thoughts to consider when you ponder how to add elements to linked lists:

• If you specified a type for the list when you created it, the items you add must be of the correct type. The compiler kvetches if they aren't.

• REMEMBER 

  Like arrays and everything else in Java, linked lists are indexed starting with zero.

• If you specify an index that doesn't exist, the add method throws IndexOutOfBoundsException. This is an unchecked exception, so you don't have to handle it.

• TECHNICAL STAUFF 

  LinkedList also has weird methods named offer, offerFirst, and offerLast. The offer method adds an item to the end of the list and has a return type of boolean. However, it always returns true. The offer method is defined by the Queue interface, which LinkedList implements. Some classes that implement Queue can refuse to accept an object added to the list via offer. In that case, the offer method returns false. But because a linked list never runs out of room, the offer method always returns true to indicate that the object offered to the list was accepted.

• In case you're not a M*A*S*H fan, Tuttle was a fictitious officer that Hawkeye and B.J. made up in one episode so they could collect his paychecks and donate the money to the local orphanage. Unfortunately, the ruse got out of hand. When Tuttle won a medal and a general wanted to present it in person, they arranged for "Tuttle" to "die" in an unfortunate helicopter accident.

Retrieving Items from a LinkedList

As with the ArrayList class, you can use the get method to retrieve an item based on its index. If you pass it an invalid index number, the get method throws the unchecked IndexOutOfBoundsException.

You can also use an enhanced for loop to retrieve all the items in the linked list. The examples in the preceding section use this enhanced for loop to print the contents of the officers linked list:

for (String s : officers)
 System.out.println(s);

If you want, you can also use the iterator method to get an iterator that can access the list. (For more information about iterators, refer to Book IV, Chapter 3.)

The LinkedList class also has a variety of other methods that retrieve items from the list. Some of these methods remove the items as they are retrieved. Some throw exceptions if the list is empty; others return null.

Nine methods retrieve the first item in the list:

• getFirst: Retrieves the first item from the list. This method doesn't delete the item. If the list is empty, NoSuchElement-Exception is thrown.
• element: Identical to the getFirst method. This strangely named method exists because it's defined by the Queue interface, and the LinkedList class implements Queue.
• peek: Similar to getFirst, but doesn't throw an exception if the list is empty. Instead, it just returns null. (The Queue interface also defines this method.)
• peekFirst: Identical to peek. Only the name of the method is changed to protect the innocent.
• remove: Similar to getFirst, but also removes the item from the list. If the list is empty, it throws NoSuchElementException.
• removeFirst: Identical to remove. If the list is empty, it throws NoSuchElementException.
• poll: Similar to removeFirst but returns null if the list is empty. (Yet another method that the Queue interface defines.)
• pollFirst: Identical to poll (well, identical except for the name of the method).
• pop: Identical to removeFirst (but with a more catchy name).

Four methods also retrieve the last item in the list:

• getLast: Retrieves the last item from the list. This method does not delete the item. If the list is empty, NoSuchElement-Exception is thrown.
• peekLast: Similar to getLast, but doesn't throw an exception if the list is empty. Instead, it just returns null.
• removeLast: Similar to getLast, but also removes the item. If the list is empty, it throws NoSuchElementException.
• pollLast: Similar to removeLast but returns null if the list is empty.

Updating LinkedList Items

As with the ArrayList class, you can use the set method to replace an object in a linked list with another object. For example, in that M*A*S*H episode where Hawkeye and B.J. made up Captain Tuttle, they quickly found a replacement for him when he died in that unfortunate helicopter accident. Here's how Java implements that episode:

LinkedList officers = new LinkedList();

// add the original officers
officers.add("Blake");
officers.add("Burns");
officers.add("Tuttle");
officers.add("Houlihan");
officers.add("Pierce");
officers.add("McIntyre");
System.out.println(officers);

// replace Tuttle with Murdock
officers.set(2, "Murdock");
System.out.println("
Tuttle is replaced:");
System.out.println(officers);

The output from this code looks like this:

[Blake, Burns, Tuttle, Houlihan, Pierce, McIntyre]

Tuttle is replaced:
[Blake, Burns, Murdock, Houlihan, Pierce, McIntyre]

Tip 

As with an ArrayList, any changes you make to an object retrieved from a linked list are automatically reflected in the list. That's because the list contains references to objects, not the objects themselves. (For more information about this issue, refer to Book IV, Chapter 3.)

Removing LinkedList Items

You've already seen that several of the methods that retrieve items from a linked list also remove the items. In particular, the remove, removeFirst, and poll methods remove the first item from the list, and the removeLast method removes the last item.

You can also remove any arbitrary item by specifying either its index number or a reference to the object you want to remove on the remove method. For example, to remove item 3, use a statement like this:

officers.remove(3);

And if you have a reference to the item you want to remove, use the remove method like this:

officers.remove(tuttle);

To remove all the items from the list, use the clear method:

officers.clear(); // Goodbye, Farewell, and Amen.