1. 继承关系图谱
2. 特征
有序，元素可重复
3. 源码简析（基于jdk1.8）
根据面向接口编程的设计原则，在实际使用中，我们一般不会定义死容器的具体类型。所以在使用List时，一般是面向List接口编程，这样以后可以方便的替换List的具体类型。LinkedList经常在需要时用来替换ArrayList，它们底层实现的不同使得它们适用于不同的场景。
LinkedList是用双向链表来实现的：
LinkedList内部持有头部和尾部的Node引用，Node是链表的一个节点，其内部构造很简单，只保存持有的元素以及相邻两个节点的引用。所以LinkedList的内部实现如下图所示：
看一下常用的add、get及remove操作
一旦理解了双向链表结构，那以上操作其实理解起来很直观。add操作不指定索引时默认在末尾插入，所以实例化一个node，持有插入的元素，将其作为新的尾节点，其前节点指向原来的尾节点，原来的尾节点的后节点指向新的尾节点，其复杂度为O(1)。当在指定位置插入时，需要先遍历到达指定位置，复杂度为O(n)。有时我们需要将新元素放到第一的位置，这时LinkedList只需要O(1)的时间。
get操作先判断索引离头节点近还是离尾节点近，然后从头节点或尾节点依次遍历到达指定节点，获取其持有的元素，复杂度为O(n)。
remove指定索引处元素的操作和get操作一样，先获得指定索引处的节点，然后将其与相连节点断开，相连节点再互相连接，复杂度为O(n)。不过在实际使用中，更常用的是remove某个确定的元素，这时与ArrayList相比，两者都需要先遍历找到元素，这部分的开销是固定的，但是找到元素后，ArrayList还需要O(n)的时间来删除，而LinkedList仅需要O(1)的时间。
4. 结论
LinkedList是一个有序、持有元素可重复的容器，应用场景较ArrayList相对较少。LinkedList不适合需要频繁查找指定索引处元素的操作，当需要频繁删除、插入时，可以选择LinkedList。
网友评论