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.

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

Open table as spreadsheet

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.

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]

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.