Java-LinkedList ソースコードの原理分析と LinkedList によるキューの構築-java类库-php.cn

Java-LinkedList ソースコードの原理分析と LinkedList によるキューの構築

高洛峰

リリース： 2016-10-11 16:27:26

オリジナル

2009 人が閲覧しました

ここでは、最も単純なリンクリスト LinkedList を紹介します。

add() メソッドを見てください:

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

ログイン後にコピー

void linkLast(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++;
        modCount++;
    }

ログイン後にコピー

add の原理は次のとおりです:

1. 最初にリンクリストの最後のノードを取得します。

2. 最後のノードの後に新しいノードを挿入します。

3.linkedList の最後の属性は最後のノードにリダイレクトされます。

4. このノードが最初のノードであり、前のノードがない場合は、linkedList の最初の属性を新しいノードにポイントし、そうでない場合は、前のノードの次の属性をそのノードにポイントします。

LinkedList を使用して先入れ先出しキューを構築します:

offer() メソッドを使用してキューに参加します: add() メソッドを使用して最後にノードを挿入します。

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

ログイン後にコピー

poll() メソッド dequeue: リンクされたリストの先頭からキューを削除します

public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

ログイン後にコピー

LinkedList を使用して後入れ先出しキューを構築します:

push() メソッド enqueue: 最初にノードを挿入します

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

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

ログイン後にコピー

pop() メソッド dequeue : リンクされたリストの先頭から開始してキューから削除します

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

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

ログイン後にコピー

最後に注意すべきことは、LinkedList はスレッド安全ではないということです。スレッドの安全性が必要な場合は、同期ロックを使用するか、を使用してください。ベクターを使用するか、java.util.concurrent パッケージを使用します。

スレッドが List を走査するときに ConcurrentModificationException を回避する必要がある場合、3 つの解決策があります。

1. リストを走査するときに同期ロックを使用します。

2. リストを使用するたびに、実際にはリストのコピーを使用します。

3. Jdk8 では foreach メソッドを使用しますが、このメソッドはラムダ式のみを受け入れます

list.forEach(item -> {
                    System.out.println("遍历元素：" + item);
                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                });

ログイン後にコピー