上一章我们手写了ArrayList的核心源码，ArrayList底层是用了一个数组来保存数据，数组保存数据的优点就是查找效率高，但是删除效率特别低，最坏的情况下需要移动所有的元素。在查找需求比较重要的情况下可以用ArrayList，如果是删除操作比较多的情况下，用ArrayList就不太合适了。Java为我们提供了LinkedList，是用链接来实现的，我们今天就来手写一个QLinkedList，来提示底层是怎么做的。
如上图，底层用一个双链表，另外有两个指示器，一个指向头，一个指向尾。 链表中的每个节点的next指向下一个节点，同理pre指向上一个节点，第一个节点的pre为null，最后一个节点的next为null
双链表的细节实现较多，尤其是边界的问题，要十分仔细，LinkedList中设计了许多的小函数，本例中就不设计那么多的小方法了，直接把最核心的代码都写到一个方法中。以方便揭示核心原理。
下面是完整的QLinkedList的源码，注释很清楚。
1public class QLinkedList<T> { 2 private QNode<T> first; //指向头节点 3 private QNode<T> last; //指向尾节点 4 5 private int size; //节点的个数 6 7 //节点类 8 public static class QNode<T> { 9 T value; //数据 10 QNode<T> pre; //指向上一个节点 11 QNode<T> next; //指向下一个节点 12 13 14 public QNode(QNode<T> pre, QNode<T> next, T value) { 15 this.pre = pre; //节点的上一个指向 16 this.next = next; //节点的下一个指向 17 this.value = value; //存放的数据 18 } 19 } 20 21 public QLinkedList() { 22 23 //默认是一个空狼链表，first,last都为null, 节点个数为0 24 first = null; 25 last = null; 26 size = 0; 27 } 28 29 //默认添加到尾 30 public void add(T e) { 31 addLast(e); 32 } 33 34 //添加到头部 35 public void addFirst(T e) { 36 if (first == null && last == null) { 37 QNode<T> node = new QNode<>(null, null, e); 38 first = node; 39 last = node; 40 } else { 41 QNode<T> node = new QNode<>(null, first, e); 42 first.pre = node; 43 } 44 45 size++; 46 } 47 48 //添加到尾部,我们默认添加的都是不为null的数据 49 public void addLast(T e) { 50 if (e == null) { 51 throw new RuntimeException("e == null"); 52 } 53 54 //1 链表还是空的时候 55 if (size == 0) { 56 57 //1.1 新建一个节点，pre,next都为null 58 QNode<T> node = new QNode(null, null, e); 59 60 //1.2 只有一个节点，first,last都指向null 61 first = node; 62 last = node; 63 64 65 //2 链表不为空 66 } else { 67 68 //2.1 新建一个节点，pre指向last最后一个节点，next为null(因为是最后一个节点) 69 QNode<T> node = new QNode<>(last, null, e); 70 71 //2.2 同时之前的最后一节点的next 指向新建的node节点 72 last.next = node; 73 74 //2.3 然后移动last，让last指向最后一个节点 75 last = node; 76 } 77 78 //添加一个节点后，别忘了节点的总数加 1 79 size++; 80 } 81 82 // position 从 0 开始 83 // 这里面有个小技巧，可以先判断一下 position 是大于 size/2 还是小于 size/2 84 // 如果 position > size / 2 , 说明position是在链表的后半段，我们可以从last开始往前遍历 85 // 如果 position < size / 2, 说明position是在链表的前半段，我们可以从first开始往后遍历 86 // 这样效率会高许多，这也是双链表的意义所在，我们这里就不这样做了。直接从前往后遍历 87 // 读者可以自己实现，以加深对链表的理解 88 public T get(int position) { 89 // 不合法的position直接抛异常，让开发者直接定位问题 90 if (position < 0 || position > size - 1) { 91 throw new RuntimeException("invalid position"); 92 } 93 94 // 如果链表为空，直接返回null 95 if (size == 0) { 96 return null; 97 } 98 99 // 如果链表只有一个节点，直接返回 100 // 因为position合法性在前面已经验证过 101 // 所以在这里面不用验证，一定是0 102 if(size == 1){ 103 return first.value; 104 } 105 106 // 注意这个新建的 p 节点，p.next 指向的是 first 107 // 这是为了下面的循环，保证 i == 0 的时候，p 指向第一个节点 108 QNode<T> p = new QNode<>(null, first, null); 109 for (int i = 0; i <= position; i++) { 110 p = p.next; 111 } 112 113 //如果找到了，就返回value 114 if (p != null) { 115 return p.value; 116 } 117 118 //否则返回 null 119 return null; 120 } 121 122 // 返回链表的节点总个数 123 // 注意first和last节点只是帮助我们方便操作的 124 // size可不包括first,last 125 public int size() { 126 return size; 127 } 128 129 // 删除一个元素，这里传的参数是 T e ，我们也可以传position进行删除，这里就不作演示了 130 // 可以先调用上面的get()方法，返回对应的值，再调用此方法 131 // 读者可以自己实现 132 public T remove(T e) { 133 //1 不合法，抛异常 134 if (e == null) { 135 throw new RuntimeException("e == null"); 136 } 137 138 //2 链表为空，返回 null 139 if (size == 0) { 140 return null; 141 } 142 143 //2 如果链表只有一个节点 144 if (size == 1) { 145 QNode<T> node = first; 146 147 //3 如果相等，删除节点 size-- ,并把first,last赋值为null 148 if(e == node.value || e.equals(node.value)){ 149 first = last = null; 150 size--; 151 return node.value; 152 }else { 153 //4 不相等，返回null 154 return null; 155 } 156 } 157 158 // 如果链表大于1个节点，我们从前往后找value等于e的节点 159 // 1 查找， 和get()方法一样，注意p的next指向first 160 QNode<T> p = new QNode<>(null, first, null); 161 boolean find = false; 162 for (int i = 0; i < size; i++) { 163 p = p.next; 164 165 if (p != null && (e == p.value || e.equals(p.value))) { 166 find = true; 167 break; 168 } 169 } 170 171 // 2 如果找到了 172 if (find) { 173 // 2.1 如果找到的节点是最后一个节点 174 // 删除的是最后一个 175 if (p.next == null) { 176 177 //2.2 改变last的值，指向p的前一个节点 178 last = p.pre; 179 180 //2.3 p的前一个节点，变成了最后一个节点，所以，前一个节点的next值赋值为null 181 p.pre.next = null; 182 183 //2.4 把p.pre赋值为null,已经没有用了 184 p.pre = null; 185 186 //2.5 别忘了节点个数减1 187 size--; 188 189 //2.6 返回删除的节点的value 190 return p.value; 191 192 //3.1 如果删除的是第一个节点（p.pre == null就表明是第一个节点） 193 } else if (p.pre == null) { 194 195 //3.2 改变first的指向，指向p的下一个节点 196 first = p.next; 197 198 //3.3 p的下一个节点变成了第一个节点，需要把p的下一个节点的pre指向为null 199 p.next.pre = null; 200 201 //3.4 p.next没有用了 202 p.next = null; 203 204 //3.5 别忘了节点个数减1 205 size--; 206 207 //3.6 返回删除的节点的value 208 return p.value; 209 210 211 // 4 如果删除的不是第一个也不是最后一个，是中间的某一个，这种情况最简单 212 } else { 213 214 //4.1 p的上一个节点的next需要指向p的下一个节点 215 p.pre.next = p.next; 216 217 //4.2 p 的下一个节点的pre需要指向p的上一个节点 218 p.next.pre = p.pre; 219 220 //4.3 此时p无用了，把p的pre,next赋值为null 221 //这时候不需要调整first,last的位置 222 p.pre = null; 223 p.next = null; 224 225 //4.4 别忘了节点个数减1 226 size--; 227 228 //4.5 返回删除的节点的value 229 return p.value; 230 } 231 } 232 233 //没有找到与e相等的节点，直接返回null 234 return null; 235 } 236 237}
我们来测试一下QLinkedList，测试代码如下：
1 public static void main(String[] args) { 2 QLinkedList<String> list = new QLinkedList<>(); 3 list.add("one"); 4 list.add("two"); 5 list.add("three"); 6 list.add("four"); 7 8 System.out.println(list.size); 9 for (int i = 0; i < list.size; i++) { 10 System.out.println(list.get(i)); 11 } 12 13 System.out.println("==================="); 14 15 System.out.println(list.remove("two")); 16 System.out.println(list.size); 17 for (int i = 0; i < list.size; i++) { 18 System.out.println(list.get(i)); 19 } 20 }
输出如下：
14 2one 3two 4three 5four 6=================== 7two 83 9one 10three 11four
由此可见我们的QLinkedList可以正常的add,get,size,remove了。 建议可以参考一下JDK中的LinkedList。以加深对LinkedList的理解 明天手写HashMap的核心源码实现