salesforce零基礎學習（七十八）線性錶鏈形結構簡單實現

前兩篇內容為棧和隊列的順序結構的實現，棧和隊列都是特殊的線性表，線性表除了有順序結構以外，還有線性結構。

一.線性表的鏈形結構--鏈表

使用順序存儲結構好處為實現方式使用數組方式，順序是固定的。所以查詢某個位置的元素特別容易，時間複雜度為O(1),但是當增加或者刪除時，會需要將操作元素後面的元素整體向左或者向右平移。時間複雜度為O(n)。所以當線性表查詢操作多於增刪操作，優先使用順序存儲結構的線性表；當線性表增刪操作多於查詢操作，則優先使用鏈式存儲結構的線性表。

線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以是連續的，也可以是不連續的。這就意味著，這些數據元素可以存在內存未被佔用的任意位置。因為鏈表可以不連續的存儲，所以每個元素需要記錄一下他的後繼的地址，從而實現每個不連續的元素之間實現關聯。我們把元素內容信息和節點信息封裝在一起，叫做結點。即每個結點擁有當前元素的信息以及此元素的後繼結點的信息。

結點的代碼描述可以為下方模型：這樣可以通過某個結點獲取其元素內容以及前一個和後一個結點。

1 private class Node {
2 Object item; // 當前節點所包含的值
3 Node next; //下一個節點
4 Node prev; //上一個節點
5 Node(Node prev, Object element, Node next) {
6 this.item = element;
7 this.next = next;
8 this.prev = prev;
9 }
10 }

二.鏈表功能的實現

鏈表作為線性表應該包含一些基礎的功能，包括添加，修改，刪除等。下方代碼實現了以下的功能：

Integer size:返回鏈表的長度；

addFirst(Object obj):在鏈表第一個位置添加元素；

add(Object obj)：在鏈表尾部添加元素；

add(Object obj,Integer index):在指定位置添加元素，index從0開始；

Object removeFirst:移除列表中的第一個元素，並且返回它的值；

Object removeLast:移除列表中的最後一個元素，並且返回它的值；

Object remove(Integer index):移除指定位置的元素，index從0開始，並且返回它的值；

Boolean removeAll:移除所有的元素，成功返回true；

set(Integer index,Object obj):設置指定位置的value值；

Object toArray:將鏈錶轉換成數組，並返回數組；

toString：重寫toString方法，返回的數據結構為(obj1,obj2,...objn)

上述方法中，如果出現數組越界或者其他情況下，返回自定義的異常。代碼如下：

1 public without sharing class LinkedList {
2
3 private Integer size = 0;
4
5 private Node first;
6
7 private Node last;
8
9 public Integer size {
10 return size;
11 }
12
13 //在第一個位置添加元素
14 public void addFirst(Object obj) {
15 linkNode(obj,0);
16 }
17
18 //在最後一個位置添加元素
19 public void add(Object obj) {
20 linkNode(obj,size);
21 }
22
23 //在指定位置前添加元素
24 public void add(Object obj,Integer index) {
25 linkNode(obj,index);
26 }
27
28 public Object removeFirst {
29 return unLinkNode(0);
30 }
31
32 public Object removeLast {
33 return unLinkNode(size - 1);
34 }
35
36 public Object remove(Integer index) {
37 return unLinkNode(index);
38 }
39
40 public Boolean removeAll {
41 return (Boolean)unLinkNode(null);
42 }
43
44 public void set(Integer index,Object obj) {
45 checkPositionIndex(index,"edit");
46 Node operateNode = node(index,"edit");
47 operateNode.item = obj;
48 }
49
50 public Object toArray {
51 Object results = new Object[size];
52 Integer i = 0;
53 for(Node n = first;n != null;n = n.next) {
54 results[i++] = n.item;
55 }
56 return results;
57 }
58
59 public Object get(Integer index) {
60 checkPositionIndex(index,"get");
61 Node result = node(index,"get");
62 return result.item;
63 }
64
65 override public String toString {
66 Object results = toArray;
67 return String.valueOf(results);
68 }
69
70 private Object unLinkNode(Integer index) {
71 checkPositionIndex(index,"delete");
72 Node leftNode;
73 Node rightNode;
74 Node operateNode;
75 Object result;
76 if(index != null) {
77 if(index == 0) {//remove first
78 operateNode = first;
79 result = operateNode.item;
80 rightNode = operateNode.next;
81 first = rightNode;
82 //如果只有一個結點，則將last置空
83 if(rightNode == null) {
84 last = null;
85 } else {
86 rightNode.prev = null;
87 }
88 size--;
89 } else if(index == size - 1) {//remove last
90 operateNode = last;
91 result = operateNode.item;
92 leftNode = operateNode.prev;
93 last = leftNode;
94 if(leftNode == null) {
95 first = null;
96 } else {
97 leftNode.next = null;
98 }
99 size--;
100 } else {//remove index node
101 operateNode = node(index,"delete");
102 result = operateNode.item;
103 leftNode = operateNode.prev;
104 rightNode = operateNode.next;
105 if(leftNode != null) {
106 leftNode.next = rightNode;
107 }
108 if(rightNode != null) {
109 rightNode.prev = leftNode;
110 } else {
111
112 }
113
114 size--;
115 }
116 } else {//remove all
117 first = null;
118 last = null;
119 size = 0;
120 result = true;
121 }
122 return result;
123 }
124
125 private void linkNode(Object e,Integer index) {
126 checkPositionIndex(index,"add");
127 Node newNode;
128 Node leftNode;
129 Node rightNode;
130 if(index == 0) {//add first
131 rightNode = first;
132 newNode = new Node(null,e,rightNode);
133 first = newNode;
134 if(rightNode == null) {
135 last = newNode;
136 } else {
137 rightNode.prev = newNode;
138 }
139 } else if(index == size) {//add last
140 leftNode = last;
141 newNode = new Node(leftNode,e,null);
142 last = newNode;
143 if(leftNode == null) {
144 first = newNode;
145 } else {
146 leftNode.next = newNode;
147 }
148 } else {//add node to specify index
149 //get the index node
150 rightNode = node(index,"add");
151 leftNode = rightNode.prev;
152 newNode = new Node(leftNode,e,rightNode);
153 rightNode.prev = newNode;
154 if(leftNode == null) {
155 first = newNode;
156 } else {
157 leftNode.next = newNode;
158 }
159 }
160 size++;
161 }
162
163 //獲取指定位置的結點元素，此部分可以進行優化。比如二分法或者其他處理從而減小循環的數量
164 private Node node(Integer index,String operateType) {
165 checkPositionIndex(index,operateType);
166 Node x = first;
167 for(Integer i = 1;i < size;i++) {
168 x = x.next;
169 if(index == i) {
170 break;
171 }
172 }
173 return x;
174 }
175
176 //判斷當前的index是否符合規範，比較其和size的關係以及是否大於0等校驗
177 private void checkPositionIndex(Integer index,String operateType) {
178
179 if(index < 0) {
180 throw new LinkedListException("index必須大於等於0");
181 }
182
183 if("delete".equalsIgnorecase(operateType)) {
184 if(size <= 0) {
185 throw new LinkedListException("鏈表長度必須大於0才可以刪除");
186 }
187 }
188
189 if(!"add".equalsIgnorecase(operateType)) {
190 if(index >= size) {
191 throw new LinkedListException("index 越界！");
192 }
193 }
194
195 }
196
197 private class Node {
198 Object item; // 當前節點所包含的值
199 Node next; //下一個節點
200 Node prev; //上一個節點
201
202 Node(Node prev, Object element, Node next) {
203 this.item = element;
204 this.next = next;
205 this.prev = prev;
206 }
207 }
208
209 public class LinkedListException extends Exception {
210
211 }
212 }

三.測試結果

使用鏈表進行添加刪除操作，並返回鏈表的值操作：

LinkedList ll = new LinkedList;
ll.add("aaa");
System.debug(LoggingLevel.INFO, "*** 1: " + ll);
ll.addFirst("bbb");
System.debug(LoggingLevel.INFO, "*** 2: " + ll);
ll.add("ccc",1);
System.debug(LoggingLevel.INFO, "*** 3: " + ll);
ll.add("ddd");
System.debug(LoggingLevel.INFO, "*** 4: " + ll);
System.debug(LoggingLevel.INFO, "*** ll.get(3): " + ll.get(3));
ll.removeFirst;
System.debug(LoggingLevel.INFO, "*** 5: " + ll);
ll.remove(2);
System.debug(LoggingLevel.INFO, "*** 6: " + ll);
ll.set(1, "set new obj");
System.debug(LoggingLevel.INFO, "*** 7: " + ll);

System.debug(LoggingLevel.INFO, "*** ll.get(0): " + ll.get(0));

Object objs = ll.toArray;
for(Object obj : objs) {
System.debug(LoggingLevel.INFO, "*** obj: " + obj);
}

結果顯示：

總結：此篇簡單的實現了鏈表的數據結構以及最基本的方法，裡面沒有對空指針進行太多的處理，應該有很多隱藏的bug，感興趣的可以去完善，比如完善一下構造函數傳鏈表或者數組情況，getFirst,getLast等等的方法。篇中有錯誤的地方歡迎指出，有問題歡迎交流。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！