链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域，
另一个是存储下一个结点地址的指针域。双链表是链表的一种，由节点组成，每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
二、LinkedList 2.1 LinkedList基本介绍LinkedList是一个实现了List接口和Deque接口的双端链表。有关索引的操作可能从链表头开始遍历到链表尾部，也可能从尾部遍历到链表头部，这取决于看索引更靠近哪一端。
LinkedList不是线程安全的，如果想使LinkedList变成线程安全的，可以使用如下方式：
List list = Collections.synchronizedList(new LinkedList(...));iterator()和listIterator()返回的迭代器都遵循fail-fast机制。 LinkedList的继承关系如下图所示：
从上图可以看出LinkedList与ArrayList的不同之处，ArrayList直接继承自AbstractList，而LinkedList继承自AbstractSequentialList，然后再继承自AbstractList。另外，LinkedList还实现了Dequeu接口，双端队列。
2.2 内部结构
动画演示
从上图可以看出，LinkedList内部是一个双端链表结构，有两个变量，first指向链表头部，last指向链表尾部。
LinkedtList内部的成员变量如下：
下面是Node节点的定义，Node类LinkedList的静态内部类
从Node的定义可以看出链表是一个双向链表结构
2.3 构造方法LinkedList有两个构造方法，一个用于构造一个空的链表，一个用已有的集合创建链表。如下：
当使用第二个构造方法时，会调用addAll()方法将集合中的元素添加到链表中
2.4 添加操作 2.4.1 add(E e)add(E e)用于将元素添加到链表尾部，实现如下:
从上面代码可以看到，linkLast方法中就是一个链表尾部添加一个双端节点的操作，但是需要注意对链表为空时头节点的处理。
2.4.2 add(int index,E e)1.checkPositionIndex
2.isPositionIndex
3.add
从上面代码可以看到，主要分为3步： 1. 检查index的范围，否则抛出异常 2. 如果插入位置是链表尾部，那么调用linkLast方法 3. 如果插入位置是链表中间，那么调用linkBefore方法
4.node(int index)
该方法返回指定位置的节点，实现如下：
从上面可以看到，node(int index)方法将根据index是靠近头部还是尾部选择不同的遍历方向。一旦得到了指定索引位置的节点，再看linkBefore()方法，实现如下：
5.linkBefore
从上图以及代码可以看到linkBefore主要分三步： 1. 创建newNode节点，将newNode的后继指针指向succ，前驱指针指向pred 2. 将succ的前驱指针指向newNode 3. 根据pred是否为null，进行不同操作。 - 如果pred为null，说明该节点插入在头节点之前，要重置first头节点 - 如果pred不为null，那么直接将pred的后继指针指向newNode即可
2.5 删除操作 2.5.1 remove(int index)
从上面可以看到remove(int index)操作有两步： 1. 检查index范围，属于[0,size） 2. 将索引处节点删除
2.5.2 remove(Object o)1.remove
从代码可以看到，由于LinkedList可以存储null元素，所以对删除对象以是否为null做区分。然后从链表头开始遍历，一旦匹配，就会调用unlink()方法将该节点从链表中移除。下面是unlink()方法的实现：
2.unlink
get(int index)方法根据指定索引返回数据，如果索引越界，那么会抛出异常。实现如下：
LinkedList的iterator()方法内部调用了其listIterator()方法，所以可以只分析listIterator()方法。
private class ListItr implements ListIterator {
// 上一次返回的节点，默认为null
private Node lastReturned;
// 下次调用next返回的节点
private Node next;
// 下次调用next返回的节点的index
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
// next为列表中下标为index的元素，如果到最后，为null
next = (index == size) ? null : node(index);
// 设置nextIndex
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++;
// 返回lastReturned节点的元素item
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
// next为null，next为last，否则为next的prev
// lastReturned = next
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
// 如果为null，报错
throw new IllegalStateException();
Node lastNext = lastReturned.next;
// 删除lastReturned
unlink(lastReturned);
// 设置next
if (next == lastReturned)
// 刚刚调用了previous
next = lastNext;
else
// 刚刚调用next
nextIndex--;
lastReturned = null;
// expectedModCount也进行++
expectedModCount++;
}
}在ListIterator的构造器中，得到了当前位置的节点，就是变量next。
next()方法返回当前节点的值并将next指向其后继节点，previous()方法返回当前节点的前一个节点的值并将next节点指向其前驱节点。
由于Node是一个双端节点，所以这儿用了一个节点就可以实现从前向后迭代和从后向前迭代。
另外在ListIterator初始时，exceptedModCount保存了当前的modCount，如果在迭代期间，有操作改变了链表的底层结构，那么再操作迭代器的方法时将会抛出ConcurrentModificationException。
三、测试
LinkedList是基于双向链表的List，其内部的实现源于对链表的操作，所以适用于频繁增加、删除的情况；因为，查询元素需要一个一个遍历，所以查询效率比较低。该类不是线程安全的；另外，由于LinkedList实现了Queue接口，所以LinkedList不止有队列的接口，还有栈的接口，可以使用LinkedList作为队列和栈的实现。
参考博客，视频教程
