5.10 LinkedList

1. What Is It?

A sequential list implemented underneath with a doubly linked list.

It is ordered and allows duplicates.

2. How to Use It

public class LinkedListTest
{
    public static void main(String[] args)
    {
        LinkedList<String> list = new LinkedList<>();
        list.add("1");
        list.add("2");
        list.addFirst("3");
        list.addLast("4");
        System.out.println(list);
        list.remove(0);
        list.remove("2");
        list.remove();
        list.removeFirst();
        list.removeLast();
    }
}

3. Implementation Analysis

3.1. UML

It can be seen that LinkedList is a List, a double-ended queue, serializable, and cloneable.

3.2. Constructor

It consists of a head node, tail node, and length.

public class LinkedList<E>
    extends AbstractSequentialList<E>//Provides a skeletal implementation of List.
    implements List<E>/*List interface*/, Deque<E>/*double-ended queue*/, Cloneable, java.io.Serializable
{
    // Fields
    transient int size = 0;//Length
    transient Node<E> first;//Head node
    transient Node<E> last;//Tail node

    // Constructor
    public LinkedList() {
    }
}

3.2.1. Queue Node

private static class Node<E> {
    E item;//Data
    Node<E> next;//Next pointer
    Node<E> prev;//Previous pointer

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

The structure is shown below:

3.3. add Method

• O(1)

public boolean add(E e) {
    // Call linkLast.
    linkLast(e);
    return true;
}

3.3.1. Insert at the Tail of the List

• linkLast

void linkLast(E e) {
    // Save the tail node.
    final Node<E> l = last;
    // Construct a new node whose prev points to the old tail.
    final Node<E> newNode = new Node<>(l, e, null);
    // Update last to the new node.
    last = newNode;
    // If the old tail was null, this is the first node.
    if (l == null)
        first = newNode;
    else
        // Otherwise update the old tail's next pointer.
        l.next = newNode;
    size++;
    modCount++;
}

3.3.2. Construct a New Node [prev Points to Tail, next Is null]

final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);

3.3.3. Update the Tail Node

if (l == null)
    first = newNode;
else
    l.next = newNode;

3.3.4. Update size

size++;

3.4. addLast Method

• O(1)

public void addLast(E e) {
    // Call linkLast.
    linkLast(e);
}

• linkLast

See the add method.

3.5. addFirst Method

• O(1)

public void addFirst(E e) {
    // Simply call linkFirst.
    linkFirst(e);
}

3.5.1. Insert a Node at the Head

• linkFirst

private void linkFirst(E e) {
    // Save the old head node.
    final Node<E> f = first;
    // Create a new node whose next points to the old head.
    final Node<E> newNode = new Node<>(null, e, f);
    // Update first to the new node.
    first = newNode;
    // If the old head was null, this is the first element,
    // so update last to the new node.
    if (f == null)
        last = newNode;
    else
        // Otherwise update the old head's prev pointer.
        f.prev = newNode;

    size++;
    modCount++;
}

3.5.2. Construct a New Node [prev Is null, next Points to Head]

final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);

3.5.3. Update the Head Node

if (f == null)
    last = newNode;
else
    f.prev = newNode;

3.5.4. Update size

size++;

3.6. remove Method [Delete by Index]

• O(N)
• Modify the next and prev pointers of the nodes before and after the target node.

public E remove(int index) {
    // Check whether the index is out of bounds.
    checkElementIndex(index);
    // Find the corresponding node by index and delete it.
    return unlink(node(index));
}

3.6.1. Traverse to Find the Node at This Position

• node

Node<E> node(int index) {
    // assert isElementIndex(index);

    // Index is in the left half of the list.
    if (index < (size >> 1)) {
        // Search rightward from the head.
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    // Index is in the right half.
    } else {
        // Search leftward from the tail.
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

3.6.2. Update the Pointers of the Nodes Before and After It

E unlink(Node<E> x) {
    // assert x != null;
    // Save prev, next, and item of the current node.
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // Update prev.
    if (prev == null) {
        // No previous node means x is the head; point first to x.next.
        first = next;
    } else {
        // Previous node's next points to current node's next.
        prev.next = next;
        // help GC
        x.prev = null;
    }

    // Update next.
    if (next == null) {
        // No next node means x is the tail; point last to x.prev.
        last = prev;
    } else {
        // Next node's prev points to current node's prev.
        next.prev = prev;
        // help GC
        x.next = null;
    }

    // help GC
    x.item = null;
    size--;//Update size.
    modCount++;
    return element;
}

3.7. remove Method [Delete by Element]

• O(N)

public boolean remove(Object o) {
    // == null
    if (o == null) {
        // Traverse to find the node.
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    // equals
    } else {
        // Traverse to find the node.
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

3.7.1. Traverse to Find the Element

for (Node<E> x = first; x != null; x = x.next)
{
    //...
}

3.7.2. Update the Pointers of the Nodes Before and After It

The pointer-update logic is the same as unlink above.

3.8. remove Method [No Arguments]

• O(1)

public E remove() {
    // Simply call removeFirst.
    return removeFirst();
}

3.8.1. Delete the Head Node

• removeFirst

public E removeFirst() {
    // Head node.
    final Node<E> f = first;
    if (f == null)
        // Throw if null.
        throw new NoSuchElementException();
    // Call unlinkFirst to remove the head.
    return unlinkFirst(f);
}

3.8.2. Make the Old Head’s next Node the New Head

• unlinkFirst

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // Save item and next.
    final E element = f.item;
    final Node<E> next = f.next;

    // help GC
    f.item = null;
    f.next = null;

    // first directly points to the old head's next.
    first = next;
    // If the head's next is null, there was only one node.
    if (next == null)
        // Update last to null.
        last = null;
    else
        // Otherwise clear the new head's prev pointer.
        next.prev = null;
    size--;
    modCount++;
    return element;
}

3.9. removeLast Method

• O(1)

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

3.9.1. Make the Old Tail’s prev Node the New Tail

• unlinkLast

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // Save the tail's item and prev.
    final E element = l.item;
    final Node<E> prev = l.prev;
    // help GC
    l.item = null;
    l.prev = null;
    // Update last to the old tail's prev.
    last = prev;
    // Only one element.
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}