java.util.LinkedList は、List、Deque、Queue の各インタフェースを実装する双方向連結リストです。これにより、リスト操作だけでなく、キュー・スタック・デックとしても利用可能です。

継承関係

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

主要フィールド

// 要素数
transient int size = 0;
// 先頭ノード
transient Node<E> head;
// 末尾ノード
transient Node<E> tail;

要素は Node オブジェクトとして保持され、各ノードは前後のノードへの参照を持ちます。

コンストラクタ

public LinkedList() {}

public LinkedList(Collection<? extends E> collection) {
    this();
    addAll(collection);
}

Listインタフェースの実装

インデックス指定による要素追加

public void add(int index, E element) {
    checkPositionIndex(index);
    if (index == size) {
        linkLast(element);
    } else {
        linkBefore(element, nodeAt(index));
    }
}

Node<E> nodeAt(int idx) {
    if (idx < (size >> 1)) {
        Node<E> current = head;
        for (int i = 0; i < idx; i++) {
            current = current.next;
        }
        return current;
    } else {
        Node<E> current = tail;
        for (int i = size - 1; i > idx; i--) {
            current = current.prev;
        }
        return current;
    }
}

void linkBefore(E value, Node<E> successor) {
    final Node<E> predecessor = successor.prev;
    final Node<E> newNode = new Node<>(predecessor, value, successor);
    successor.prev = newNode;
    if (predecessor == null) {
        head = newNode;
    } else {
        predecessor.next = newNode;
    }
    size++;
    modCount++;
}

要素削除

public boolean remove(Object target) {
    if (target == null) {
        for (Node<E> x = head; x != null; x = x.next) {
            if (x.item == null) {
                detach(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = head; x != null; x = x.next) {
            if (target.equals(x.item)) {
                detach(x);
                return true;
            }
        }
    }
    return false;
}

E detach(Node<E> node) {
    final E data = node.item;
    final Node<E> next = node.next;
    final Node<E> prev = node.prev;

    if (prev == null) {
        head = next;
    } else {
        prev.next = next;
        node.prev = null;
    }

    if (next == null) {
        tail = prev;
    } else {
        next.prev = prev;
        node.next = null;
    }

    node.item = null;
    size--;
    modCount++;
    return data;
}

Queueインタフェースの実装

末尾への追加

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

public boolean offer(E e) {
    return add(e);
}

void linkLast(E value) {
    final Node<E> oldTail = tail;
    final Node<E> newNode = new Node<>(oldTail, value, null);
    tail = newNode;
    if (oldTail == null) {
        head = newNode;
    } else {
        oldTail.next = newNode;
    }
    size++;
    modCount++;
}

先頭からの削除

public E remove() {
    return removeFirst();
}

public E poll() {
    final Node<E> firstNode = head;
    return (firstNode == null) ? null : detachFirst(firstNode);
}

private E detachFirst(Node<E> node) {
    final E data = node.item;
    final Node<E> next = node.next;
    node.item = null;
    node.next = null;
    head = next;
    if (next == null) {
        tail = null;
    } else {
        next.prev = null;
    }
    size--;
    modCount++;
    return data;
}

先頭要素の参照

public E element() {
    final Node<E> f = head;
    if (f == null) throw new NoSuchElementException();
    return f.item;
}

public E peek() {
    final Node<E> f = head;
    return (f == null) ? null : f.item;
}

Dequeインタフェースの拡張

先頭への追加

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E value) {
    final Node<E> oldHead = head;
    final Node<E> newNode = new Node<>(null, value, oldHead);
    head = newNode;
    if (oldHead == null) {
        tail = newNode;
    } else {
        oldHead.prev = newNode;
    }
    size++;
    modCount++;
}

末尾からの削除

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

public E pollLast() {
    final Node<E> l = tail;
    return (l == null) ? null : detachLast(l);
}

private E detachLast(Node<E> node) {
    final E data = node.item;
    final Node<E> prev = node.prev;
    node.item = null;
    node.prev = null;
    tail = prev;
    if (prev == null) {
        head = null;
    } else {
        prev.next = null;
    }
    size--;
    modCount++;
    return data;
}

スタック操作

public void push(E e) {
    addFirst(e);
}

public E pop() {
    return removeFirst();
}

特定要素の削除（末尾から探索）

public boolean removeLastOccurrence(Object o) {
    if (o == null) {
        for (Node<E> x = tail; x != null; x = x.prev) {
            if (x.item == null) {
                detach(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = tail; x != null; x = x.prev) {
            if (o.equals(x.item)) {
                detach(x);
                return true;
            }
        }
    }
    return false;
}