[TOC] ## LinkedList :-: ![](https://box.kancloud.cn/6ba4ca4b3f6d727ba288f0a3d843b915_769x400.png) ### 1\. 概览 **LinkedList 底层是基于双向链表实现的**,也是实现了 List 接口,所以也拥有 List 的一些特点 (JDK1.7/8 之后取消了循环,修改为双向链表) 。 LinkedList 同时实现了 List 接口和 Deque 接口,也就是说它既可以看作一个顺序容器,又可以看作一个队列(Queue),同时又可以看作一个栈(Stack)。这样看来, LinkedList 简直就是个全能冠军。当你需要使用栈或者队列时,可以考虑使用 LinkedList ,一方面是因为 Java 官方已经声明不建议使用 Stack 类,更遗憾的是,Java里根本没有一个叫做 Queue 的类(它是个接口名字)。 关于栈或队列,现在的首选是 ArrayDeque,它有着比 LinkedList (当作栈或队列使用时)有着更好的性能。 基于双向链表实现,内部使用 Node 来存储链表节点信息。 ~~~java private static class Node<E> { E item; Node<E> next; Node<E> prev; } ~~~ 每个链表存储了 Head 和 Tail 指针: ~~~java transient Node<E> first; transient Node<E> last; ~~~ LinkedList 的实现方式决定了所有跟下标相关的操作都是线性时间,而在首段或者末尾删除元素只需要常数时间。为追求效率*LinkedList*没有实现同步(synchronized),如果需要多个线程并发访问,可以先采用`Collections.synchronizedList()`方法对其进行包装。 ### 2\. add() :-: ![](https://box.kancloud.cn/ad49ee1801fa0eb20dd1807db3734136_800x436.png) add() 方法有两个版本,一个是`add(E e)`,该方法在 LinkedList 的末尾插入元素,因为有 last 指向链表末尾,在末尾插入元素的花费是常数时间。只需要简单修改几个相关引用即可;另一个是`add(int index, E element)`,该方法是在指定下表处插入元素,需要先通过线性查找找到具体位置,然后修改相关引用完成插入操作。 ~~~java // JDK 1.8 public boolean add(E e) { linkLast(e); return true; } /** * Links e as last element. */ void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } ~~~ `add(int index, E element)`的逻辑稍显复杂,可以分成两部分 1. 先根据 index 找到要插入的位置; 2. 修改引用,完成插入操作。 ~~~java public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } ~~~ 上面代码中的`node(int index)`函数有一点小小的 trick,因为链表双向的,可以从开始往后找,也可以从结尾往前找,具体朝那个方向找取决于条件`index < (size >> 1)`,也即是 index 是靠近前端还是后端。 ### 3\. remove() remove() 方法也有两个版本,一个是删除跟指定元素相等的第一个元素`remove(Object o)`,另一个是删除指定下标处的元素`remove(int index)`。 :-: ![](https://box.kancloud.cn/fa1fb1de846a65bcd8c07ed0d7e451c6_800x569.png) 两个删除操作都要: 1. 先找到要删除元素的引用; 2. 修改相关引用,完成删除操作。 在寻找被删元素引用的时候`remove(Object o)`调用的是元素的 equals 方法,而`remove(int index)`使用的是下标计数,两种方式都是线性时间复杂度。在步骤 2 中,两个`revome()`方法都是通过`unlink(Node<E> x)`方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。 ### 4\. get() ~~~java public E get(int index) { checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // assert isElementIndex(index); 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; } } ~~~ 由此可以看出是使用二分查找来看`index`离 size 中间距离来判断是从头结点正序查还是从尾节点倒序查。 * node() 会以`O(n/2)`的性能去获取一个结点 * 如果索引值大于链表大小的一半,那么将从尾结点开始遍历 这样的效率是非常低的,特别是当 index 越接近 size 的中间值时。 ### 5\. 总结 * LinkedList 插入,删除都是移动指针效率很高。 * 查找需要进行遍历查询,效率较低。 ### 6\. ArrayList 与 LinkedList * ArrayList 基于动态数组实现,LinkedList 基于双向链表实现; * ArrayList 支持随机访问,LinkedList 不支持; * LinkedList 在任意位置添加删除元素更快。 ### 面试题:ArrayList 与 LinkedList哪个更占空间? https://www.cnblogs.com/yeya/p/13430797.html