MyLinkList類 1 package List; 2 3 // 單向鏈表 4 public class MyLinkList { 5 private Node root; // 根結點 6 private int size; // 結點個數 7 private int index; // 腳標 ...
一.單向鏈表（遞歸）
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 }MyLinkList
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 }TestMyLinkList
列印
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 是否相等trueTestMyLinkList-console
總結：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
