JAva linkedlistアルゴリズムノート1

Java linkedlist挿入データを自己理解するアルゴリズム:まず、linkedlist挿入ソースコードを見てみましょう.

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
    private transient Entry header = new Entry(null, null, null);//         header，   


    /**
     * Constructs an empty list.//       
     */
    public LinkedList() {
        header.next = header.previous = header; //           （1）
        addBefore(e, header);（2）

    }

.......

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

private static class Entry {//      ，          
     E element;
     Entry next;//     
     Entry previous;//     

     Entry(E element, Entry next, Entry previous) {
         this.element = element;
         this.next = next;
         this.previous = previous;
     }
}


//      
    private Entry addBefore(E e, Entry entry) {
         Entry newEntry = new Entry(e, entry, entry.previous);（3）
         newEntry.previous.next = newEntry;（4）
         newEntry.next.previous = newEntry;（5）
         size++;（6）
         modCount++;
         return newEntry;
    }


/*    ~~*/

 
以上の部分がアルゴリズムである:(簡単な式置換プロセス)アルゴリズムステップ(上の番号に対応):(1)ヘッダ(Entry)ヘッダをインスタンス化するnext=ヘッダヘッダヘッダr.previous=ヘッダの最初のデータがチェーンテーブルに挿入された場合:(3)1つのEntry newEntry(以下、E 1と略す)E 1.next=header E 1.previous=header.previous E 1.previous.next=header.previous.next=header.next(4)は、以下のようになります.

newEntry.previous.next = newEntry;

機能:
E 1.previous.next=header.next=E 1に相当するのは、前節のnextが次のノードデータを指すのでheader.nextの次のノードがE 1(5)E 1.next.previous=header.previous=E 1(ここでは巧みに使用されている)実はこの用法はE 1.next.previous=E 1単から見て、直感的にE 1の次のノードデータの前のノードがE 1であるべきであることから分かるように、E 1.next==header、なぜheader.previous=E 1を?実は1つの再帰が含まれています.もう1つのデータEntry E 2が追加された場合:上記のコードから分かるように、E 2のインスタンス化プロセスは:(linkedlistは1つのデータを追加するたびにheaderを介して値を送信します)

Entry E2 = new Entry(data, header, header.previous);

アイデアコード部分の負の値.肝心なのはここで、インスタンス化の時、E 2.previous=header.previous=E 1は簡単に負の値の過程を完成した.そしてE 2.previous.next=E 1.next=E 2.next.previous=header.previous=E 2......(次に次のデータを挿入して再帰する)(6)記録チェーンテーブルビット数は小さな再帰アルゴリズムに設計されている.linkedlistレコード1.終わりました.