Java LinkedList源码浅析

简介

LinkedList是一种双向链表数据结构，每个节点维护了自身的数据及前后节点的指针。

链表

链表是由一系列非连续节点组成的数据结构。链表分为担心链表、双向链表。又可以分别循环链表和非循环链表。

1. 单向链表。每个节点有一个指向下一个节点的指针next，最后一个节点next指向null。如图1所示
2. 单向循环链表。单向循环链表和单向链表唯一不同的是最后一个节点的next指向head，形成一个“环”。如图2所示
3. 双向链表。双向两边每个节点包含两个指针，prev指向前一个节点，next指向下一个节点，第一个节点的prev指向null，最后一个节点的next指向null。如图3所示
4. 双向循环链表。双向循环链表与双向链表不同的是第一个节点的prev指针指向最后一个节点（tail），最后一个节点（tail）的next指针指向第一个节点（head），形成双向的“环”。如图4所示
   

LinkedListUML图

LinkedList 定义

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

LinkedList属性

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

内部类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);
}

方法摘要

返回类型	方法名称	描述
boolean	add(E e)	增加指定的元素
void	add(int, index, E e)	在指定位置元素
boolean	addAll(Collection<? extends E> c)	增加指定集合的所有元素
boolean	addAll(int index, Collection<? extends E> c)	在指定位置开始增加集合的所有元素
void	addFirst(E e)	在表头插入
void	addLast(E e)	在表尾插入
void	clear()	清空所有元素
Object	clone()	克隆副本
boolean	contains(Object o)	判断是否包含指定的元素。如存在返回true，否则返回false
Iterator	descendingIterator()	返回一个从队尾到队头的反向迭代器
E	get(int index)	返回指定位置的元素
E	getFirst()	返回第一个元素（队头）
E	getLast()	返回最后一个元素（队尾）
int	indexOf(Object o)	返回列表中首次出现指定元素的位置，不存在返回-1
int	lastIndexOf(Object o)	返回列表中最后一次出现指定元素的位置，不存在返回-1
boolean	offer(E e)	同add
boolean	offerFirst(E e)	同addFirst
boolean	offerLast(E e)	同addLast
E	peek()	和getFirst类似，唯一的区别是getFirst时first存在抛出NoSuchElementException，peek时first不存在返回null
E	peekFirst()
E	peekLast()
E	poll()	表头出队（返回表头元素并删除表头）
E	pollFirst()	同poll
E	pollLast()	表尾出队（返回表尾元素并删除表尾）
E	pop()	同removeFirst()
void	push(E e)	同addFirst(E e)
E	remove()	同removeFirst()
E	remove(int index)	删除指定位置元素
boolean	remove(Object o)	删除指定的元素
E	removeFirst()	表头出队（返回表头元素并删除表头），表头为空抛出NoSuchElementException
E	removeLast()	表尾出队（返回表尾元素并删除表尾）.表尾为空抛出NoSuchElementException
E	set(int index, E e)	用指定的元素替换列表中指定位置的元素
int	size()	返回集合元素大小
Object[]	toArray()
T []	toArray(T [])
void	trimToSize()	容量调整为当前元素大小

核心源码（基于1.8）

增加元素

public boolean add(E e) {
    // 连接到队尾
    linkLast(e);
    return true;
}
void linkLast(E e) {
    // 列表原队尾节
    final Node<E> l = last;
    // 创建包含元素e的节点newNode
    final Node<E> newNode = new Node<>(l, e, null);
    // 队尾指向newNode
    last = newNode;
    // 如果列表原队尾节为空，则把对头节点也指向newNode。否则把原队尾节点的下一个节点指向newNode
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

/**
 * 指定位置插入
 */
public void add(int index, E element) {
    // 下标检查
    checkPositionIndex(index);
    if (index == size)
        // 插入到队尾
        linkLast(element);
    else
        // 队尾之前插入
        linkBefore(element, node(index));
}
/**
 * 查找index位置的节点
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果 index < size/2 (size >> 1即一除以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;
    }
}
/**
 * succ节点之前插入元素
 */
void linkBefore(E e, Node<E> succ) {
    // 原index位置前一个节点pred
    final Node<E> pred = succ.prev;
    // 创建包含元素e的节点newNode
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 修改succ.prev指向
    succ.prev = newNode;
    // 如果pred为空，即插入到队头。否则succ前一个节点的下一个节点（pred.next）指向newNode
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}
/**
 * 将集合中所有元素插入到列表
 */
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;
    // index位置前节点pred及index位置前节
    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;
    }
    // 如果队尾插入，last指向pred(即最后一个元素节点)
    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}
/**
 * 队头插入
 */
public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}
/**
 * 队尾插入
 */
public void addLast(E e) {
    linkLast(e);
}
public void push(E e) {
    addFirst(e);
}
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

获取元素

public E get(int index) {
    // 下标检查
    checkElementIndex(index);
    // 迭代查找
    return node(index).item;
}
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
public E element() {
    return getFirst();
}
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}
public E pop() {
    return removeFirst();
}
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}
/**
 * 解开非空节点x
 */
E unlink(Node<E> x) {
    // 取出节点元素
    final E element = x.item;
    // 取出next指针
    final Node<E> next = x.next;
    // 取出prev指针
    final Node<E> prev = x.prev;
    // 如果prev为空，即unlink节点是表头
    if (prev == null) {
        first = next;
    } else {
        // prev.next下移
        prev.next = next;
        // 置空
        x.prev = null;
    }
    // 如果next为空，即unlink的是表尾节点
    if (next == null) {
        last = prev;
    } else {
        // next.prev前移
        next.prev = prev;
        x.next = null;
    }
    // 置空，帮助gc
    x.item = null;
    // 实际元素-1
    size--;
    modCount++;
    return element;
}

删除元素

public E remove() {
    return removeFirst();
}
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;
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

查找

public E get(int index) {
    // 下标检查
    checkElementIndex(index);
    return node(index).item;
}

更新

public E set(int index, E element) {
    checkElementIndex(index);
    // 查找节点
    Node<E> x = node(index);
    // 取出旧值
    E oldVal = x.item;
    // 修改值
    x.item = element;
    // 返回旧值
    return oldVal;
}

总结

1. 顺序插入ArrayList较快（不涉及扩容的情况下）。因为LinkedList需要new节点，ArrayList是基于数组的，直接赋值即可
2. LinkedList是一个双向链表，不仅维护元素本身，还维护了前置和后继，内存消耗上大于ArrayList
3. ArrayList遍历速度高于LinkedList
4. 插入/删除：在队头/队尾插入/删除删除较快，在中间插入因为需要整个列表寻找，所以较慢（越往后插入/删除需要寻址次数越多）

---

本系列文章是为团队内部分享参考网络资料及个人理解整理而成