Chapter 4

Using the LinkedList Class

IN THIS CHAPTER

check Introducing linked lists

check Comparing linked lists with array lists

check Creating linked lists

check Adding items to a linked list

check Retrieving items from a linked list

check Updating and deleting items in a linked list

The ArrayList class, which I cover in the preceding 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 alternatives 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, but 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.

Understanding the LinkedList Class

A linked list is a collection in which every object in the list maintains with it a pointer to the following object in the list and another pointer to the preceding 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. With the ArrayList class, however, this operation is pretty inefficient. It has to copy all the items past the insertion point one slot over to free a slot for the item you’re inserting. Not so with the LinkedList class. To insert an item into the middle of a linked list, all you have to do is change the pointers in the preceding and the following 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 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.

    If you want to remove the third item from a list that has 10,000 items in it, for example, the ArrayList class has to copy 9,997 items. By 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.

  • Technical stuff 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 arrays 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

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.

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.

descendingIterator()

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, it throws NoSuchElementException.

getLast()

Returns the last element in the list. If the list is empty, it 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, it returns -1.

isEmpty()

Returns a boolean value that indicates whether the linked list is empty.

iterator()

Returns an iterator for the linked list.

lastIndexOf(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, it 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.

offerFirst(Object elem)

Adds the specified object to the front of the list. This method returns a boolean value, which is always true.

offerLast(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, it returns null.

peekFirst()

Returns (but does not remove) the first element in the list. If the list is empty, it returns null.

peekLast()

Returns (but does not remove) the last element in the list. If the list is empty, it returns null.

poll()

Retrieves the first element and removes it from the list. It returns the element that was retrieved or, if the list is empty, null.

pollFirst()

Retrieves the first element and removes it from the list. It returns the element that was retrieved or, if the list is empty, null.

pollLast()

Retrieves the last element and removes it from the list. It returns the element that was retrieved or, if the list is empty, 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. It returns the element that was retrieved. If the list is empty, it throws NoSuchElementException.

remove(int index)

Removes the object at the specified index and 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. It 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. It returns the element that was retrieved. If the list is empty, it throws NoSuchElementException.

removeFirstOccurrence(Object elem)

Finds the first occurrence of elem in the list and removes this occurrence from the list. It returns false if the list has no such occurrence.

removeLast()

Retrieves the last element and removes it from the list. It returns the element that was retrieved. If the list is empty, it throws NoSuchElementException.

removeLastOccurrence(Object elem)

Finds the last occurrence of elem in the list and removes this occurrence from the list. It 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 stuff As you look over these methods, you’ll find several that seem to do the same thing. These similar methods usually have subtle differences. The getFirst and peek methods, for example, 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, such as the remove and removeFirst methods. 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

As with any other kind of object, creating a linked list is a two-step affair. First, you declare a LinkedList variable; 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 You can (and should) use the generics feature to specify a type when you declare the linked list. Here’s a statement that creates a linked list that holds strings:

LinkedList<String> officers = new LinkedList<String>();

Then you can add only 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 gives you many ways to add items to the list. The most basic is the add method, which works pretty much the same way that it does for the ArrayList class. Here’s an example:

LinkedList<String> officers = new LinkedList<String>();

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 way, but the addFirst method adds items to the front of the list. Consider these statements:

LinkedList<String> officers = new LinkedList<String>();

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<String> officers = new LinkedList<String>();

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

(In case you’re not a M*A*S*H fan, Tuttle was a fictitious officer that Hawkeye and Trapper made up in one episode so that 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.)

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 stuff 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, but 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.

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 4, 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. (This method is 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 catchier name).

Four methods also retrieve the last item in the list:

  • getLast: Retrieves the last item from the list. This method doesn't 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. In that M*A*S*H episode in which Hawkeye and Trapper 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<String> officers = new LinkedList<String>();

// 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("\nTuttle 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 4, 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. To remove item 3, for example, use a statement like this:

officers.remove(3);

If you have a reference to the item that 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.