Java容器源码LinkedList原理解析

LinkedList简介

LinkedList是一个使用双向链表结构实现的容器，与ArrayList一样，它能动态扩充其长度，LinkedList相较于ArrayList，其任意位置插入速度比ArrayList要快，但是其查询速度要比ArrayList要慢；LinkedList继承自AbstractSequentialList，实现了List、Deque、Cloneable、Serializable接口。

LinkedList UML图如下：

和ArrayList一样，LinkedList也不是一个线程安全的容器。

LinkedList源码分析

构造方法

LinkedList有两个构造方法：

public LinkedList() {
}

//从已有的一个容器创建一个LinkedList对象
public LinkedList(Collection<? extends E> c) {
 this();
 addAll(c);
}

addAll()方法：

public boolean addAll(Collection<? extends E> c) {
 return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
 //检查index是否溢出
 checkPositionIndex(index);

Object[] a = c.toArray();
 int numNew = a.length;
 if (numNew == 0)
   return false;
 //获取第index位置的node元素和node的前一个元素
 //succ：第index位置的node元素
 //pred：index位置前一个node元素
 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;
 modCount++;
 return true;
}

add方法

LinkedList也有两个add方法，如下：

public boolean add(E e) {
 //添加元素到队尾
 linkLast(e);
 return true;
}

public void add(int index, E element) {
 //检查index是否溢出
 checkPositionIndex(index);

if (index == size)
   //index == size，直接添加到队尾
   linkLast(element);
 else
   //index != size，添加元素到index位置
   linkBefore(element, node(index));
}

linkLast方法：

void linkLast(E e) {
 final Node<E> l = last;
 //新建一个node，将其前一个元素指针指向原链表的最后一个元素
 final Node<E> newNode = new Node<>(l, e, null);
 //更新尾指针
 last = newNode;
 if (l == null)
   //若原last==null说明此时链表就一个元素
   first = newNode;
 else
   //更新原链表尾元素指针
   l.next = newNode;
 size++;
 modCount++;
}

linkBefore方法：

void linkBefore(E e, Node<E> succ) {
 // assert succ != null;
 //获取指定位node元素的前一个元素pred
 final Node<E> pred = succ.prev;
 //新建一个node，将其前指针指向pred元素
 final Node<E> newNode = new Node<>(pred, e, succ);
 //将指定位置的node元素的前指针指向新元素，完成插入
 succ.prev = newNode;
 if (pred == null)
   first = newNode;
 else
   pred.next = newNode;
 size++;
 modCount++;
}

获取指定位置node指针方法node：

Node<E> node(int index) {
 // assert isElementIndex(index);
 //index > size/2时，说明在链表前半段，从前往后搜索
 if (index < (size >> 1)) {
   Node<E> x = first;
   for (int i = 0; i < index; i++)
     x = x.next;
   return x;
 //index < size/2时，从后往前搜索
 } else {
   Node<E> x = last;
   for (int i = size - 1; i > index; i--)
     x = x.prev;
   return x;
 }
}

get方法也比较简单，首先检测index是否溢出，然后直接找到index位置的元素，并返回其item。

来源：https://www.cnblogs.com/Sirius-/p/13934542.html