[TOC]
LinkedList 源码分析
1. 链表介绍
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
双链表是链表的一种，由节点组成，每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
LinkedList 底层就是双链表。
2. 源码分析
构造方法
// 无参构造方法
public LinkedList() {
}
// 传入集合构造方法
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
插入方法
// 插入元素
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
// new Node = l(前继节点), e(新创建节点), null(后继节点)
final Node<E> newNode = new Node<>(l, e, null);
// 设置新节点是为尾节点
last = newNode;
// 判断链表是否有元素节点
if (l == null)
first = newNode;
else
// 设置原尾节点的后继节点是 newNode
l.next = newNode;
size++;
modCount++;
}
// 指定元素位置插入
public void add(int index, E element) {
// 检测 index 值是否合法
checkPositionIndex(index);
// index 是不是尾部位置
if (index == size)
// 直接添加到尾节点
linkLast(element);
else
// element 要插入节点
// node(index) 原 index 位置节点
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// 原 index 的前继节点 pred
final Node<E> pred = succ.prev;
// newNode = pred <-- e --> succ
final Node<E> newNode = new Node<>(pred, e, succ);
// 修改原 succ 节点的前继节点是 newNode
succ.prev = newNode;
if (pred == null)
first = newNode;
else
// 修改 pred 节点的指针，指向 newNode 节点
pred.next = newNode;
size++;
modCount++;
}
删除方法
// 删除指定下标元素
public E remove(int index) {
// 检测 index 值是否合法
checkElementIndex(index);
// node(index) 获取 index 位置的元素
return unlink(node(index));
}
// 获取 index 位置的元素节点
Node<E> node(int index) {
// 如果 index 小于 （元素 size 的 / 2）
if (index < (size >> 1)) {
// 从前往后找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 从后往前找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
// 删除元素
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
// 解链操作
E unlink(Node<E> x) {
// x 要删除节点
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 删除节点的前继节点=null
if (prev == null) {
// 头部指向 x 删除节点的后继节点
first = next;
} else {
// 删除元素的前继节点 --> 删除元素的后继节点
prev.next = next;
// 清空删除节点x的前继指向
x.prev = null;
}
// 删除节点的后继节点=null
if (next == null) {
// 尾部指向删除节点的前继节点
last = prev;
} else {
// (prev) <-- (next)
// x --> (next) null
// 删除节点的后继节点，指向删除节点的前继节点
next.prev = prev;
// 清空删除节点x的后继指向
x.next = null;
}
// 清空 x 节点
x.item = null;
size--;
modCount++;
// 返回删除元素
return element;
}
查找方法
// 查找指定下标元素节点
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 获取 index 位置的元素节点
Node<E> node(int index) {
// 如果 index 小于 （元素 size 的 / 2）
if (index < (size >> 1)) {
// 从前往后找
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
// 从后往前找
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
遍历
使用迭代器。
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
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();
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)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
3. ArrayList 和 LinkedList 同时进行查找和插入操作，ArrayList 效率高
举个例子：
public class Test {
public static void main(String[] args) {
long start = System.currentTimeMillis();
// List<String> list = new ArrayList<>();
List<String> list = new LinkedList<>();
int times = 100000;
for (int i = 0; i < times; i++) {
list.add(i + "");
}
for (int i = 0; i < times; i++) {
list.get(i);
}
System.out.println("use = " + (System.currentTimeMillis() - start));
}
}
运行出来的结果是：
ArrayList 62 毫秒
LinkedList 24019 毫秒
ArrayList 比 LinkedList 快很多。
原因：
因为在上述代码中我们没有指定 ArrayList 添加元素时的插入位置，默认往数组尾部插入，这样就没有那么多 System.arraycopy(elementData, index, elementData, index + 1, size - index); 数组 copy 操作，这样就没有那么耗时。
