java.util.LinkedList源码阅读

LinkedList 是链表实现的线性表（双链表），元素有序且可以重复。

LinkedList继承AbstractSequentialList并且实现了List和Deque，Cloneable, Serializable接口。

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable

 1.属性

//链表元素的个数 transient int size = 0; //第一个元素的指针 transient Node<E> first; //最后一个元素的指针 transient Node<E> last;

Node 类，这是 LinkedList 类中的一个内部类，集合里每一个元素就代表一个 Node 类对象，LinkedList 集合就是由许多个 Node 对象类似于手拉着手构成，由此可知，LinkedList是一个双向链表。

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; } }

每个节点都prev都保存上一个节点的引用，next保存下一个节点的引用；

 

2.构造函数

无参构造函数 public LinkedList() { } 泛型参数有参构造函数 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

3.添加元素

添加元素 public boolean add(E e) { //将元素添加到链表的尾部 linkLast(e); return true; } void linkLast(E e) { //用变量将链表的尾节点存储下来 final Node<E> l = last; //新增加一个元素，即新增加一个node节点。该节点prev指向当前last节点，e为添加元素，next指向null final Node<E> newNode = new Node<>(l, e, null); //将链表尾部指向新节点 last = newNode; if (l == null) //如果链表为空，将这个新节点也设为头部节点，那么新增节点既是头节点也是尾节点,并且头节点的prev和next都是null first = newNode; else //链表不为空，将之前存储的原链表尾部节点的next指向新增节点 l.next = newNode; //节点数加1 size++; modCount++; }

这里只介绍add(E e)，addFirst(E e)，addLast(E e)和 实现类似。

将元素插入指定位置 public void add(int index, E element) { //判断索引是否越界 checkPositionIndex(index); if (index == size) //如果索引值等于链表大小，则直接在链尾添加元素 linkLast(element); else linkBefore(element, node(index)); } //根据索引获取节点，因为是链表，不像数组，在内存中并不是一块连续的位置存储，不能根据索引直接取到值，需要从头部或者尾部一个个向下找 Node<E> node(int index) { //size >> 1表示移位，指除以2的1次方 if (index < (size >> 1)) {//如果索引比链表的一半小 Node<E> x = first;//设x为头节点,表示从头节点开始遍历 for (int i = 0; i < index; i++)//因为只需要找到index处，所以遍历到index处就可以停止 x = x.next;//从第一个节点开始向后移动，直到移动到index前一个节点就能找到index处的节点 return x; } else {//如果索引比链表的一半大 Node<E> x = last;//设x为尾部节点,表示从最后一格节点开始遍历 for (int i = size - 1; i > index; i--) x = x.prev;//从最后一个节点开始向前移动，直到移动到index后一个节点就能找到index处的节点 return x; } } void linkBefore(E e, Node<E> succ) { //获取index 节点的上一个节点 final Node<E> pred = succ.prev; //新增一个节点，prev指向pred,e为新加元素，next指向succ节点 final Node<E> newNode = new Node<>(pred, e, succ); //succ的prev指向新节点 succ.prev = newNode; //如果插入节点的上一个节点引用为空 if (pred == null) //头部节点设为新节点 first = newNode; else //原始index的上一个节点的next 设为新节点 pred.next = newNode; //链表长度+1 size++; modCount++; }

4.修改元素

public E set(int index, E element) { //判断索引是否越界 checkElementIndex(index); Node<E> x = node(index);//获取指定索引处的节点 E oldVal = x.item;//获取指定索引处节点的实际元素 x.item = element;//将指定位置的节点元素替换成需要修改的元素 return oldVal;//返回索引处原来的节点的元素值 }

5.查找元素

public E get(int index) { //判断索引是否越界 return index >= 0 && index <= size; checkElementIndex(index); //node(index)上面已经讲过，这里获取节点的实际元素 return node(index).item; }

返回链表中第一个出现指定元素的索引

public int indexOf(Object o) { int index = 0; if (o == null) {//查找的元素为null for (Node<E> x = first; x != null; x = x.next) {//从头结点开始不断向下一个节点进行遍历 if (x.item == null) return index;//找到了则返回index index++; } } else {//查找的元素不为null for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item))//使用equals 比较 return index;//找到了则返回index index++; } } return -1;//找不到指定元素，则返回-1 }

6.删除元素

public E remove(int index) { checkElementIndex(index); //先获取指定位置的节点 return unlink(node(index)); } E unlink(Node<E> x) { final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) {//如果删除节点的上一个节点引用为null，表示删除节点为头节点 first = next;//将头节点设置为删除节点的下一个节点 } else { prev.next = next;//将删除节点的上一个节点的next指向删除节点的下一个节点 x.prev = null;//将删除节点的上一个节点引用设为null，否则链表就乱了 } if (next == null) {//如果删除节点的下一个节点引用为null,表示删除节点为尾部节点 last = prev;//将尾部节点设为删除节点的上一个节点 } else {//不是尾部节点 next.prev = prev;//将删除节点的下一个节点的prev指向删除节点的上一个节点 x.next = null;//将删除节点的下一个节点引用设为null } x.item = null;//将删除节点的实际元素设为null,便于垃圾回收 size--; modCount++; return element; }