JAva LinkedList下位実装とソース分析

日常にほらを吹く
LinkedListは、List集合の実装クラスとして(集合の継承体系を理解する必要がある場合は、ArrayListの下位実装方式とは異なり、ArrayListの下位が配列によって実装されている場合、このような下位がArrayListの読み取り速度を決定するのは比較的速く、結局、アクセスは連続的なメモリアドレスですが、クエリーや変更が面倒で、遍歴して対応する読み取りとシフトを行う必要があるという弊害があります.
このときLinkedListの利点が現れ,その下位層が双方向チェーンテーブルで構成されている点でその修正が保証され,指定ノードの前後指向に対してのみ修正すればよい.
本題に入る
LinkedListのクラスに入ると,このクラスの構成は簡単で,メンバー変数は前後Nodeとこのlistのsizeのみであることが分かった.想像していたのとは少し違いますが、やはり一つ一つの要素が保存されているのではないでしょうか.

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection extends E> c) {
        this();
        addAll(c);
    }
...
}

ここではノード類がどのように構成されているのかを見てみましょう

private static class Node {
        E item;
        Node next;
        Node prev;

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

当時sun社のエンジニアたちに感心せざるを得ませんでした.簡潔で、これは大通りからジェーンと呼ばれています.では、実際にノードごとに、自分のデータitemを保存する以外に、別の2つのオブジェクトを持っていることがわかります.それぞれ前駆者、後継者です.
この構成を見てsizeの大きさは最初の宣言時の0であることがわかる.まずLinkedList#addメソッド,すなわち末尾追加に注目し,いったい何をしたのか

    /**
     * Appends the specified element to the end of this list.
     *
     * 
This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

addメソッドは外部に露出するメソッドにすぎず,実際に実行するときはlinkLastメソッドに渡されることがわかる.

は、まず、このlistオブジェクト内のノードタイプメンバーlast、すなわち末尾ノードを取得し、このノードを新しい挿入要素の前駆ノードとして、新しいノード

を作成する.

そして新しいノードをリストオブジェクトの最後のノード

とする.

は元の末尾ノードを処理し、最初の状況分析はこのlistがもともと空のチェーンテーブルであれば、ok、私たちは新しいノードを最初のノードとします.チェーンテーブルの内部にすでに要素がある場合は、元の末尾ノードの後続を新しいノードに向け、チェーンテーブル修正

を完了する.

最後に現在のlistのsizeを変更し、そのlistオブジェクトが変更を実行する回数

を記録する.
最後の追加方法の操作手順は、ターゲットノードが作成された後に前駆ノードを探し、前駆ノードが存在する場合は前駆ノードの後継を変更し、ターゲットノードを指す
次に、指定された位置挿入のaddメソッドを見てみましょう.内容は以下の通りです.

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

private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

Node node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
/**
*           
*/
void linkBefore(E e, Node succ) {
        // assert succ != null;
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

 

挿入位置が合法かどうかをチェックします.結局-1を挿入したり、存在しない位置を挿入したりすることはできません.

挿入位置が末位であれば、上に私たちが末位に追加した論理です.逆に、現在のlist内の指定位置ノードの存在が

を探し始めることを示す.

ここで私たちが見ることができることを探して、for、すぐにこのlistのノード要素を遍歴して、そしてノードの後継にアクセスして次のノードを見つけて、これはチェーンテーブルで、双方向のリンクは現在のノードが自分の後継が後ろのノードであることを知っている後で、後ろのノードがその前駆が自分であることを知っていることを保証するだけで、相互接続を実現することができます.ただし、LinkedList挿入時に探す点は必ずしもチェーンテーブルの先頭からではなく、ターゲット位置とリストの中間下付きの大きさに基づいて探す方向がより高い位置に探すか、より低い位置に探すかを決定する方式を二分検索

と呼ぶ.

ターゲットノードが見つかった後、新しいノードを作成し、その前駆が元の位置ノードの前駆predであることを新しいノードに伝え、その後、元の位置ノードsuccに続く.

それはこの時、元の位置ノードsuccのほかに、新しいノードnewNodeの前駆者が元の位置前駆ノードpredを指していることに気づく.つまり、newNodeは自分の前後を知っているが、succもノードが知っている前後を知っている.最も面倒なのは、彼らが自分の前が同じノードだと言っていることだ.そしてpredは今、自分の後継がsuccであることしか知らない.newNode

を認識しない

次にしなければならないのは、元の位置ノードに、あなたの今の前は新しいノードnewNodeであることを伝えることです.このようにすると、元のノードが前駆者を通じてnewNodeを見つけることができるだけでなく、predノードにも伝える必要があります.その後、現在はnewNodeです.双方向チェーンテーブルの相互接続を実現することで、挿入操作は

を完了する.

は、最後に現在のlistのsizeを変更し、そのlistオブジェクトが変更された回数を記録する.

以上、指定した位置に追加するロジックです.まず新しいノードを操作し、すぐに元のノードの前駆属性を変更し、最後に前駆ノードの後続属性を変更します.
ここでaddAllがどうなっているか見てみましょう

public boolean addAll(Collection extends E> c) {
        return addAll(size, c);
    }
public boolean addAll(int index, Collection extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

addAllメソッドは,従来の1つずつ追加するよりも,ノードを追加する際にノードを追加した前駆者の後継者を指定することが多いことが分かる.しかし、ここでの操作回数は1回しか記録されず、追加された集合個数に基づいて決定されるとは想像できません.
ArrayListとの異同点
以上の分析を経て、ArrayListに対する以前の理解と合わせて、比較結果を得ることができます.
集合タイプ
最下位実装
親
実装インタフェース
かくさんきこう
ArrayList
はいれつ
AbstractList
List
1.5倍拡張、すなわち10->15
LinkedList
にほうこうチェーンテーブル
AbstractSequentialList
List,Deque
チェーンテーブルは、拡張を必要としないことを決定します.
しかしnull値はサポートされており、スレッドは安全に処理されていません.