數據結構Java實現----鏈表

一.單向鏈表（遞歸）

MyLinkList類

  1 package List;
  2 
  3 // 單向鏈表
  4 public class MyLinkList {
  5     private Node root; // 根結點
  6     private int size; // 結點個數
  7     private int index; // 腳標
  8     private Object[] reData; // 保存數據的數組
  9 
 10     // 構造方法
 11     public MyLinkList() {
 12         this.root = new Node("head");
 13         System.out.println("創建了帶頭指針的鏈表");
 14     }
 15 
 16     public MyLinkList(Object data) {
 17         if (data == null)
 18             System.out.println("參數錯誤");
 19         this.root = new Node(data);
 20         this.size++;
 21         System.out.println("創建成功" + data);
 22     }
 23 
 24     // 是否是空表
 25     public boolean isEmpty() {
 26         return this.size == 0;
 27     }
 28 
 29     // 返回長度
 30     public int size() {
 31         return this.size;
 32     }
 33     
 34     // 清空鏈表
 35     public void clear(){
 36         this.root = null;
 37         this.size = 0;
 38     }
 39 
 40     // 判斷兩個鏈表是否相等
 41     public boolean equals(Object obj){
 42         // 常規判斷
 43         if(obj == null)
 44             return false;
 45         if(obj == this)
 46             return true;
 47         
 48         // 是MyLinkList類
 49         if(obj instanceof MyLinkList){
 50             MyLinkList linkList = (MyLinkList)obj;
 51             
 52             // 根結點相同
 53             if(!this.root.data.equals(linkList.root.data)){
 54                 System.out.println("根節點不相同");
 55                 return false;
 56             }
 57             // 長度相同
 58             if(this.size != linkList.size) {
 59                 System.out.println("長度不同");
 60                 return false;
 61             }
 62             
 63             // 各個結點相同
 64             if(this.size==1){ // 只含有根結點
 65                 return true;
 66             }
 67             return this.root.next.equals(linkList.root.next);
 68         }
 69         
 70         // 不是MyLinkList類
 71         return false;
 72             
 73     }
 74 
 75     // 添加單個數據
 76     public boolean addData(Object data) {
 77         if (data == null) {
 78             System.out.println("參數錯誤");
 79             return false;
 80         }
 81 
 82         // 把data封裝成帶指針域的結點
 83         Node node = new Node(data);
 84 
 85         if (this.root.next == null)
 86             this.root.next = node;
 87         else
 88             this.root.next.addNode(node);
 89         System.out.println("添加成功" + data);
 90         this.size++;
 91         return true;
 92     }
 93 
 94     // 添加多個數據
 95     public boolean addDatas(Object[] datas) {
 96         if (datas == null) {
 97             System.out.println("參數錯誤");
 98             return false;
 99         }
100 
101         // 迴圈添加結點
102         for (int index = 0; index < datas.length; ++index) {
103             Node data = new Node(datas[index]);// 封裝結點
104             this.root.addNode(data);
105             this.size++;
106         }
107         return true;
108     }
109 
110     // 查找數據是否存在
111     public boolean contains(Object data) {
112         if (data == null || this.isEmpty())
113             return false;
114         return this.root.containsNode(data);
115     }
116 
117     // 查找指定位置下的數據
118     public Object get(int index) {
119         // 參數錯誤
120         if (this.isEmpty() || index < 0 || index > this.size)
121             return null;
122 
123         if (this.root.data.equals("head")) { // 帶頭指針
124             if (index == 1) // 返回第一個有效數據
125                 return this.root.next.data;
126             else {
127                 this.index = 0;
128                 return this.root.next.getNode(index);
129             }
130         } else { // 不帶頭指針
131             if (index == 1) // 返回第一個有效數據
132                 return this.root.data;
133             else {
134                 this.index = 1;
135                 return this.root.next.getNode(index);
136             }
137 
138         }
139     }
140 
141     // 刪除數據
142     public boolean deleteData(Object data) {
143         if (data == null || this.isEmpty()) {
144             return false;
145         }
146         // 是根結點
147         if (this.root.data.equals(data)) {
148             this.root = this.root.next;
149             this.size--;
150             return true;
151         }
152 
153         // 不是根節點
154         else
155             return this.root.deleteNode(data);
156     }
157 
158     // 列印所有數據
159     public void print() {
160         if (this.isEmpty())
161             System.out.print("空表--------");
162         else
163             this.root.printNode();
164         System.out.println("");
165     }
166 
167     // 返回數組數據
168     public Object[] toArray() {
169         if (this.isEmpty())
170             return null;
171 
172         // 數組保存
173         this.index = 0; // 數組下標
174         if (this.root.data.equals("head")) // 鏈錶帶頭指針
175             reData = new Object[++this.size];
176         else
177             reData = new Object[this.size];
178         this.root.toArray();
179         return reData;
180     }
181 
182     // 結點類（內部）
183     class Node {
184         Object data; // 數據域
185         Node next; // 指針域
186 
187         // 構造方法
188         public Node(Object data) {
189             this.data = data;
190         }
191 
192         // 添加結點
193         public void addNode(Node node) {
194             if (this.next == null)
195                 this.next = node;
196             else
197                 this.next.addNode(node);
198         }
199 
200         // 列印結點數據
201         public void printNode() {
202             System.out.print(this.data + " ");
203             if (this.next != null)
204                 this.next.printNode();
205         }
206 
207         // 刪除結點
208         public boolean deleteNode(Object data) {
209             if (this.next == null) {
210                 System.out.println("刪除失敗" + data);
211                 return false;
212             }
213             if (this.next.data.equals(data)) {
214                 System.out.println("刪除成功" + this.next.data);
215                 MyLinkList.this.size--;
216                 this.next = this.next.next;
217                 return true;
218             }
219             return this.next.deleteNode(data);
220         }
221 
222         // 返回數組
223         public void toArray() {
224             MyLinkList.this.reData[MyLinkList.this.index++] = this.data;
225             if (this.next != null)
226                 this.next.toArray();
227         }
228 
229         // 查找指定結點
230         public Object getNode(int index) {
231             if (++MyLinkList.this.index == index)
232                 return this.data;
233             return this.next.getNode(index);
234         }
235 
236         // 查找結點
237         public boolean containsNode(Object data) {
238             if (this.data == data)
239                 return true;
240             if (this.next != null)
241                 return this.next.containsNode(data);
242             return false;
243         }
244         
245         // 重寫equals()
246         public boolean equals(Node node){
247             // 數據域是否相同
248             if(!this.data.equals(node.data)) {
249                 System.out.println("數據域不同this:"+this.data+" linkList:"+node.data);
250                 return false;
251             }
252             // 還有下個結點
253             if(this.next!=null)
254                 return this.next.equals(node.next);
255             // 沒有下個結點且到目前為止所有結點數據域相同
256             return true;
257             
258         }
259     }
260 }

TestMyLinkList類

 1 package List;
 2 
 3 // 單向鏈表測試
 4 public class TestMyLinkList {
 5 
 6     public static void main(String[] args) {
 7         // 創建一個鏈表
 8         MyLinkList linkList = new MyLinkList(5);
 9 
10         // 初始化一個鏈表
11         for (int index = 1; index < 10; ++index) {
12             int num = (int) (Math.random() * 11);
13             linkList.addData(num);
14         }
15 
16         // 列印鏈表的所有數據
17         linkList.print();
18 
19         // 刪除結點
20         linkList.deleteData(5);
21         linkList.print();
22         linkList.deleteData(10);
23         linkList.print();
24 
25         System.out.println("第2個結點數據:" + linkList.get(2));
26         // 數組化
27         Object[] data = new Object[linkList.size()];
28         data = linkList.toArray();
29         for (Object index : data)
30             System.out.print(index + " ");
31         System.out.println("");
32         System.out.println("-------------------");
33         // 創建一個鏈表
34         MyLinkList linkList2 = new MyLinkList();
35 
36         // 待添加數據的數組
37         Object[] datas = { 5, "123", 26 };
38         linkList2.addDatas(datas);
39         System.out.println("包含'5'嗎" + linkList2.contains(5));
40         linkList2.print();
41         System.out.println("----------------------------");
42         // 創建一個鏈表
43         MyLinkList linkList1 = new MyLinkList();
44         linkList1.addDatas(datas);
45         linkList1.print();
46         System.out.println("是否相等"+linkList2.equals(linkList1));
47     }
48 
49 }

列印

 1 添加成功5
 2 添加成功1
 3 添加成功6
 4 添加成功6
 5 添加成功6
 6 添加成功1
 7 添加成功5
 8 添加成功2
 9 添加成功10
10 5 5 1 6 6 6 1 5 2 10 
11 5 1 6 6 6 1 5 2 10 
12 刪除成功10
13 5 1 6 6 6 1 5 2 
14 第2個結點數據:1
15 5 1 6 6 6 1 5 2 
16 -------------------
17 包含'5'嗎true
18 head 5 123 26 
19 ----------------------------
20 head 5 123 26 
21 是否相等true

總結：1.避免空指針異常(NullPointException):先判斷引用是否為null，後使用。

參考:https://www.cnblogs.com/dolphin0520/p/3811445.html

2018-7-19

二、雙向鏈表(迴圈、頭插法)

DoubleLink類

  1 package List;
  2 
  3 // 雙向鏈表（循壞、頭插法）
  4 public class DoubleLink {
  5     private Node root; // 表頭
  6     private int size; // 長度
  7 
  8     // 結點類
  9     private class Node {
 10         Object data; // 數據域
 11         Node prev; // 前趨
 12         Node next; // 後繼
 13 
 14         // 構造方法
 15         public Node(Object data, Node prev, Node next) {
 16             this.data = data;
 17             this.prev = prev;
 18             this.next = next;
 19         }
 20 
 21         public Node(Object data) {
 22             this.data = data;
 23         }
 24     }
 25 
 26     // 構造方法
 27     public DoubleLink() {
 28         this.root = new Node(null, null, null);
 29         this.root.prev = this.root.next = this.root;
 30         this.size = 0;
 31     }
 32 
 33     // 是否是空表
 34     public boolean isEmpty() {
 35         return this.size == 0;
 36     }
 37 
 38     // 返回長度
 39     public int size() {
 40         return this.size;
 41     }
 42 
 43     // 添加數據
 44     public boolean addData(Object data) {
 45         // 空引用
 46         if (data == null)
 47             return false;
 48 
 49         this.size++; // 增加長度
 50         Node node = new Node(data); // 封裝結點
 51         // 添加結點
 52 
 53         if (this.isEmpty()) {
 54             this.root.next = node;
 55             this.root.prev = node;
 56 
 57             node.next = this.root;
 58             node.prev = this.root;
 59             return true;
 60         }
 61 
 62         // 頭插法
 63         node.next = this.root.next; // 將新結點的後繼指向頭結點的後繼
 64         node.prev = this.root; // 將新結點的前驅指向頭結點
 65         this.root.next.prev = node; // 頭結點的後繼結點的前驅指向新結點
 66         this.root.next = node; // 頭結點的後繼節點指向新結點
 67         return true;
 68     }
 69 
 70     // 查找第index結點
 71     private Node getNode(int index) {
 72         Node oldNode = this.root;
 73         int foot = 0; // 腳標
 74         if (index <= this.size / 2) { // 正查找
 75             System.out.print("正查");
 76             while (true) {
 77                 if (foot++ == index)
 78                     break;
 79                 oldNode = oldNode.next;
 80             }
 81         } else {
 82             int LIndex = this.size + 1 - index;
 83             System.out.print("反查");
 84             while (true) {
 85                 if (foot++ == LIndex)
 86                     break;
 87                 oldNode = oldNode.prev;
 88             }
 89         }
 90         System.out.print(oldNode.data);
 91         return oldNode;
 92     }
 93 
 94     // 查找結點
 95     private Node getNode(Object data) {
 96         Node oldNode = this.root.next;
 97         while (true) {
 98             if (oldNode.data.equals(data))
 99                 return oldNode;
100             if (oldNode.next.data == null)
101                 return null;
102             oldNode = oldNode.next;
103         }
104 
105     }
106 
107     // 刪除結點
108     private void removeNode(Node node) {
109         node.next.prev = node.prev; // 結點的後繼結點的前驅指向結點的前驅
110         node.prev.next = node.next; // 結點的前驅結點的後繼指向結點的後繼
111         node = null;
112     }
113 
114     // 前插法
115     private boolean addNode(Node oldNode, Node newNode) {
116         oldNode.prev.next = newNode;
117         newNode.prev = oldNode.prev;
118         oldNode.prev = newNode;
119         newNode.next = oldNode;
120         return true;
121     }
122 
123     // 在index結點前插入新結點
124     public boolean addData(Object data, int index) {
125         if (data == null)
126             return false;
127         if (index <= 0 || index > this.size)
128             return false;
129 
130         Node newNode = new Node(data); // 封裝結點
131 
132         // 查找結點
133         Node oldNode = getNode(index);
134         this.size++; // 增加長度
135         // 更改指針域
136         return addNode(oldNode, newNode);
137     }
138 
139     // 得到第index個結點的數據
140     public Object get(int index) {
141         if (this.isEmpty())
142             return null;
143         if (index <= 0 || index > this.size)
144             return null;
145 
146         // 查找結點
147         return getNode(index).data;
148     }
149 
150