写在前面：
双向链表是一种对称结构，它克服了单链表上指针单向性的缺点，其中每一个节点即可向前引用，也可向后引用，这样可以更方便的插入、删除数据元素。
由于双向链表需要同时维护两个方向的指针，因此添加节点、删除节点时指针维护成本更大；但双向链表具有两个方向的指针，因此可以向两个方向搜索节点，因此双向链表在搜索节点、删除指定索引处节点时具有较好的性能。
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); }} |
