LinkedList

查找

linkedList 底层是基于链表 结构的，无法像ArrayList那样随机访问指定位置元素。LinkedList查询过程要稍微麻烦一些，需要从链表头（或者尾结点）向后查找 时间复杂度为o(n)

主要是通过遍历的方式定位目标位置的节点后，取出节点储存的值然后返回。在源码有个优化的地方，就是比较要查询的节点即index 与阶段数量size的一半 的大小，决定是从头节点查询还是从尾结点查询

源代码如下：

public E get(int index) { //检查index是否在size区间内 checkElementIndex(index); //node中存储的为item 数据 next 下一个节点 prev 上一个节点 return node(index).item; } Node<E> node(int index) { //判断size是在前半部分还是在后半部分 if (index < (size >> 1)) { 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; } }

遍历

链表虽然没有数组遍历范快，但是遍历的过程也是很简单，和上面的查找很相似，就是从头结点开始遍历。但是LinkedList 遍历有个可以优化的地方，就是我们在使用forEach循环遍历LinkedList的时候，它其实还是转化为迭代器的形式，所以分析LinkedList的遍历就是迭代器实现的

看源码

public ListIterator<E> listIterator(int index) { //这个方法上面有说过 checkPositionIndex(index); return new ListItr(index); } private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { //先判断index和size是否相等，相等返回最后一个 next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; //调用 next 方法后，next 引用都会指向他的后继节点 nextIndex++; //将该节点的数据返回 return lastReturned.item; } .... }

因为LinkedList 的随机访问效率很差，通过上面的方式每获取一个元素，LinkedList 都需要从头节点（或尾节点）进行遍历。看代码,经过测试，在使用LinkedList的随机访问10000条数据的时候随机访问的时间为4364ms 但是ArrayList的随机访问时间基本可以忽略。所以在开发的时候 需要遍历数据的时候尽量不使用LinkedList

public static void main(String[] args) { List<Integer> linkedList = new LinkedList(); List<Integer> list = new ArrayList(); for (int i = 0; i < 100000; i++) { linkedList.add(i); } for (int i = 0; i < 100000; i++) { list.add(i); } long start = System.currentTimeMillis(); for (int i = 0; i < linkedList.size(); i++) { linkedList.get(i); } long end = System.currentTimeMillis(); System.out.println(end - start); long l = System.currentTimeMillis(); for (int i = 0; i < linkedList.size(); i++) { list.get(i); } long l1 = System.currentTimeMillis(); System.out.println(l1 - l); }

插入

LinkedList；除了实现list接口以外还实现了Deque，实现所以插入的方法实现基本和List中的一致，只不过是链表结构

源码如下:

public boolean add(E e) { //直接在链表最后插入 linkLast(e); return true; } //在指定位置插入 public void add(int index, E element) { checkPositionIndex(index); //判断是否为最后 if (index == size) linkLast(element); else linkBefore(element, node(index)); } //在最后插入 void linkLast(E e) { final Node<E> l = last; //创建一个新的node节点 final Node<E> newNode = new Node<>(l, e, null); //将新节点指定给最后一个节点 last = newNode; //判断该对象中是否含有节点，没有就将新节点赋值为第一个节点，否则赋值为最后一个节点的后继 if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } //往中间插 void linkBefore(E e, Node<E> succ) { //获取传递的node的前驱 final Node<E> pred = succ.prev; //将新节点的前驱和后继赋值 final Node<E> newNode = new Node<>(pred, e, succ); //如果传入的node节点的前驱为null说明该节点为最后一个节点，所以新的节点直接赋值为最后一个节点 succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }

上面插入过程的源码，总结起来就是几部，以linkBefore举例：

创建一个新的节点，并为新节点指明前驱和后继将succ的前驱指向新节点判断succ的后继是否存在，存在就将新节点的后继指向succ的后继，否则定义为最后一个节点

删除

删除操作其实就是 通过解除前后节点的链接实现删除，

源码如下：

public boolean remove(Object o) { if (o == null) { //这个是从第一个节点判断item是否为null 为null直接删除 unlink 下面说 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { //遍历节点，找到符合条件移除 if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //根据index删除 public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } E unlink(Node<E> x) { // assert x != null; //先获取要删除节点的信息 final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //判断前驱是否存在，不存在，说明这个是第一个，那么就将x的后继设置为头结点 if (prev == null) { first = next; } else { //否则，将x前驱的后继 执行x的后继 ，并且将x的后继设置为null prev.next = next; x.prev = null; } //判断x的后继是否为null 为null就说明x的后继为尾结点 ，然后就将尾结点设置为x的前驱 if (next == null) { last = prev; } else { //否则将x的前驱赋值给x后继的前驱 next.prev = prev; x.next = null; } //将x的各个部分设置成null有助于垃圾回收的工作 x.item = null; size--; modCount++; return element; }

删除操作的步骤

将x节点的前驱 的后继指向 x的后继将 x 节点的前驱引用置空，断开与前驱的链接将x节点的后继的前驱执行 x的前驱将x节点的后继引用为null，断开后继的链接

这就是本文的全部内容啦