(二)LinkedList集合解析及手寫集合

2019 年 10 月 3 日
筆記

一、LinkedList集合特點

問題	結論
LinkedList是否允許空	允許
LinkedList是否允許重複數據	允許
LinkedList是否有序	有序
LinkedList是否執行緒安全	非執行緒安全

　　 LinkedList集合底層是由雙向鏈表組成，而不是雙向循環鏈表。

有一個頭結點和一個尾結點，我們可以從頭開始正向遍歷，或者是從尾開始逆向遍歷，並且可以針對頭部和尾部進行相應的操作。

二、LinkedList集合底層實現

1.什麼是鏈表

鏈表原是一種線性的存儲結構，意思是將要存儲的數據存在一個存儲單元裡面，這個存儲單元裡面除了存放有待存儲的數據以外，還存儲有其下一個存儲單元的地址（下一個存儲單元的地址是必要的，有些存儲結構還存放有其前一個存儲單元的地址），每次查找數據的時候，通過某個存儲單元中的下一個存儲單元的地址尋找其後面的那個存儲單元。

2. 什麼是雙向鏈表

雙向鏈表也是鏈表的一種，它每個數據結點中都有兩個結點，分別指向其直接前驅和直接後繼。所以我們從雙向鏈表的任意一個結點開始都可以很方便的訪問其前驅元素和後繼元素。

3.雙向鏈表的定義

4.雙向鏈表的存儲結構

雙向鏈表也是採用的鏈式存儲結構，它與單鏈表的區別就是每個數據結點中多了一個指向前驅元素的指針域，它的存儲結構如下圖

當雙向鏈表只有一個結點的時候它的存儲結構如下：

頭節點和尾結點指向同一個元素。

三.LinkedList源碼分析

1.構造方法，無參構造，有參構造。

1 public LinkedList() {  2 }  3 public LinkedList(Collection<? extends E> c) {  4         // 調用無參構造函數  5         this();  6         // 添加集合中所有的元素  7         addAll(c);  8     }

2.Node結點組成

 1 private static class Node<E> {   2         E item; // 數據域   3         Node<E> next; // 後繼   4         Node<E> prev; // 前驅   5   6         // 構造函數，賦值前驅後繼   7         Node(Node<E> prev, E element, Node<E> next) {   8             this.item = element;   9             this.next = next;  10             this.prev = prev;  11         }  12     }

3.添加元素 add方法

 1 public boolean add(E e) {   2         linkLast(e);// // 添加元素到末尾   3         return true;   4     }   5 void linkLast(E e) {   6         // 保存尾結點，l為final類型，不可更改   7         final Node<E> l = last;   8         // 新生成結點的前驅為l,後繼為null   9         final Node<E> newNode = new Node<>(l, e, null);  10         // 重新賦值尾結點  11         last = newNode;  12         if (l == null) // 尾結點為空  13             first = newNode; // 賦值頭結點  14         else // 尾結點不為空  15             l.next = newNode; // 尾結點的後繼為新生成的結點  16         // 大小加1      17         size++;  18         // 結構性修改加1  19         modCount++;  20     }

3.查詢元素E get(int index)獲取指定節點數據

 1 public E get(int index) {   2     checkElementIndex(index);   3     return node(index).item;   4 }   5  Node<E> node(int index) {   6         // 判斷插入的位置在鏈表前半段或者是後半段   7         if (index < (size >> 1)) { // 插入位置在前半段   8             Node<E> x = first;   9             for (int i = 0; i < index; i++) // 從頭結點開始正向遍歷  10                 x = x.next;  11             return x; // 返回該結點  12         } else { // 插入位置在後半段  13             Node<E> x = last;  14             for (int i = size - 1; i > index; i--) // 從尾結點開始反向遍歷  15                 x = x.prev;  16             return x; // 返回該結點  17         }  18     }

4.remove移除結點時

 1 E unlink(Node<E> x) {   2         // 保存結點的元素   3         final E element = x.item;   4         // 保存x的後繼   5         final Node<E> next = x.next;   6         // 保存x的前驅   7         final Node<E> prev = x.prev;   8   9         if (prev == null) { // 前驅為空，表示刪除的結點為頭結點  10             first = next; // 重新賦值頭結點  11         } else { // 刪除的結點不為頭結點  12             prev.next = next; // 賦值前驅結點的後繼  13             x.prev = null; // 結點的前驅為空，切斷結點的前驅指針  14         }  15  16         if (next == null) { // 後繼為空，表示刪除的結點為尾結點  17             last = prev; // 重新賦值尾結點  18         } else { // 刪除的結點不為尾結點  19             next.prev = prev; // 賦值後繼結點的前驅  20             x.next = null; // 結點的後繼為空，切斷結點的後繼指針  21         }  22  23         x.item = null; // 結點元素賦值為空  24         // 減少元素實際個數  25         size--;  26         // 結構性修改加1  27         modCount++;  28         // 返回結點的舊元素  29         return element;  30     }

四.手寫LinkedList程式碼：

手寫源碼主要是為了便於對LinkedList集合的更好理解，主要對add(),remove,add(index,element) ,get(i)這些方法進行簡單的寫法，寫法比較通俗更便於理解。具體可以參考下面的程式碼。

1.自定義LinkedList集合。

  1 package com.zzw.cn.springmvc.linkList;    2    3 /**    4  * @author Simple    5  * @date 16:58 2019/9/5    6  * @description 手寫LinkList集合    7  * 思路:    8  * 1.集合add    9  * 2.remove   10  * 3.add(index,element)   11  */   12   13 public class AnLinkeList<E> {   14     private Node first;//第一個節點值   15     private Node last;//最後一個節點值   16     int size;//集合長度   17   18     /**   19      * 添加   20      *   21      * @param e   22      */   23     public void add(E e) {   24         Node node = new Node();   25         //增加時判斷集合是否為null 1.為null時候位置指向不同   26         node.object = e;   27         if (null == first) {   28   29             //第一個元素添加是第一個節點和最後一個節點指向位置都為第一個   30             first = node;   31         } else {   32             //存放上一個節點內容   33             node.prev = last;   34             //將上一個節點值指向當前節點   35             last.next = node;   36         }   37         //對最後一個節點賦值   38         last = node;   39         size++;   40     }   41   42     public E get(int index) {   43         Node node = null;   44         if (null != first) {   45             node = first;   46             //循環遍歷指向最後一個節點   47             for (int i = 0; i < index; i++) {   48                 node = node.next;   49             }   50             return (E) node.object;   51         }   52         return null;   53     }   54   55     public Node getNode(int index) {   56         Node node = null;   57         if (null != first) {   58             node = first;   59             //循環遍歷指向最後一個節點   60             for (int i = 0; i < index; i++) {   61                 node = node.next;   62             }   63             return node;   64         }   65         return null;   66     }   67   68     //刪除   69     public void remove(int index) {   70         //1找到當前元素  刪除時，將當前元素B的pre指向上一個A節點，將上一個元素A的節點指向當前元素B的next節點。   71         checkElementIndex(index);   72         Node node = getNode(index);   73         Node prevNode = node.prev;   74         Node nextNode = node.next;   75         if (prevNode.next != null) {   76             prevNode.next = nextNode;   77         }   78         if (nextNode != null) {   79             nextNode.prev = prevNode;   80         }   81         size--;   82   83     }   84   85     private boolean isElementIndex(int index) {   86         return index >= 0 && index <= size;   87     }   88   89     private void checkElementIndex(int index) {   90         if (!isElementIndex(index))   91             throw new IndexOutOfBoundsException("越界啦!");   92     }   93   94     private void add(int index, E e) {   95         checkElementIndex(index);   96         if (index == size)   97             add(e);   98         else   99             addEle(index, e);  100  101     }  102  103     private void addEle(int index, E e) {  104         /**  105          *  106          *   新增E  上一個節點是A   下一個節點是B  107          *   A->next=E  108          *   E->pre=A  109          *   E->next=B  110          *   B->pre=E  111          */  112         Node newNode = new Node();  113         newNode.object = e;  114         Node oldNode = getNode(index);  115         Node oldPrev = oldNode.prev;  116         //當前節點上一個對應新節點  117         oldNode.prev = newNode;  118         //如果當前節點為第一個時候  119         if (oldPrev == null) {  120             first = newNode;  121         } else {  122             //新節點的下一個對應當前節點  123             oldPrev.next = newNode;  124         }  125         //新節點的上一個對應老節點之前的  126         newNode.prev = oldPrev;  127         //老節點的下一個對應新節點  128         newNode.next = oldNode;  129         size++;  130  131     }  132  133 }

2.節點的定義

 1 package com.zzw.cn.springmvc.linkList;   2   3 /**   4  * @author Simple   5  * @date 17:01 2019/9/5   6  * @description 定義節點   7  */   8 public class Node {   9     Node prev;//上一個節點  10     Node next;//下一個節點  11     Object object;//節點值  12 }

3.測試類的編寫。

 1 package com.zzw.cn.springmvc.linkList;   2   3 /**   4  * @author Simple   5  * @date 19:45 2019/9/5   6  * @description   7  */   8 public class TestLinkeList {   9     public static void main(String[] args) {  10         AnLinkeList<String> list = new AnLinkeList<>();  11         list.add("1");  12         list.add("2");  13         list.add("3");  14         System.out.println("add方法後結果");  15         for (int i = 0; i < list.size; i++) {  16             System.out.print(list.get(i)+" ");  17         }  18         System.out.println();  19         list.remove(2);  20         System.out.println("remove方法後結果");  21         for (int i = 0; i < list.size; i++) {  22             System.out.print(list.get(i)+" ");  23         }  24         System.out.println("根據索引值添加的");  25         list.add(1,"3");  26         for (int i = 0; i < list.size; i++) {  27             System.out.print(list.get(i)+" ");  28         }  29     }  30 }

4.運行結果

五、LinkedList和ArrayList的對比

1、順序插入速度ArrayList會比較快，因為ArrayList是基於數組實現的，數組是事先new好的，只要往指定位置塞一個數據就好了；

LinkedList則不同，每次順序插入的時候LinkedList將new一個對象出來，如果對象比較大，那麼new的時間勢必會長一點，再加上一些引用賦值的操作，所以順序插入LinkedList必然慢於ArrayList

2、基於上一點，因為LinkedList裡面不僅維護了待插入的元素，還維護了Entry的前置Entry和後繼Entry，如果一個LinkedList中的Entry非常多，那麼LinkedList將比ArrayList更耗費一些記憶體

3、有些說法認為LinkedList做插入和刪除更快，這種說法其實是不準確的：

（1）LinkedList做插入、刪除的時候，慢在定址，快在只需要改變前後Entry的引用地址

（2）ArrayList做插入、刪除的時候，慢在數組元素的批量copy，快在定址