内部構造と特徴

LinkedList は内部的にダブルリンクリスト（双方向リスト）によって実装されており、List インターフェースと Deque インターフェースの両方を実装しています。このため、LinkedList はリストとして扱うことができるだけでなく、キュー（Queue）やスタック（Stack）としても利用可能です。

ただし、スタックやキューとして使用する場合には ArrayDeque の使用が推奨されています。ArrayDeque の方がパフォーマンス的に優れているためです。

主要フィールド

// 先頭ノード
transient Node<E> head;

// 末尾ノード
transient Node<E> tail;

// 要素数
transient int length;

// 構造変更回数
protected transient int changeCount;

コンストラクタ

// 引数なしコンストラクタ
public LinkedList() {
}

// 集合を元に初期化するコンストラクタ
public LinkedList(Collection<? extends E> collection) {
    this();
    addAll(collection);
}

要素挿入処理

LinkedList では List や Deque インターフェースで定義された複数の挿入メソッドを実装しています。

/** 末尾に要素を追加 */
public boolean add(E element) {
    appendTail(element);
    return true;
}

/** 指定位置に要素を挿入 */
public void add(int index, E element) {
    validateIndex(index);

    if (index == length)
        appendTail(element);
    else
        insertBefore(element, findNode(index));
}

/** リスト末尾に新規ノードを追加 */
private void appendTail(E element) {
    final Node<E> oldTail = tail;
    final Node<E> newNode = new Node<>(oldTail, element, null);
    tail = newNode;

    if (oldTail == null)
        head = newNode;
    else
        oldTail.next = newNode;

    length++;
    changeCount++;
}

/** 指定ノードの前にノードを挿入 */
private void insertBefore(E element, Node<E> current) {
    final Node<E> prevNode = current.prev;
    final Node<E> newNode = new Node<>(prevNode, element, current);
    current.prev = newNode;

    if (prevNode == null)
        head = newNode;
    else
        prevNode.next = newNode;

    length++;
    changeCount++;
}

挿入処理の中核となるのは appendTail と insertBefore メソッドです。insertBefore の処理手順は以下の通りです：

1. 新しいノードを生成し、前後の参照を適切に設定
2. 挿入位置のノードの前参照（prev）を新しいノードへ更新
3. 必要に応じて前ノードの次参照（next）を新しいノードへ更新