JDK源碼閱讀-------自學筆記(二十三)(java.util.LinkedList 初探 自定義講解)

1、LinkedList簡介

  • (1) 底層用雙向鏈表實現的存儲
  • (2) 查詢效率低，頻繁增刪效率高，執行緒不安全是其主要特點
  • (3) 常用單詞Node/Entry表示一個節點,或稱為條項,詞條(形容節點的樣子)
  • (4) 鏈表由三部分組成:前一個節點,本節點保存的數據,後一個節點

2、LinkedList和Collection的關係

3、雙向鏈表Java實現

  • (1) 定義一個對象Node,在對象中定義組成節點的三部分:上一個節點、數據位置、下一個節點
  • (2) 定義一個鏈表對象,在鏈表對象中操作節點對象.

  • (3) 以add方法為例子:

      • 每天執行add()方法的時候,新建一個節點Node,將要添加的元素,放入到Node對象中
      • 第一次添加對象的時候,鏈表中是空的,所以,鏈表的第一個節點和最後一個節點都是傳入的Node
      • 第二次,開始,添加的對象都存在next當中,以此類推,如圖:

    • 形成了類似遞歸的添加方式.

  • 4、實戰程式碼

    • 實體類Node，建立
       1 package com.synway.test.collections.version3.basesimple;
 2 
 3 /**
 4  * @author liuyangos8888
 5  * @description <p>存儲元素的實體類對象 </p>
 6  */
 7 public class Node {
 8 
 9 
10     /**
11      * 上一個節點
12      */
13     Node previous;
14 
15     /**
16      * 存儲數據
17      */
18     Object elements;
19 
20 
21     /**
22      * 下一個節點
23      */
24     Node next;
25 
26 
27     public Node() {
28 
29     }
30 
31     public Node(Object elements) {
32         this.elements = elements;
33     }
34 
35     public Node(Node previous, Object elements, Node next) {
36         this.previous = previous;
37         this.elements = elements;
38         this.next = next;
39     }
40 
41     public Node getPrevious() {
42         return previous;
43     }
44 
45     public void setPrevious(Node previous) {
46         this.previous = previous;
47     }
48 
49     public Object getElements() {
50         return elements;
51     }
52 
53     public void setElements(Object elements) {
54         this.elements = elements;
55     }
56 
57     public Node getNext() {
58         return next;
59     }
60 
61     public void setNext(Node next) {
62         this.next = next;
63     }
64 }
      View Code
    • 鏈表類建立
       1 package com.synway.test.collections.version3.basesimple;
 2 
 3 import com.synway.test.collections.version002.methodadd.base.son.AbstractMyCollection;
 4 
 5 import java.util.Iterator;
 6 
 7 /**
 8  * @author liuyangos8888
 9  * @description <p>自定義一個鏈表<p/>
10  */
11 public class MyLinkedList {
12 
13     /**
14      * 第一個節點
15      */
16     private Node firstNode;
17 
18 
19     /**
20      * 最後一個節點
21      */
22     private Node lastNode;
23 
24 
25     /**
26      * 鏈表大小
27      */
28     private int size;
29 
30 
31     /**
32      * 添加元素
33      *
34      * @param o 傳入的元素
35      */
36     public void add(Object o) {
37         Node node = new Node(o);
38 
39 
40         if (firstNode == null) {
41             firstNode = node;
42         } else {
43             node.previous = lastNode;
44             node.next = null;
45             lastNode.next = node;
46         }
47         lastNode = node;
48     }
49 
50 
51     /**
52      * 添加元素(使用對象set值的方式,更適合java程式設計師理解)
53      *
54      * @param o 傳入的元素
55      */
56     public void addObject(Object o) {
57         Node node = new Node();
58         node.setElements(o);
59 
60         if (firstNode == null) {
61             firstNode = node;
62         } else {
63             node.setPrevious(lastNode);
64             node.setNext(null);
65             lastNode.setNext(node);
66         }
67 
68         lastNode = node;
69     }
70 
71 
72     @Override
73     public String toString() {
74         StringBuilder stringBuilder = new StringBuilder();
75         stringBuilder.append("[");
76 
77         Node temp = firstNode;
78 
79         while (temp != null) {
80             stringBuilder.append(temp.elements).append(",");
81             temp = temp.next;
82         }
83 
84         stringBuilder.setCharAt(stringBuilder.length() - 1, ']');
85 
86         return stringBuilder.toString();
87     }
88     
89 }
      View Code
    • 添加方法說明
       一般add方法寫法
       1     /**
 2      * 添加元素
 3      *
 4      * @param o 傳入的元素
 5      */
 6     public void add(Object o) {
 7         Node node = new Node(o);
 8 
 9 
10         if (firstNode == null) {
11             firstNode = node;
12         } else {
13             node.previous = lastNode;
14             node.next = null;
15             lastNode.next = node;
16         }
17         lastNode = node;
18     }
      View Code
      適合java開發理解查看的寫法
       1 /**
 2      * 添加元素(使用對象set值的方式,更適合java程式設計師理解)
 3      *
 4      * @param o 傳入的元素
 5      */
 6     public void addObject(Object o) {
 7         Node node = new Node();
 8         node.setElements(o);
 9 
10         if (firstNode == null) {
11             firstNode = node;
12         } else {
13             node.setPrevious(lastNode);
14             node.setNext(null);
15             lastNode.setNext(node);
16         }
17 
18         lastNode = node;
19     }
      View Code
    • 測試
      一般add方法寫法測試
       1 package com.synway.test.version003;
 2 
 3 import com.synway.test.collections.version3.basesimple.MyLinkedList;
 4 
 5 public class TestLinkedList {
 6 
 7     public static void main(String[] args) {
 8 
 9         MyLinkedList myLinkedList = new MyLinkedList();
10         myLinkedList.add("a");
11         myLinkedList.add("b");
12         myLinkedList.add("c");
13         System.out.println(myLinkedList.toString());
14 
15 }
      View Code
      適合java開發理解查看的寫法測試
       1 package com.synway.test.version003;
 2 
 3 import com.synway.test.collections.version3.basesimple.MyLinkedList;
 4 
 5 public class TestLinkedList {
 6 
 7     public static void main(String[] args) {
 8 
 9          MyLinkedList myLinkedList2 = new MyLinkedList();
10          myLinkedList2.addObject("a");
11          myLinkedList2.addObject("b");
12          myLinkedList2.addObject("c");
13          myLinkedList2.addObject("e");
14          myLinkedList2.addObject("f");
15          System.out.println(myLinkedList2.toString());
16 
17     }
18 }
      View Code

       



Tags:

VirMach 便宜 VPS