1. 原理
LinkedList是基于双链表的动态数组,数据添加删除效率高,只需要改变指针指向即可,但是访问数据的平均效率低,需要对链表进行遍历。因此,LinkedList善于进行一些插入、删除操作,不利于进行检索操作。LinkedList和ArrayList这两个list在我们代码里会经常用到,因此,小编自定义实现LinkedList的简易版--MyLinkedList。
2. public API
3. 图解核心操作
一个节点Node类的数据结构
doClear( ) 方法,初始化一个双链表,先定义一个头结点beginMarker,然后定义一个尾结点endMarker,前驱指向头结点,最后头结点的后继指向尾结点。
添加元素,先定义一个被添加元素x的节点,使它前驱指向被插入位置的前一个,后继指向被插入位置的节点,这是第一步,然后将被插入的前一个节点的next指向此节点,被插入位置的节点的prev指向此节点。
Node<AnyType> newNode = new Node<>(x, p.prev, p); // ①②
newNode.prev.next = newNode; // ③
p.prev = newNode; // ④当然,第三步和第四步可以合并:
Node<AnyType> newNode = new Node<>(x, p.prev, p); // ①②
p.prev = p.prev.next = newNode; // ③④没想到以上4步全可以合并为:
p.prev = p.prev.next = new Node<>(x, p.prev, p); // ①②③④
精辟!
删除元素,根据索引找到对应的节点p,将p的后继的prev指向p的前驱,将p的前驱的next指向p的后继。
p.next.prev = p.prev;
p.prev.next = p.next;
检索节点getNode,LinkedList可以很快很方便地插入和删除元素,但是对于检索元素则就慢了,我们可以将索引分为前半部分和后半部分,如果索引在前半部分,我们就向后的方向遍历该链表;同样的道理,如果索引在后半部分,我们就从终端开始往回走,向前遍历该链表,这样可以提高一下检索速度吧。
// 从头结点开始向后找
if (idx < size() / 2) {
p = beginMarker.next;
for (int i = 0; i < idx; i++) {
p = p.next;
}
}
// 从尾节点开始向前找
else {
p = endMarker;
for (int i = size(); i > idx; i--) {
p = p.prev;
}
}
4. MyLinkedList代码实现
1 package com.hx.list; 2 3 /** 4 * @author: wenhx 5 * @date: Created in 2019/10/17 16:11 6 * @description: 用双链表实现MyLinkedList 7 */ 8 public class MyLinkedList<AnyType> implements Iterable<AnyType> { 9 10 11 private int theSize; 12 private int modCount = 0; 13 private Node<AnyType> beginMarker; 14 private Node<AnyType> endMarker; 15 16 /** 17 * 内部类,定义链表的节点 18 */ 19 private static class Node<AnyType> { 20 21 public AnyType data; 22 public Node<AnyType> prev; 23 public Node<AnyType> next; 24 25 public Node(AnyType d, Node<AnyType> p, Node<AnyType> n) { 26 data = d; 27 prev = p; 28 next = n; 29 } 30 } 31 32 /** 33 * 构造器 34 */ 35 public MyLinkedList() { 36 doClear(); 37 } 38 39 /** 40 * 判空 41 */ 42 public boolean isEmpty() { 43 return size() == 0; 44 } 45 46 /** 47 * 清空 48 */ 49 public void clear() { 50 doClear(); 51 } 52 53 54 /** 55 * 返回链表的长度 56 */ 57 public int size() { 58 return theSize; 59 } 60 61 /** 62 * 根据索引检索元素 63 */ 64 public AnyType get(int idx) { 65 return getNode(idx).data; 66 } 67 68 /** 69 * 根据索引跟新元素 70 */ 71 public AnyType set(int idx, AnyType newVal) { 72 Node<AnyType> p = getNode(idx); 73 AnyType oldVal = p.data; 74 p.data = newVal; 75 return oldVal; 76 } 77 78 /** 79 * 添加元素x 80 */ 81 public boolean add(AnyType x) { 82 add(size(), x); 83 return true; 84 } 85 86 /** 87 * 根据索引添加元素 88 */ 89 public void add(int idx, AnyType x) { 90 addBefore(getNode(idx, 0, size()), x); 91 } 92 93 /** 94 * 根据索引删除元素 95 */ 96 public AnyType remove(int idx) { 97 return remove(getNode(idx)); 98 } 99 100 /** 101 * 打印链表 102 */ 103 public String toString() { 104 StringBuilder sb = new StringBuilder("[ "); 105 106 for (AnyType x : this) { 107 sb.append(x + " "); 108 } 109 sb.append("]"); 110 111 return new String(sb); 112 } 113 114 /** 115 * 清空链表(实现) 116 */ 117 private void doClear() { 118 beginMarker = new Node<>(null, null, null); 119 endMarker = new Node<>(null, beginMarker, null); 120 beginMarker.next = endMarker; 121 theSize = 0; 122 modCount++; 123 } 124 125 /** 126 * 根据索引检索节点 127 */ 128 private Node<AnyType> getNode(int idx) { 129 return getNode(idx, 0, size() - 1); 130 } 131 132 /** 133 * 检索节点 134 */ 135 private Node<AnyType> getNode(int idx, int lower, int upper) { 136 Node<AnyType> p; 137 138 if (idx < lower || idx > upper) { 139 throw new IndexOutOfBoundsException("getNode index: " + idx + "; size: " + size()); 140 } 141 142 if (idx < size() / 2) { 143 p = beginMarker.next; 144 for (int i = 0; i < idx; i++) { 145 p = p.next; 146 } 147 } else { 148 p = endMarker; 149 for (int i = size(); i > idx; i--) { 150 p = p.prev; 151 } 152 } 153 154 return p; 155 } 156 157 /** 158 * 插入节点 159 */ 160 private void addBefore(Node<AnyType> p, AnyType x) { 161 Node<AnyType> newNode = new Node<>(x, p.prev, p); 162 newNode.prev.next = newNode; 163 p.prev = newNode; 164 theSize++; 165 modCount++; 166 } 167 168 /** 169 * 删除节点p 170 */ 171 private AnyType remove(Node<AnyType> p) { 172 p.next.prev = p.prev; 173 p.prev.next = p.next; 174 theSize--; 175 modCount++; 176 177 return p.data; 178 } 179 180 181 /** 182 * 返回一个迭代器对象,用于遍历链表 183 */ 184 public java.util.Iterator<AnyType> iterator() { 185 return new LinkedListIterator(); 186 } 187 188 /** 189 * LinkedListIterator迭代器的实现 190 */ 191 private class LinkedListIterator implements java.util.Iterator<AnyType> { 192 193 private Node<AnyType> current = beginMarker.next; 194 private int expectedModCount = modCount; 195 private boolean okToRemove = false; 196 197 public boolean hasNext() { 198 return current != endMarker; 199 } 200 201 public AnyType next() { 202 if (modCount != expectedModCount) { 203 throw new java.util.ConcurrentModificationException(); 204 } 205 if (!hasNext()) { 206 throw new java.util.NoSuchElementException(); 207 } 208 209 AnyType nextItem = current.data; 210 current = current.next; 211 okToRemove = true; 212 return nextItem; 213 } 214 215 public void remove() { 216 if (modCount != expectedModCount) { 217 throw new java.util.ConcurrentModificationException(); 218 } 219 if (!okToRemove) { 220 throw new IllegalStateException(); 221 } 222 223 MyLinkedList.this.remove(current.prev); 224 expectedModCount++; 225 okToRemove = false; 226 } 227 } 228 229 230 /** 231 * 主方法:用来测试MyLinkedList 232 */ 233 public static void main(String[] args) { 234 MyLinkedList<Integer> myLinkedList = new MyLinkedList<>(); 235 236 for (int i = 0; i < 10; i++) { 237 myLinkedList.add(i); 238 } 239 for (int i = 20; i < 30; i++) { 240 myLinkedList.add(0, i); 241 } 242 243 System.out.println(myLinkedList.toString()); 244 System.out.println("----------"); 245 myLinkedList.remove(0); 246 myLinkedList.remove(myLinkedList.size() - 1); 247 System.out.println(myLinkedList); 248 System.out.println("----------"); 249 java.util.Iterator<Integer> itr = myLinkedList.iterator(); 250 while (itr.hasNext()) { 251 itr.next(); 252 itr.remove(); 253 System.out.println(myLinkedList); 254 } 255 } 256 }
完成,撒花,一个迷你版的LinkedList就写好啦,下次有空再写一个迷你版的ArrayList
http://www.auto-trainer.com/atricle/0fb0bd87.html
http://www.auto-trainer.com/atricle/94e0fbd9.html
http://www.auto-trainer.com/atricle/914307a0.html
http://www.auto-trainer.com/atricle/8ab5cb73.html
http://www.auto-trainer.com/atricle/b79196d2.html
http://www.auto-trainer.com/atricle/5c8ea5fa.html
http://www.auto-trainer.com/atricle/bc97cb4d.html
http://www.auto-trainer.com/atricle/bf5d3689.html
http://www.auto-trainer.com/atricle/01188222.html
http://www.auto-trainer.com/atricle/a8e9f307.html
http://www.auto-trainer.com/atricle/9bdde9c6.html
http://www.auto-trainer.com/atricle/e3354785.html
http://www.auto-trainer.com/atricle/d8735392.html
http://www.auto-trainer.com/atricle/77019316.html
http://www.auto-trainer.com/atricle/e4c817ab.html
http://www.auto-trainer.com/atricle/af3e4812.html
http://www.auto-trainer.com/atricle/bf2b5211.html
http://www.auto-trainer.com/atricle/247d3ad9.html
http://www.auto-trainer.com/atricle/b2afb651.html
http://www.auto-trainer.com/atricle/583b9d93.html
http://www.auto-trainer.com/atricle/9b6f93fb.html
http://www.auto-trainer.com/atricle/4eebe4d0.html
http://www.auto-trainer.com/atricle/bab9a830.html
http://www.auto-trainer.com/atricle/f2d042a9.html
http://www.auto-trainer.com/atricle/b43f5c08.html
http://www.auto-trainer.com/atricle/ca3d6d5a.html
http://www.auto-trainer.com/atricle/dbe14253.html
http://www.auto-trainer.com/atricle/5b8ae834.html
http://www.auto-trainer.com/atricle/7dc5caae.html
http://www.auto-trainer.com/atricle/65c2038a.html
http://www.auto-trainer.com/atricle/c7f32c55.html
http://www.auto-trainer.com/atricle/0a27a143.html
http://www.auto-trainer.com/atricle/b80b3e03.html
http://www.auto-trainer.com/atricle/df0257e6.html
http://www.auto-trainer.com/atricle/ae7f389b.html
http://www.auto-trainer.com/atricle/d167534c.html
http://www.auto-trainer.com/atricle/2b8d712a.html
http://www.auto-trainer.com/atricle/9b436c36.html
http://www.auto-trainer.com/atricle/dcab4ea6.html
http://www.auto-trainer.com/atricle/f91e54ae.html
http://www.auto-trainer.com/atricle/e18ef12b.html
http://www.auto-trainer.com/atricle/55c87a73.html
http://www.auto-trainer.com/atricle/d91ec75e.html
http://www.auto-trainer.com/atricle/66ac0529.html
http://www.auto-trainer.com/atricle/f301f5ef.html
http://www.auto-trainer.com/atricle/36d617e6.html
http://www.auto-trainer.com/atricle/45aed19c.html
http://www.auto-trainer.com/atricle/e45557e2.html
http://www.auto-trainer.com/atricle/76f84eaf.html
http://www.auto-trainer.com/atricle/c64953f9.html
http://www.auto-trainer.com/atricle/77f9c0f5.html
http://www.auto-trainer.com/atricle/406cd2ad.html
http://www.auto-trainer.com/atricle/1002fac0.html
http://www.auto-trainer.com/atricle/28ef1bb1.html
http://www.auto-trainer.com/atricle/e55fc47a.html
http://www.auto-trainer.com/atricle/be169276.html
http://www.auto-trainer.com/atricle/3443a9c3.html
http://www.auto-trainer.com/atricle/f7617387.html
http://www.auto-trainer.com/atricle/b44f4349.html
http://www.auto-trainer.com/atricle/ace6cf88.html
http://www.auto-trainer.com/atricle/cee87c90.html
http://www.auto-trainer.com/atricle/7f3a42d6.html
http://www.auto-trainer.com/atricle/c3eaf4a1.html
http://www.auto-trainer.com/atricle/2e2da24d.html
http://www.auto-trainer.com/atricle/5f59b653.html
http://www.tcinsulator.com/atricle/0e8c0c65.html
http://www.tcinsulator.com/atricle/c49d1eab.html
http://www.tcinsulator.com/atricle/0bc60daf.html
http://www.tcinsulator.com/atricle/6d8c7b4f.html
http://www.tcinsulator.com/atricle/510e1ee7.html
http://www.tcinsulator.com/atricle/86df1ebb.html
http://www.tcinsulator.com/atricle/ab8a71ce.html
http://www.tcinsulator.com/atricle/0f3789de.html
http://www.tcinsulator.com/atricle/14414508.html
http://www.tcinsulator.com/atricle/7e7751a9.html
http://www.tcinsulator.com/atricle/ea77b8c9.html
http://www.tcinsulator.com/atricle/a626d65e.html
http://www.tcinsulator.com/atricle/3793a844.html
http://www.tcinsulator.com/atricle/3001e4ef.html
http://www.tcinsulator.com/atricle/ba3b3601.html
http://www.tcinsulator.com/atricle/60cfec18.html
http://www.tcinsulator.com/atricle/b6415e25.html
http://www.tcinsulator.com/atricle/7337d1dc.html
http://www.tcinsulator.com/atricle/36c6fd97.html
http://www.tcinsulator.com/atricle/079d1299.html
http://www.tcinsulator.com/atricle/aaf263e2.html
http://www.tcinsulator.com/atricle/5b23848f.html
http://www.tcinsulator.com/atricle/83f7e371.html
http://www.tcinsulator.com/atricle/ff4cbdbd.html
http://www.tcinsulator.com/atricle/28baa93b.html
http://www.tcinsulator.com/atricle/3c862a80.html
http://www.tcinsulator.com/atricle/d659d458.html
http://www.tcinsulator.com/atricle/dae75021.html
http://www.tcinsulator.com/atricle/c50b9a94.html
http://www.tcinsulator.com/atricle/d1d0bf61.html
http://www.tcinsulator.com/atricle/bf92c7f8.html
http://www.tcinsulator.com/atricle/88999deb.html
http://www.tcinsulator.com/atricle/5c78c953.html
http://www.tcinsulator.com/atricle/38d7a810.html
http://www.tcinsulator.com/atricle/0e136a6b.html
http://www.tcinsulator.com/atricle/5d13c0f3.html
http://www.tcinsulator.com/atricle/461301ad.html
http://www.tcinsulator.com/atricle/37a05a50.html
http://www.tcinsulator.com/atricle/d29f9007.html
http://www.tcinsulator.com/atricle/11a7253d.html
http://www.tcinsulator.com/atricle/509f7de5.html
http://www.tcinsulator.com/atricle/ec96c586.html
http://www.tcinsulator.com/atricle/9a9c136b.html
http://www.tcinsulator.com/atricle/a95fdca8.html
http://www.tcinsulator.com/atricle/45aee0a4.html
http://www.tcinsulator.com/atricle/9c54bac2.html
http://www.tcinsulator.com/atricle/b2c58696.html
http://www.tcinsulator.com/atricle/21b5a77c.html
http://www.tcinsulator.com/atricle/6d352c23.html
http://www.tcinsulator.com/atricle/0e6d888e.html
http://www.tcinsulator.com/atricle/3ff927da.html
http://www.tcinsulator.com/atricle/68e6217f.html
http://www.tcinsulator.com/atricle/7f12ff15.html
http://www.tcinsulator.com/atricle/91eb7ab0.html
http://www.tcinsulator.com/atricle/7ef3b35b.html
http://www.tcinsulator.com/atricle/4037f2b7.html
http://www.tcinsulator.com/atricle/8d8e6998.html
http://www.tcinsulator.com/atricle/42aebd42.html
http://www.tcinsulator.com/atricle/7cfd0343.html
http://www.tcinsulator.com/atricle/57c3eaac.html
http://www.tcinsulator.com/atricle/8390f01d.html
http://www.tcinsulator.com/atricle/e97ad32a.html
http://www.tcinsulator.com/atricle/981f04e6.html
http://www.tcinsulator.com/atricle/ea093889.html
http://www.tcinsulator.com/atricle/a8e6a620.html
http://www.czctt.com/atricle/3bf06bb2.html
http://www.czctt.com/atricle/0608e5a5.html
http://www.czctt.com/atricle/3e292c26.html
http://www.czctt.com/atricle/ff8fb0e5.html
http://www.czctt.com/atricle/470fda4f.html
http://www.czctt.com/atricle/4293817f.html
http://www.czctt.com/atricle/ff175d5d.html
http://www.czctt.com/atricle/03d376c3.html
http://www.czctt.com/atricle/5419ef3b.html
http://www.czctt.com/atricle/8c3ca7e7.html
http://www.czctt.com/atricle/aa580434.html
http://www.czctt.com/atricle/05b2446e.html
http://www.czctt.com/atricle/d91ae73e.html
http://www.czctt.com/atricle/70b0bbed.html
http://www.czctt.com/atricle/a27ffc3e.html
http://www.czctt.com/atricle/8380fdcc.html
http://www.czctt.com/atricle/81c1bf63.html
http://www.czctt.com/atricle/c80dd9c7.html
http://www.czctt.com/atricle/d0ab681c.html
http://www.czctt.com/atricle/3d1e37d7.html
http://www.czctt.com/atricle/b0ecc8ac.html
http://www.czctt.com/atricle/cf7b2e72.html
http://www.czctt.com/atricle/80fc400e.html
http://www.czctt.com/atricle/975c5443.html
http://www.czctt.com/atricle/a34a8158.html
http://www.czctt.com/atricle/4ba51e17.html
http://www.czctt.com/atricle/40eb2ece.html
http://www.czctt.com/atricle/2709673e.html
http://www.czctt.com/atricle/57017980.html
http://www.czctt.com/atricle/bf868de1.html
http://www.czctt.com/atricle/45a124a7.html
http://www.czctt.com/atricle/b23b40ea.html
http://www.czctt.com/atricle/fc0448a5.html
http://www.czctt.com/atricle/4d929878.html
http://www.czctt.com/atricle/4bf763c5.html
http://www.czctt.com/atricle/205d534c.html
http://www.czctt.com/atricle/329535dd.html
http://www.czctt.com/atricle/cec173cc.html
http://www.czctt.com/atricle/6f262593.html
http://www.czctt.com/atricle/04b5189b.html
http://www.czctt.com/atricle/c1ccb762.html
http://www.czctt.com/atricle/ec3e9516.html
http://www.czctt.com/atricle/d9a0d77d.html
http://www.czctt.com/atricle/98bf8552.html
http://www.czctt.com/atricle/67d0e3db.html
http://www.czctt.com/atricle/252acf36.html
http://www.czctt.com/atricle/dca05126.html
http://www.czctt.com/atricle/6ae60a60.html
http://www.czctt.com/atricle/80db3490.html
http://www.czctt.com/atricle/bff880fc.html
http://www.czctt.com/atricle/00bbbf24.html
http://www.czctt.com/atricle/1dd70ec6.html
http://www.czctt.com/atricle/cc5e3193.html
http://www.czctt.com/atricle/b657aef8.html
http://www.czctt.com/atricle/611d4ebd.html
http://www.czctt.com/atricle/588202fe.html
http://www.czctt.com/atricle/229cddc5.html
http://www.czctt.com/atricle/8e8ba5fa.html
http://www.czctt.com/atricle/ea361a45.html
http://www.czctt.com/atricle/dc1f9294.html
http://www.czctt.com/atricle/6dceaddf.html
http://www.czctt.com/atricle/51ea1907.html
http://www.czctt.com/atricle/6c1fe6b4.html
http://www.czctt.com/atricle/894c8d3a.html
http://www.auto-trainer.com/atricle/0fb0bd87.html
http://www.auto-trainer.com/atricle/94e0fbd9.html
http://www.auto-trainer.com/atricle/914307a0.html
http://www.auto-trainer.com/atricle/8ab5cb73.html
http://www.auto-trainer.com/atricle/b79196d2.html
http://www.auto-trainer.com/atricle/5c8ea5fa.html
http://www.auto-trainer.com/atricle/bc97cb4d.html
http://www.auto-trainer.com/atricle/bf5d3689.html
http://www.auto-trainer.com/atricle/01188222.html
http://www.auto-trainer.com/atricle/a8e9f307.html
http://www.auto-trainer.com/atricle/9bdde9c6.html
http://www.auto-trainer.com/atricle/e3354785.html
http://www.auto-trainer.com/atricle/d8735392.html
http://www.auto-trainer.com/atricle/77019316.html
http://www.auto-trainer.com/atricle/e4c817ab.html
http://www.auto-trainer.com/atricle/af3e4812.html
http://www.auto-trainer.com/atricle/bf2b5211.html
http://www.auto-trainer.com/atricle/1026b966.html
http://www.auto-trainer.com/atricle/517b5067.html
http://www.auto-trainer.com/atricle/7c96e90a.html
http://www.auto-trainer.com/atricle/d84d3f52.html
http://www.auto-trainer.com/atricle/41f7764b.html
http://www.auto-trainer.com/atricle/20c3decb.html
http://www.auto-trainer.com/atricle/106ab1ae.html
http://www.auto-trainer.com/atricle/9129c14e.html
http://www.auto-trainer.com/atricle/b73759b5.html
http://www.auto-trainer.com/atricle/b1508875.html
http://www.auto-trainer.com/atricle/4f2e69de.html
http://www.auto-trainer.com/atricle/59b6cf53.html
http://www.auto-trainer.com/atricle/262325f8.html
http://www.auto-trainer.com/atricle/2ea33b4b.html
http://www.auto-trainer.com/atricle/efcfe1c9.html
http://www.auto-trainer.com/atricle/4ee0fe37.html