Java数据结构之链表的原理及LinkedList的部分源码剖析 (2)

Java中的LinkedList就是底层就是双向循环链表。我们来瞅一下它的源码：

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

我们主要看一下，它的最基本的add方法，来体验一个它的魅力

它有add(E e)和add(int index, E e)两个方法

add(E e)就是添加到链表的最后,最终调用的方法如下：

void linkLast(E e) { //将当前的最后一个节点保存下来 final Node<E> l = last; //构造一个新的节点对象 final Node<E> newNode = new Node<>(l, e, null); //将这个链表的last指向这个新元素 last = newNode; if (l == null){ //这个条件就是说，此时链表为空。因为l是在添加之前的last,如果这个链表为空，last肯定是空的 first = newNode; }else{ l.next = newNode; } size++;//当前的链表大小++ modCount++;//这个是用来记录这个链表的操作次数，对这个链表进行的任何操作，这个都会++ }

上边的构造方法

Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; }

这个插入到时最后的链表并没有去遍历一个整个链表，而是将last.next指向了这个新的节点

add(int index, E e)插入到指定位置
这个最重要的就是利用循环列表来找到这个index是在前半边还是后半边，主要寻找的代码如下：

Node<E> node(int index) { if (index < (size >> 1)) { //上边的>>就是取半，除以2 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

可以看到，它判断了所在的部分进行了不同的遍历方式，就是对二分法的一次简利用

当然，它内部还写了迭代等其他的方法，感兴趣的可以自己看一下。