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等等的方法。篇中有錯誤的地方歡迎指出，有問題歡迎交流。

作者：zero

部落格位址：http://www.cnblogs.com/zero-zyq/

本文歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接

個人下載下傳了一些相關學習的PDF檔案，如果需要下載下傳請通路百度雲點選此處通路密碼：jhuy

如果文章的内容對你有幫助，歡迎點贊~

為友善手機端檢視部落格，現正在将部落格遷移至微信公衆号：Salesforce零基礎學習，歡迎各位關注。

salesforce零基礎學習（七十八）線性表鍊形結構簡單實作

繼續閱讀

網絡功能虛拟化（NFV）

Java常用算法三：01背包問題

HTML5 API 浏覽器支援情況檢測

讓Firefox支援offsetX、offsetY

raid5和raid10 哪種适合你（2）

salesforce零基礎學習（七十九）簡單排序淺談篇一

salesforce零基礎學習（七十六）順序棧的實作以及應用

salesforce零基礎學習（七十七）隊列的實作以及應用

テリトリーの設定について、

Sales force：custom settings

Salesforce 的代碼調試

Salesforce CSV檔案輸出

Where You Can Use Visualforce in Lightning Experience

使用Visual Studio Code編輯以及debug apex

Window 10視窗在螢幕間快速移動設定

Salesforce:檔案上傳