一、数据结构通讲
1.链表
①链表基本介绍
在上篇讲完了数组【源码系列】Java中的数据结构——数组与ArrayList之后，我们知道了数组因为连续存储的原因，所以用下标访问时时间复杂度为O(1)。但连续存储也带来一个问题——数组对于内存条件太苛刻了，系统不可能为它之后预留一大块连续空间，所以数组的大小在一开始便确认了。
在这种情况下，数组对于增删扩容的操作并不友好，每次删除增加都伴随着后续元素的前移和后移，如果容量不够，还得进行数组的复制来达到扩容的效果。
所以数组适合于一些增删操作不怎么频繁且不会经常需要扩容的情况。
但是面对增删操作比较频繁的情况该怎么办呢？
面对这种情况，有没有一种方式可以适应这种增删操作特别平凡的情况呢？
这时候就轮到我们的链表出场了。
我们知道数组这些优缺点的根本原因在于它的存储方式——连续存储。那么我们能不能不连续存储，采取零散存储的方式来避免这种情况呢。
答案是可以的，但此时又面临着一个问题——如何访问对应的元素？
数组因为连续存储的方式可以根据下标轻而易举地确定元素的地址，可是链表是如何做的呢？
在链表中，我们把每个元素叫做结点，结点一般包括该元素的值以及指向下一个元素的指针，有了下一个元素的指针我们便可以方便地访问下一个元素的地址，这样就可以访问对应的元素了。
换个形象点的说法，我们可以把每个元素想象成一个铁链上的一个铁环，元素的指针就是那个环扣，这样我们把每个铁环环环相扣，那么便组成了一条长长的链子，而这便是链表。
（图片来自王争的数据结构与算法之美）
而链表的结构也五花八门，常见的有单链表，双向链表，循环链表。
（图片来自王争的数据结构与算法之美）
看图应该很快就能明白，它们的区别就在于结点之间的连接方式，或者说结点里的指针。
对于单链表，
如果我们要删除链表中的结点时，只需将前一个结点指针指向这个结点即可。事实上，从内存上看，这个结点并未“删除”，只是链表中指向它的指针指向了另一个结点，这样这个结点就脱离了这个链表，逻辑上就是在这个链表上删除了这个元素。
增加也同理，只需把前一个结点的指针指向新加的结点，新加的结点指针只需指向下一个结点即可。
这样链表增加删除元素实际只需做好指针重新赋值即可，时间复杂度也是O（1）。
②链表的优缺点
优点：
1.由于分散存储，对于内存的要求不高，可以有效利用现有内存空间
2.增删元素非常方便快速，只需把结点的指针重新赋值即可
缺点：
1.根据下标查询效率慢，只能一个一个遍历
2.因为每个结点还需要存储其他结点的指针，所以占用的内存空间会多一些
2.栈
关于“栈”，你可以把它想象成一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。
（来自王争的数据结构与算法之美）
从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
3.队列
队列这个概念非常好理解。
你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。
我们知道，栈只支持两个基本操作：入栈 push()和出栈 pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。
（来自王争的数据结构与算法之美）
所以，队列跟栈一样，也是一种操作受限的线性表数据结构。
二、LinkedList源码探究
1.LinkedList继承关系
可以看到LinkedList既实现了List接口，也实现了Queue接口（队列），同时也实现了Queue的子类接口Deque接口（双向队列）。
我们前面讲队列和栈的时候讲到栈和队列都是操作受限的线性表，所以我们完全可以用链表来实现队列和栈。而这就是为什么LinkedList会实现Queue和Deque的原因，目的就是提供一个操作受限的接口供用户使用。
2.LinkedList核心原理
2.1内部类Node
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; } }
这里看到结点里有两个指针，一个指向上一个结点，一个指向下一个结点，所以我们可以知道LinkedList实际上是一个双向链表。
2.2属性
//当前list中元素的数量 transient int size = 0; /** * 指向第一个结点的指针 */ transient Node<E> first; /** * 指向最后一个结点的指针 */ transient Node<E> last;
LinkedList对象中的属性就只有三个，事实上在所有集合类中，为了尽可能减少内存消耗，都会尽可能少地去设计属性。
2.3 构造方法
public LinkedList() { } public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
一个是空构造函数，里面啥也没干；一个是创建一个LinkedList对象，然后将集合c中的元素都添加进对象中。
PS：这里并没有像ArrayList那样有规定初始大小的构造函数，因为链表容量本来就是可以增加的，所以不需要有这样的构造函数。
点开addAll（）方法
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }
public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); //调用集合c的toArray方法将集合类对象转化为对象数组 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; //找到对应下标的结点 if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } //循环插入 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } //最后一个结点的处理 if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; //修改操作计数+1 modCount++; return true; }
大致来讲它调用了集合的toArray()方法将集合c化为数组，然后循环创建结点然后加到对应的位置，同时修改计数+1
