寫在前面：
雙向鏈表是一種對稱結構，它克服了單鏈表上指針單向性的缺點，其中每一個節點即可向前引用，也可向后引用，這樣可以更方便的插入、刪除數據元素。
由于雙向鏈表需要同時維護兩個方向的指針，因此添加節點、刪除節點時指針維護成本更大；但雙向鏈表具有兩個方向的指針，因此可以向兩個方向搜索節點，因此雙向鏈表在搜索節點、刪除指定索引處節點時具有較好的性能。
Java語言實現雙向鏈表：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 | package com.ietree.basic.datastructure.dublinklist;/** * 雙向鏈表 * * @author Dylan */public class DuLinkList<T> { // 定義一個內部類Node，Node實例代表鏈表的節點 private class Node { // 保存節點的數據 private T data; // 保存上個節點的引用 private Node prev; // 指向下一個節點的引用 private Node next; // 無參構造器 public Node() { } // 初始化全部屬性的構造器 public Node(T data, Node prev, Node next) { this.data = data; this.prev = prev; this.next = next; } } // 保存該鏈表的頭節點 private Node header; // 保存該鏈表的尾節點 private Node tail; // 保存該鏈表中已包含的節點數 private int size; // 創建空鏈表 public DuLinkList() { // 空鏈表，header和tail都是null header = null; tail = null; } // 以指定數據元素來創建鏈表，該鏈表只有一個元素 public DuLinkList(T element) { header = new Node(element, null, null); // 只有一個節點，header、tail都指向該節點 tail = header; size++; } // 返回鏈表的長度 public int length() { return size; } // 獲取鏈式線性表中索引為index處的元素 public T get(int index) { return getNodeByIndex(index).data; } // 根據索引index獲取指定位置的節點 public Node getNodeByIndex(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("線性表索引越界"); } if (index <= size / 2) { // 從header節點開始 Node current = header; for (int i = 0; i <= size / 2 && current != null; i++, current = current.next) { if (i == index) { return current; } } } else { // 從tail節點開始搜索 Node current = tail; for (int i = size - 1; i > size / 2 && current != null; i++, current = current.prev) { if (i == index) { return current; } } } return null; } // 查找鏈式線性表中指定元素的索引 public int locate(T element) { // 從頭結點開始搜索 Node current = header; for (int i = 0; i < size && current != null; i++, current = current.next) { if (current.data.equals(element)) { return i; } } return -1; } // 向線性鏈表的指定位置插入一個元素 public void insert(T element, int index) { if (index < 0 || index > size) { throw new IndexOutOfBoundsException("線性表索引越界"); } // 如果還是空鏈表 if (header == null) { add(element); } else { // 當index為0時，也就是在鏈表頭處插入 if (index == 0) { addAtHeader(element); } else { // 獲取插入點的前一個節點 Node prev = getNodeByIndex(index - 1); // 獲取插入點的節點 Node next = prev.next; // 讓新節點的next引用指向next節點，prev引用指向prev節點 Node newNode = new Node(element, prev, next); // 讓prev的next節點指向新節點 prev.next = newNode; // 讓prev的下一個節點的prev指向新節點 next.prev = newNode; size++; } } } // 采用尾插法為鏈表添加新節點 public void add(T element) { // 如果該鏈表還是空鏈表 if (header == null) { header = new Node(element, null, null); // 只有一個節點，header、tail都指向該節點 tail = header; } else { // 創建新節點，新節點的pre指向原tail節點 Node newNode = new Node(element, tail, null); // 讓尾節點的next指向新增的節點 tail.next = newNode; // 以新節點作為新的尾節點 tail = newNode; } size++; } // 采用頭插法為鏈表添加新節點 public void addAtHeader(T element) { // 創建新節點，讓新節點的next指向原來的header // 并以新節點作為新的header header = new Node(element, null, header); // 如果插入之前是空鏈表 if (tail == null) { tail = header; } size++; } // 刪除鏈式線性表中指定索引處的元素 public T delete(int index) { if (index < 0 || index > size - 1) { throw new IndexOutOfBoundsException("線性表索引越界"); } Node del = null; // 如果被刪除的是header節點 if (index == 0) { del = header; header = header.next; // 釋放新的header節點的prev引用 header.prev = null; } else { // 獲取刪除節點的前一個節點 Node prev = getNodeByIndex(index - 1); // 獲取將要被刪除的節點 del = prev.next; // 讓被刪除節點的next指向被刪除節點的下一個節點 prev.next = del.next; // 讓被刪除節點的下一個節點的prev指向prev節點 if (del.next != null) { del.next.prev = prev; } // 將被刪除節點的prev、next引用賦為null del.prev = null; del.next = null; } size--; return del.data; } // 刪除鏈式線性表中最后一個元素 public T remove() { return delete(size - 1); } // 判斷鏈式線性表是否為空表 public boolean empty() { return size == 0; } // 清空線性表 public void clear() { // 將底層數組所有元素賦為null header = null; tail = null; size = 0; } public String toString() { // 鏈表為空鏈表 if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = header; current != null; current = current.next) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } } // 倒序toString public String reverseToString() { if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = tail; current != null; current = current.prev) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2, len).append("]").toString(); } }} |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | package com.ietree.basic.datastructure.dublinklist;/** * 測試類 * * @author Dylan */public class DuLinkListTest { public static void main(String[] args) { DuLinkList<String> list = new DuLinkList<String>(); list.insert("aaaa", 0); list.add("bbbb"); list.insert("cccc", 0); // 在索引為1處插入一個新元素 list.insert("dddd", 1); // 輸出順序線性表的元素 System.out.println(list); // 刪除索引為2處的元素 list.delete(2); System.out.println(list); System.out.println(list.reverseToString()); // 獲取cccc字符串在順序線性表中的位置 System.out.println("cccc在順序線性表中的位置：" + list.locate("cccc")); System.out.println("鏈表中索引1處的元素：" + list.get(1)); list.remove(); System.out.println("調用remove方法后的鏈表：" + list); list.delete(0); System.out.println("調用delete(0)后的鏈表：" + list); }} |
