ホームページ > 記事 > Java > Java LinkedList ソースコード分析 (写真)

Java LinkedList ソースコード分析 (写真)

黄舟オリジナル: 2017-03-30 10:54:061544ブラウズ

全体の紹介

LinkedList は Listインターフェースと Deque インターフェースの両方を実装しています。これは、これをシーケンシャルコンテナー、キュー (キュー) とみなすことができると同時に、スタック (スタック)。この観点から見ると、LinkedListはまさに総合チャンピオンです。スタックまたはキューを使用する必要がある場合、最初に考慮する必要があるのは LinkedList です。なぜなら、Java では Stack クラスの使用は推奨されず、LinkedList の使用が推奨されていると公式に宣言されているからです。さらに残念なのは、Java には Queue というクラス (インターフェイス名です) が存在しないことです。

LinkedList の最下位層は二重リンクリストを通じて実装されます。このセクションでは、要素の挿入および削除時の二重リンクリストのメンテナンスプロセス、つまり List インターフェースに関連する関数に焦点を当てます。は解決されており、Queue と Stack are And Deque 関連の知識については次のセクションで説明します。二重リンクリストの各ノードは、内部クラス Node によって表されます。 LinkedList は、それぞれ first と last を通じてを参照します。リンクされたリストの最初と最後の要素。ここにはいわゆるダミー変数がないことに注意してください。リンクされたリストが空の場合、first と last は両方とも <a href="http:/" target="_blank">null<code>first和last引用分别指向链表的第一个和最后一个元素。注意这里没有所谓的哑元，当链表为空的时候first和last都指向<a href="http://www.php.cn/wiki/62.html" target="_blank">null</a>。

//Node内部类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。

方法剖析

add()

add()方法有两个版本，一个是add(E e)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可；另一个是add(int index, E element)，该方法是在指定下表处插入元素，需要先通过线性查找找到具体位置，然后修改相关引用完成插入操作。

Java LinkedList ソースコード分析 (写真)

结合上图，可以看出add(E e)的逻辑非常简单。

//add(E e)
public boolean add(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;//原来链表为空，这是插入的第一个元素
    else
        l.next = newNode;
    size++;
    return true;
}

add(int index, E element)的逻辑稍显复杂，可以分成两部，1.先根据index找到要插入的位置；2.修改引用，完成插入操作。

//add(int index, E element)
public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾，包括列表为空的情况
        add(element);
    else{
        Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用，完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

上面代码中的node(int index)函数有一点小小的trick，因为链表双向的，可以从开始往后找，也可以从结尾往前找，具体朝那个方向找取决于条件index > 1)，也即是index是靠近前端还是后端。

remove()

remove()方法也有两个版本，一个是删除跟指定元素相等的第一个元素remove(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object</a> o)，另一个是删除指定下标处的元素remove(int index)。

Java LinkedList ソースコード分析 (写真)

两个删除操作都要1.先找到要删除元素的引用，2.修改相关引用，完成删除操作。在寻找被删元素引用的时候remove(Object o)调用的是元素的equals方法，而remove(int index)使用的是下标计数，两种方式都是线性时间复杂度。在步骤2中，两个revome()方法都是通过unlink(Node<e> x)</e>方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

//unlink(Node<E> x)，删除一个Node
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {//删除的是第一个元素
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {//删除的是最后一个元素
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;//let GC work
    size--;
    return element;
}

get()

get(int index)得到指定下标处元素的引用，通过调用上文中提到的node(int index)方法实现。

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

set()

set(int index, E element)方法将指定下标处的元素修改成指定值，也是先通过node(int index)找到对应下表元素的引用，然后修改Node中item。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}

🎜 LinkedList の実装では、添字関連のすべての操作が線形時間であることが決定され、最初または最後の要素の削除には定数時間のみが必要です。効率を追求するため、LinkedList は同期を実装していません (同時アクセスが必要な場合は synchr🎜ized)。複数のスレッドからの場合は、まず Collections.synchronizedList() メソッドを使用してラップします。 🎜🎜メソッド分析🎜

add()

🎜add() メソッドには 2 つのバージョンがあり、1 つは add(E e) です。このメソッドは LinkedList の最後に要素を挿入します。 last はリンクされたリストの末尾を指しており、末尾に要素を挿入するには一定の時間がかかります。必要なのは、いくつかの関連する参照を変更することだけです。もう 1 つは、add(intindex, E element) です。このメソッドは、以下の指定されたテーブルに要素を挿入する必要があります。次に、関連する参照を変更して挿入操作を完了します。 🎜🎜 Java LinkedList ソースコード分析 (写真)

🎜🎜上の画像と組み合わせると、 add(E e) を参照してください。これは非常に簡単です。 🎜rrreee🎜add(intindex, E element)ロジックは少し複雑で、2 つの部分に分けることができます。1. まずインデックスに従って挿入する場所を見つけます。2. 参照を変更します。挿入操作を完了します。 🎜rrreee🎜上記のコードの node(intindex) 関数は少し注意が必要です。リンクされたリストは双方向であり、先頭から逆方向に検索することも、末尾から前方に検索することもできるためです。具体的にどの方向ですか? 方向は条件 index > 1) 、つまりインデックスがフロントエンドに近いかバックエンドに近いかによって決まります。 🎜

remove()

🎜remove() メソッドにも 2 つのバージョンがあります。1 つは、指定された要素 remove(<a href="http://www.php.cn/wiki/60.html" target="_blank">Object🎜 o)</a>、もう 1 つは、指定された添え字の要素を削除することです

remove(intインデックス)。 🎜🎜<img src="https://img.php.cn/upload/article/000/000/194/6bebb43dc9558ecf6e7e3f2aef010a7a-2.png" alt="Java LinkedList ソース コード分析 (写真)">🎜🎜どちらの削除操作にも 1 が必要です。最初の検索削除する要素の参照。 2. 関連する参照を変更して、削除操作を完了します。削除された要素への参照を探す場合、<code>remove(Object o)

は要素の equals メソッドを呼び出しますが、remove(int index) は添え字カウントでは、どちらの方法も線形時間計算量を持ちます。ステップ 2 では、両方の revome() メソッドが unlink(Node<e> x)</e> メソッドを通じて完了します。ここでは、削除された要素が最初または最後の要素である場合の境界ケースを考慮する必要があります。 🎜rrreee