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 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.

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.

The LinkedList class has several compelling advantages over the ArrayList class:

Size issues: Because the ArrayList class uses an internal array to store list data, the ArrayList class frequently has to reallocate its array when you add items to the list. Linked lists don’t have any size issues. You can keep adding items to a linked list until your computer runs out of memory.

Inserting items: With the ArrayList class, inserting an item in the middle of the list is inefficient because all items after the insertion point must be copied. With a LinkedList class, though, inserting items in the middle of the list is much more efficient.

Removing items: With an array list, removing items from the list is also inefficient because the ArrayList class must 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. With the LinkedList class, removing an item from the list is much more efficient.

Linked lists are especially well suited for creating two common types of lists:

Stack: A list in which items can only be added to and retrieved from the front of the list

Queue: A list in which items are always added to the back of the list and always retrieved from the front

The two drawbacks of the LinkedList class compared with the ArrayList class are

Linked lists require more memory than arrays.

Linked lists are slower than arrays when it comes to simple sequential access.

Constructors

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.

Methods

Method	Explanation
add(Object element)	Adds the specified object to the end of the linked list. If you specify a type when you create 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 specify a type when you create 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 specify a type when you create 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 specify a type when you create 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 element)	Returns a Boolean value that indicates whether the specified object is in the linked list.
containsAll (Collection c)	Returns a Boolean value 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 NoSuch ElementException.
indexOf(Object element)	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 element)	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 element)	Adds the specified object to the end of the list. This method returns a Boolean value, which is always true.
offerFirst(Object element)	Adds the specified object to the front of the list. This method returns a Boolean value, which is always true.
offerLast(Object element)	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()	Retrieves and removes the first element from the list.
push(Object element)	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 NoSuchElement Exception.
remove(int index)	Removes the object at the specified index and returns the element that was removed.
remove(Object element)	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 value 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 NoSuchElement Exception.
removeFirstOccurrence (Object element)	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 NoSuchElement Exception.
removeLastOccurrence (Object element)	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 element)	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.

Creating a LinkedList

To create a linked list, declare a LinkedList variable and 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.

You can also use the generics feature to specify a type when you declare the linked list:

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

In this case, you will only be able to add String objects to this list. (For more information, see Generics in Part 2.)

Adding items to a LinkedList

The LinkedList class gives you several ways to add items to the list. The most basic is the add method, which adds an item to the end of an existing list:

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

officers.add(“One”);

officers.add(“Two”);

officers.add(“Three”);

The result is a list with three strings, One, Two, and Three.

The addLast method is equivalent to the add method, but the addFirst method adds items to the front of the list. Consider these statements:

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

numbers.add(“Three”);

numbers.addFirst(“Two”);

numbers.addFirst(“One”);

The result is a list with three strings in the following order: One, Two, and Three.

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

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

officers.add(“One”);

officers.add(“Three”);

officers.add(“Three”, 1);

Again, the result is a list with three strings in the following order: One, Two, and Three.

Here are some other thoughts to consider:

If you specify a type for the list when you create it, the items you add must be of the correct type. The compiler kvetches if they aren’t.

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.

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

You 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 (also called “foreach”) 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);

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. For example, in the M*A*S*H episode in which Hawkeye and B.J. make 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> numbers = new LinkedList<String>();

numbers.add(“One”);

numbers.add(“Two”);

numbers.add(“Three”);

numbers.set(0, “I”);

numbers.set(1, “II”);

numbers.set(2, “III”);

The result is a list that has three strings: I, II, and III.

Removing LinkedList items

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 2, for example, use a statement like this:

numbers.remove(2);

If you have a reference to the item that you want to remove, use the remove method, like this:

employees.remove(smith);

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

numbers.clear();