LinkedList类源码浅析(一)

1、先来看一看LinkedList类的字段和构造方法

size记录链表的长度，first永远指向链表的第一个元素，last永远指向链表的最后一个元素

提供两个构造方法，一个无参的构造方法，一个接受一个Collection对象为参数的构造方法

first和last的类型都是Node，Node是LinkedList类中的一个私有的静态内部类，定义非常简单

Node类中定义了三个字段，数据域item，后继元素next，前驱元素prev，而且都是接受泛型的

2、来看第一个方法linkFirst(E e)

这是在链表的头部添加一个元素

　　1）如果链表为空时，first和last都指向同一个节点

　　2）如果链表不为空，则在第一个元素之前插入新节点，并让first指向新的节点；

由上述可知：

LinkedList是一个链式结构，由两个指针分别指向第一个节点和最后一个节点，中间的节点由next和prev链式指向；

因为存在next和prev两个域，LinkedList是一个双向的结构，构成双向链表；

每插入一个新的元素，都会创建一个新的Node节点对象；

3、从链表头部删除一个元素：unlinkFirst(Node<E> f)

从双向链表的头部删除一个元素，并返回删除元素的数据域；

得到first指向元素的后继，如果没有后继元素，直接把last置空，如果有后继元素，则把这个后继元素的prev域置空；

4、从链表中删除一个元素：E unlink(Node<E> x)

从上述删除过程中需要注意的是，前驱和后继元素可能为空；如果为空就需要对first和last两个指针做特殊处理；

巴特西