LinkedList详解
LinkedList是List接口的一个主要的实现类之一，基于链表的实现。以java8为例来了解一下LinkedList的源码实现
继承关系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
继承了AbstractSequentialList，实现了List接口、Deque接口、Cloneable接口、Serializable接口
关键变量
/**
* 链表的长度
*/
transient int size = 0;
/**
* 头节点
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* 尾结点
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
// 这里用到了一个内部类Node，看到Node的结构就知道是一个双向链表了，保存了前驱节点和后继节点
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;
}
}
构造器
// 无参默认构造器
public LinkedList() {
}
/**
* 传入一个集合作为参数
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
// 检查是否越界
checkPositionIndex(index);
Object[] a = c.toArray();
// 新增元素的数量
int numNew = a.length;
if (numNew == 0)
return false;
// 前置节点和后置节点
Node<E> pred, succ;
// index == size时表示是从链表尾部添加元素，所以前置节点为当前链表的尾结点
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);
// 前置节点为null，表示这是头节点
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// succ == null,说明是从尾部添加的，将最后一个节点赋给尾结点
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
// 获取index位置的节点
Node<E> node(int index) {
// assert isElementIndex(index);
// index小于链表长度的一半，从链表头部开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // index不小于链表长度的一半，从链表尾部开始遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
add方法
// 逻辑比较简单，与上边addAll类似，一通插
public void add(int index, E element) {
checkPositionIndex(index);
// index == size表示在链表尾部添加
if (index == size)
linkLast(element);
else // 否则在中间插入 先找到index所在位置的节点
linkBefore(element, node(index));
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
remove方法
LinkedList的remove方法比较
public E remove(int index) {
// 检测该索引位置是否符合要求 index >= 0 && index < size
checkElementIndex(index);
return unlink(node(index));
}
// 找到当前索引位置的节点
Node<E> node(int index) {
// assert isElementIndex(index);
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;
}
}
E unlink(Node<E> x) {
// assert x != null;
// 所要删除的元素
final E element = x.item;
// 所要删除的元素的后继节点
final Node<E> next = x.next;
// 所要删除的元素前驱结点
final Node<E> prev = x.prev;
// 前驱节点为null，表示为头节点，头节点指向后继节点即可
if (prev == null) {
first = next;
} else {
// 前驱节点的后继节点指向该元素的后继节点
prev.next = next;
x.prev = null;
}
// 后继节点为null，表示为尾节点，尾节点指向前驱节点即可
if (next == null) {
last = prev;
} else {
// 后继节点的前驱节点指向该元素的前驱节点
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
迭代器
LinkedList使用的迭代器是其父类AbstractSequentialList中的iterator方法，其迭代器是双向的，可以正向也可以反向
// AbstractSequentialList类方法
public Iterator<E> iterator() {
return listIterator();
}
// LinkedList类方法
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
// 与ArrayList的迭代器不同的是，ArrayList的迭代器实现的是Iterator接口 而LinkedList为ListIterator接口，相当于ArrayList的listIterator()方法
// Iterator只能向前遍历，ListIterator可以向前也可以向后
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;
nextIndex++;
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();
}
