java集合类的底层实现

LinkedList底层实现和原理

LinkedList类是List接口的实现类，它是一个集合，可以根据索引来随机的访问集合中的元素，还实现了Deque接口，它还是一个队列，可以被当成双端队列来使用。虽然LinkedList是一个List集合，但是它的实现方式和ArrayList是完全不同的，ArrayList的底层是通过一个动态的Object[]数组来实现的，而LinkedList的底层是通过链表来实现的，因此它的随机访问速度是比较差的，但是它的删除，插入操作会很快。

1、LinkedList是基于双向循环链表实现的，除了可以当做链表来操作外，它还可以当做栈、队列和双端队列来使用。

2、LinkedList同样是非线程安全的，只在单线程下适合使用。

3、LinkedList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了Cloneable接口，能被克隆。

---

链表

链表是由一系列非连续的节点组成的存储结构，简单分下类的话，链表又分为单向链表和双向链表，而单向/双向链表又可以分为循环链表和非循环链表，下面简单就这四种链表进行图解说明。

1、单向链表

单向链表就是通过每个结点的指针指向下一个结点从而链接起来的结构，最后一个节点的next指向null。

2、单向循环链表

单向循环链表和单向链表的不同是，最后一个节点的next不是指向null，而是指向head节点，形成一个“环”。

3、双向链表

从名字就可以看出，双向链表是包含两个指针的，pre指向前一个节点，next指向后一个节点，但是第一个节点head的pre指向null，最后一个节点tail的next指向null。

4.双向循环链表

双向循环链表和双向链表的不同在于，第一个节点的pre指向最后一个节点，最后一个节点的next指向第一个节点，也形成一个“环”。而LinkedList就是基于双向循环链表设计的。

---

LinkedList是通过双向链表去实现的，既然是链表实现那么它的随机访问效率比ArrayList要低，顺序访问的效率要比较的高。每个节点都有一个前驱（之前前面节点的指针）和一个后继（指向后面节点的指针），效果如下图：

构造函数

1、LinkedList()

2、LinkedList(Collection c)

LinkedList没有长度的概念，所以不存在容量不足的问题，因此不需要提供初始化大小的构造方法，因此值提供了两个方法，一个是无参构造方法，初始一个LinkedList对象，和将指定的集合元素转化为LinkedList构造方法。

添加方法

添加方法默认是添加到LinkedList的尾部，首先将last指定的节点赋值给l节点，然后新建节点newNode ,此节点的前驱指向l节点，data = e , next = null , 并将新节点赋值给last节点，它成为了最后一个节点，根据当前List是否为空做出相应的操作。若不为空将l的后继指针修改为newNode。 size +1 , modCount＋１。

删除方法

删除方法，先循环遍历列表，找到item == o 的节点，在调用unlink()方法删除。

总结：

1、LinkedList是一个功能很强大的类，可以被当作List集合，双端队列和栈来使用。

2、LinkedList底层使用链表来保存集合中的元素，因此随机访问的性能较差，但是插入删除时性能非常的出色。

3、LinkedList在1.8版本有添加了一点新的内容，添加了一个static final 修饰的内部类LLSpliterator 并实现了Spliterator ，为了实现并行遍历而新添加的功能，整体的变化并不是很大。

List实现类的使用场景

ArrayList，底层采用数组实现，如果需要遍历集合元素，应该使用随机访问的方式，对于LinkedList集合应该采用迭代器的方式。

如果需要经常的插入。删除操作可以考虑使用LinkedList集合。

如果有多个线程需要同时访问List集合中的元素，开发者可以考虑使用Collections将集合包装成线程安全的集合。

补充说明

1、从源码中很明显可以看出，LinkedList的实现是基于双向循环链表的，且头结点中不存放数据。

2、注意两个不同的构造方法。无参构造方法直接建立一个仅包含head节点的空链表，包含Collection的构造方法，先调用无参构造方法建立一个空链表，而后将Collection中的数据加入到链表的尾部后面。

3、在查找和删除某元素时，源码中都划分为该元素为null和不为null两种情况来处理，LinkedList中允许元素为null。

4、LinkedList是基于链表实现的，因此不存在容量不足的问题，所以这里没有扩容的方法。

5、注意源码中的Entry entry(int index)方法。该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果indexsize/2，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历，从而提高一定的效率（实际上效率还是很低）。

6、注意链表类对应的数据结构Entry。

7、LinkedList是基于链表实现的，因此插入删除效率高，查找效率低（虽然有一个加速动作）。

8、要注意源码中还实现了栈和队列的操作方法，因此也可以作为栈、队列和双端队列来使用。