LinkedList
The LinkedList also implements the basic List interface like ArrayList does, but it performs certain operations (insertion and removal in the middle of the List) more efficiently than does ArrayList. Conversely, it is less efficient for random-access operations.
LinkedList also adds methods that allow it to be used as a stack, a Queue or a double-ended queue (deque).
Some of these methods are aliases or slight variations of each other, to produce names that are more familiar within the context of a particular usage (Queue, in particular). For example, getFirst( ) and element( ) are identical—they return the head (first element) of the list without removing it, and throw NoSuchElementException if the List is empty. peek( ) is a slight variation of those two that returns null if the list is empty.
removeFirst( ) and remove( ) are also identical—they remove and return the head of the list, and throw NoSuchElementException for an empty list, and poll( ) is a slight variation that returns null if this list is empty.
addFirst( ) inserts an element at the beginning of the list.
offer( ) is the same as add( ) and addLast( ). They all add an element to the tail (end) of a list.
removeLast( ) removes and returns the last element of the list.
Here’s an example that shows the basic similarity and differences between these features. It doesn’t repeat the behavior that was shown in ListFeatures.java:
//: holding/LinkedListFeatures.java
import typeinfo.pets.*;
import java.util.*;
import static net.mindview.util.Print.*;
public class LinkedListFeatures {
public static void main(String[] args) {
LinkedList<Pet> pets =
new LinkedList<Pet>(Pets.arrayList(5));
print(pets);
// Identical:
print("pets.getFirst(): " + pets.getFirst());
print("pets.element(): " + pets.element());
// Only differs in empty-list behavior:
print("pets.peek(): " + pets.peek());
// Identical; remove and return the first element:
print("pets.remove(): " + pets.remove());
print("pets.removeFirst(): " + pets.removeFirst());
// Only differs in empty-list behavior:
print("pets.poll(): " + pets.poll());
print(pets);
pets.addFirst(new Rat());
print("After addFirst(): " + pets);
pets.offer(Pets.randomPet());
print("After offer(): " + pets);
pets.add(Pets.randomPet());
print("After add(): " + pets);
pets.addLast(new Hamster());
print("After addLast(): " + pets);
print("pets.removeLast(): " + pets.removeLast());
}
} /* Output:
[Rat, Manx, Cymric, Mutt, Pug]
pets.getFirst(): Rat
pets.element(): Rat
pets.peek(): Rat
pets.remove(): Rat
pets.removeFirst(): Manx
pets.poll(): Cymric
[Mutt, Pug]
After addFirst(): [Rat, Mutt, Pug]
After offer(): [Rat, Mutt, Pug, Cymric]
After add(): [Rat, Mutt, Pug, Cymric, Pug]
After addLast(): [Rat, Mutt, Pug, Cymric, Pug, Hamster]
pets.removeLast(): Hamster
*///:~
The result of Pets.arrayList( ) is handed to the LinkedList constructor in order to populate it. If you look at the Queue interface, you’ll see the element( ), offer( ), peek( ), poll( ) and remove( ) methods that were added to LinkedList in order that it could be a Queue implementation. Full examples of Queues will be given later in this chapter.
[Thinking in Java 289]
