LinkedList分析
下面是LinkedList所继承和实现的父类的关系图
图中，红色的线代表的是继承关系，蓝色的线代表实现关系，方框标明红色A的表示是抽象类，红色I的表示是接口。
Iterable(Interface))
这个接口的意思是可迭代，也就是说，实现该接口的类都是可以迭代的。
Collection(Interface)
这是集合的父类，我们熟知的Set和List都是这个Collection接口的子接口。
该接口中定义了一些集合共有的方法
比如: size(), isEmpty(), contains(Object o), iterator(),add(),remove(Object o),clear(),equals(Object o)等方法，具体各个方法的意思是什么，应该不用说了。
Queue(Interface)
该接口描述的是队列，队列是一种先进先出的数据结构，所以它对应操作有入队，出队。
它里面声明了几个方法：
入队：add(), offer()
出队：remove(), poll()
获取队列的第一个元素：element(), peek()
以上方法都是对应队列中的一些实现逻辑
Deque(Interface)
该接口是Queue接口的一个子接口，主要是用来描述双端队列的，当然，我们在实现栈的时候，其实也与这个接口有关。
既然是要描述双端队列，那么就是说两边都可以对元素进行操作了。
所以它除了有Queue接口中方法，还增加了一些操作“双端”的方法
比如：addFirst(), addLast(), offerFirst(),offerLast(),iterator()等，这些方法从名字上就知道是什么意思了，也正是这些方法才实现了双端操作元素，iterator方法也说明了我们在实现队列和栈时可以迭代
当然，对于操作栈，还有两个我们在数据结构中熟悉的方法名：push()和pop()，入栈和出栈。
List(Interface)
List接口直接继承了Collection接口，这个集合的常用实现类就是ArrayList和LinkedList，而且是一个有序、可重复的集合。所以里面增加了一些方法。
比如：get(),set(),indexOf(),lastIndexOf(),subList()等方法。
AbstractCollection,AbstractList,AbstractSequentialList(abstract)
这三个都是抽象类，其中实现了部分Collection和List中的抽象方法。
LinkedList
LinkedList是一个实现类，其内部是用一个双向链表实现该集合的功能。内部维护了一个first和last结点，这样就可以方便的操作集合了。
该结点是LinkedList的内部类，下面是该内部类的源码
2
3
4
5
6
7
8
9
10
11
12
13
2 E item;
3 Node<E> next;
4 Node<E> prev;
5
6 Node(Node<E> prev, E element, Node<E> next) {
7 this.item = element;
8 this.next = next;
9 this.prev = prev;
10 }
11}
12
13
这个双向链表就是该集合的核心之一。
接下来看看其中的一些方法吧
针对链表的操作无非就是元素的插入，删除。其中的插入又有三种情况，即从头结点、指定位置、尾部插入，删除同理。
2
3
4
5
6
2 linkLast(e);
3 return true;
4}
5
6
我们直接看其中的几个是如何实现的吧
-
增加元素
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2 linkLast(e);
3 return true;
4}
5
6/**
7 * Links e as last element.
8 */
9void linkLast(E e) {
10 final Node<E> l = last;
11 final Node<E> newNode = new Node<>(l, e, null);
12 last = newNode;
13 if (l == null)
14 first = newNode;
15 else
16 l.next = newNode;
17 size++;
18 modCount++;
19}
20
21
队列和栈对应的入队操作（就是就是在链表的最后增加一个新的结点），其实也是调用上面这个方法
2
3
4
5
6
7
8
9
2 return add(e);
3}
4
5public void push(E e) {
6 addFirst(e);
7}
8
9
2
2
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
2 return removeFirst();
3}
4
5public E removeFirst() {
6 final Node<E> f = first;
7 if (f == null)
8 throw new NoSuchElementException();
9 return unlinkFirst(f);
10}
11
12/**
13 * Unlinks non-null first node f.
14 */
15private E unlinkFirst(Node<E> f) {
16 // assert f == first && f != null;
17 final E element = f.item;
18 final Node<E> next = f.next;
19 f.item = null;
20 f.next = null; // help GC
21 first = next;
22 if (next == null)
23 last = null;
24 else
25 next.prev = null;
26 size--;
27 modCount++;
28 return element;
29}
30
31
因为队列先进先出的，所以出队就是删除头元素
2
3
4
5
6
2 final Node<E> f = first;
3 return (f == null) ? null : unlinkFirst(f);
4}
5
6
栈是先进后出，所以出栈实际上是删除最后一个元素
2
3
4
5
2 return removeFirst();
3}
4
5
- 总结
LinkedList底层使用双向链表实现的，这个类中维护了一个first（头结点），last（最后一个结点），size（链表的长度），还有一个modCount（链表被操作的次数），这个modCount我们暂时用不到，只要理解了双向链表，那么集合框架中的LinkedList就没有难度了。
