Linked List実現原理

10174 ワード
java
Linked List概要
双方向チェーンはListとDequeインターフェースを実現する。すべてのオプションのリスト操作を実行し、null値の挿入を許可します。
すべての操作の実行方式は双方向リンクと同じです。検索操作は両端からの距離に基づいて、最初または最後からリストを巡回します。
この同期は実現されていません。List list=Collection s.synchronized List(new Linked List))で包装できます。
Linked List継承
public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
Linked Listソースコード
一、データメンバー
transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     * 
     *            。   ：(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)
     * 
     *             。   ：(first == null && last == null)|| (last.next == null && last.item！= null)
     * 
     */
    transient Node last;
二、構造関数
    /**
     * 
     *       。
     * 
     */
    public LinkedList() {
    }

    /**
     *
     *                        ​​     。
     * @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);
    }
三、その他の方法
1、linkFirst
リンクeを最初の要素として使う
private void linkFirst(E e) {
        final Node f = first;
        final Node newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
2、linkLast
最後の要素としてリンクeを使用します。
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++;
    }
3、unlinkFirst
最初のノードfのリンクをキャンセルします。
private E unlinkFirst(Node f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node 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;
    }
4、unlinkLast
最終ノードlのリンクをキャンセルします。
private E unlinkLast(Node l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)//      
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
5、unlink
リンク非空ノードxをキャンセルします。
E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
        final Node next = x.next;
        final Node prev = x.prev;

        if (prev == null) {
            first = next;//x    ，       next
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
//x    ，       prev
｝else｛next.prev=prev；x.next=null；｝x.item=null；size--modCount++;return element;
6、remove
ヘッドノードを削除
    public E removeFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
ノードを削除
public E removeLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
7、add
このリストの先頭に指定された要素を追加します。
public void addFirst(E e) {
        linkFirst(e);
    }
指定した要素をこのリストの最後に追加します。
public void addLast(E e) {
        linkLast(e);
    }
public boolean add(E e) {
        linkLast(e);
        return true;
    }
8、セット
指定された要素を指定された要素と置換します。
    public E set(int index, E element) {
        checkElementIndex(index);
        Node x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }
9、clear
このリストからすべての要素を削除します。この呼び出しが戻ったら、リストが空になります。
public void clear() {
        // Clearing all of the links between nodes is "unnecessary", but:
        // - helps a generational GC if the discarded nodes inhabit
        //   more than one generation
        // - is sure to free memory even if there is a reachable Iterator
        for (Node x = first; x != null; ) {
            Node next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }
10、indexOf
このリストに指定された要素の最初に現れた索引を返します。このリストに要素が含まれていない場合は、-1を返します。
public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
11、node
指定された要素索引の（非空）ノードを返します。
    Node node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {// index x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else { index >= size/2 ,     
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
12、peek
検索しますが、このリストの先頭(最初の要素)は削除されません。
public E peek() {
        final Node f = first;
        return (f == null) ? null : f.item;
    }
public E peekFirst() {
        final Node f = first;
        return (f == null) ? null : f.item;
     }
で検索しますが、このリストの最後は削除されません。
public E peekLast() {
        final Node l = last;
        return (l == null) ? null : l.item;
    }
13、element
検索しますが、このリストの先頭(最初の要素)は削除されません。
public E element() {
        return getFirst();
    }
14、poll
このリストのヘッダを検索して削除します。
    public E poll() {
        final Node f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
public E pollFirst() {
        final Node f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
このリストの最後を検索して削除します。
public E pollLast() {
        final Node l = last;
        return (l == null) ? null : unlinkLast(l);
    }
15、offer
public boolean offer(E e) {
        return add(e);//     
    }
16、offer First
このリストの前に指定された要素を挿入します。
public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
17、removeLastOcceurrence
このリストで指定した要素の最後の出現を削除します。要素がリストに含まれていない場合は変更されません。
        if (o == null) {
            for (Node x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
18、toAray
このリストのすべての要素を含む配列を正確な順序で返します。返した配列は「安全」です。参照がないのでリストで維持されます。したがって、変調者は、リターンされた配列を自由に修正することができ、この方法は、アレイとセットベースのAPIとの間の橋渡しとして機能する。
public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
正しい順序を含む要素(最初の要素から最後の要素まで)を返します。のリストのすべての要素の配列を返します。指定された配列に適合する場合は、指定された配列が返されます。指定された配列のランタイムタイプとこのリストのサイズを使用して、新しい配列が割り当てられます。列テーブルが空空間を持つ指定された配列に適している場合は、リストより多くの要素が配列されます。を選択します。リストの直後の配列の要素は「@code null」に設定されます。この方法は、配列とセットベースのAPIとの間のブリッジとして機能し、さらに、出力アレイの実行時のタイプの正確な制御を可能にし、場合によっては、割り当てコストを節約するために使用されることができる。
public  T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }
四、内部類
private class DescendingIterator implements Iterator 
  
private class ListItr extends Itr implements ListIterator  
  
private static class Node
  
static final class LLSpliterator implements Spliterator
DescendingIterator Iteratorインターフェースを実現しました。同時に中のhas Next（）、next（）、remove（）などを書き直しました。
ListItrはItrを継承し、ListIteratorインターフェースを実現し、同時にhas Prvious()、nextIndex()、previous Index()、previous()などの方法を書き直しました。
Nodeはチェーンのノードで、メンバーを持っています。  Node next;  Node prev;
LLSplighteratorは分割可能なサブエージェントであり、並行して要素を遍歴するために設計されたローズマリーであり、jdk 1.8のセットフレームの中のデータ構造はデフォルトでspliteratorを実現しています。具体的にはよく分かりません。
SparseArayの紹介
java放射メカニズムの概要