隨心所欲

自我理解java linkedlist插入數據的算法：
首先看一下，linkedlist插入源代碼：

 1 public class LinkedList
 2     extends AbstractSequentialList
 3     implements List, Deque, Cloneable, java.io.Serializable
 4 {
 5     private transient Entry header = new Entry(null, null, null);//初始化時先實例一個header，鏈表頭
 6 
 7 
 8     /**
 9      * Constructs an empty list.//構造一個空鏈表
10      */
11     public LinkedList() {
12         header.next = header.previous = header; //把鏈表頭和尾先連到自己（1）
13         addBefore(e, header);（2）
14 
15     }
16 
17 .
18 
19  public boolean add(E e) {//插入鏈表方法
20             return true;
21     }
22 .
23 
24 private static class Entry {//每個數據存放，所要用到的靜態(tài)內部類
25      E element;
26      Entry next;//后一個節(jié)點
27      Entry previous;//接一個節(jié)點
28 
29      Entry(E element, Entry next, Entry previous) {
30          this.element = element;
31          this.next = next;
32          this.previous = previous;
33      }
34 }
35 
36 
37 //插入操作方法
38     private Entry addBefore(E e, Entry entry) {
39          Entry newEntry = new Entry(e, entry, entry.previous);（3）
40          newEntry.previous.next = newEntry;（4）
41          newEntry.next.previous = newEntry;（5）
42          size++;（6）
43          modCount++;
44          return newEntry;
45     }
46 
47 
48 /*其他方法~~*/
49 
50 

以上部分就是算法所在：(一個簡單的公式替換過程)

算法步驟（對應上面的編號）：

（1）實例化一個header (Entry)

header.next = header

header.previous = header

當有第一條數據插入鏈表：

（3）實例化一個 Entry newEntry （以下簡稱E1）

E1.next = header

E1.previous = header.previous

E1.previous.next = header.previous.next = header.next

（4）由上面可得：

作用：

相當于 E1.previous.next = header.next = E1

其實就是，讓上一個節(jié)的next指向下一個節(jié)點數據

所以header.next 的下一個節(jié)點就是E1

（5）E1.next.previous = header.previous = E1（這里用得巧妙）

其實這個用法單從E1.next.previous= E1單這么看，很直觀因為E1的下一個節(jié)點數據的上一個節(jié)點就應該是E1

從上面可知，E1.next == header，為什么要把header.previous = E1呢？

其實包含著一個遞歸在里面。

如果再新增一個數據 Entry E2 ：

從上面的代碼可以看出，E2的實例化過程是：(其實linkedlist每次新增一個數據，都通過header傳值)

注意代碼部分的負值。關鍵就是這里，實例化的時候，E2.previous = header.previous = E1
簡單得完成了負值過程。

然后 E2.previous.next = E1.next = E2
E2.next.previous = header.previous = E2 .......(接著插入下一條數據，如此遞歸)

（6）記錄鏈表位數


涉及到了一個小小的遞歸算法。

linkedlist記錄一。完畢。。