Dive into LinkedList


 

Dive into LinkedList

LinkedList源码阅读与分析

一. 概述

LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。 LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。 LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。 LinkedList 是非同步的。

二. 基本属性

其中 size 为 LinkedList 的大小,first 和 last 分别为链表的头结点和尾结点。Node 为结点对象。

// 表中已有元素个数
transient int size = 0;

// 头结点指针
transient Node<E> first;

// 尾结点指针
transient Node<E> last;

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

三. 构造器

LinkedList中包含两个构造方法,一个空的构造构建空链表,另一个用传入的Collection构建一个含有元素的链表。

// 构造一个空的链表,size=0,first=null,last=null
public LinkedList() {
}

/**
 * 构建一个list,将Collection中的元素以它们的迭代器返回的顺序添加进去
 * 如果c为空将抛出 NullPointerException
 */
public LinkedList(Collection<? extends E> c) {
    // 构造一个空的链表
    this();
    // 将 c 中的所有元素添加进链表
    addAll(c);
}

看一眼 addAll 方法的逻辑,发现继续调用另一个addAll的重载方法,传入size(为0)和 Collection 实现类对象

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

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

    // 将 collection 转换成数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // //如果需要新增元素数量为0,则不增加,并返回false
    if (numNew == 0)
        return false;

    // index节点的前置节点,后置节点
    Node<E> pred, succ;	
    // 从表尾添加
    if (index == size) {
        // size节点(队尾)的后置节点一定是null
        succ = null;
        // 前置节点是队尾
        pred = last;
    } else {
        // index结点作为插入新增结点的后置结点
        succ = node(index);
        // 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 的值
    size += numNew;

    //结构性修改次数加一
    modCount++;
    return true;
}

四. 添加元素

1. 在表尾追加元素

public boolean add(E e) {
    linkLast(e);
    return true;
} 	

add 方法直接调用了 linkLast方法,而linkLast方法是不对外开放的。该方法做了三件事情,新增一个节点,改变其前后引用,将 size 和 modCount 自增 1。其中 modCount 是记录对集合操作的次数。

// 在表尾追加元素
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++;
}

2.. 在表头插入元素

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

3. 在指定结点前插入

// 在一个非空结点 succ 前面插入一个新的元素值为e的结点
void linkBefore(E e, Node<E> succ) {
    // 获取到要插入位置的前一个结点
    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++;
}

4. 在指定索引处插入元素

将element插入到index前

public void add(int index, E element) {
    // 索引越界检查
    checkPositionIndex(index);

    // 索引为表大小,插入表尾
    if (index == size)
        linkLast(element);
    else
        // 先获取index处的结点,再将element插入到它前面
        linkBefore(element, node(index));
}

索引越界检查

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 判断该参数对于迭代和添加元素操作而言是否一个合法的索引
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

获取指定位置的结点

因为是链表操作,显然会比数组的获取操作复杂得多 ,下面采用简单的分治思想

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 {
        // 复制尾结点
        Node<E> x = last;
        // 从表尾开始迭代定位
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}	

// 判断参数是否表中元素的索引
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

五. 删除元素

1. 删除表头元素

public E removeFirst() {
    // 判空
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    // 真正的删除逻辑
    return unlinkFirst(f);
}

// 删除非空的头结点,调用该方法前需要确保  f == first && f != null;
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 获取结点元素
    final E element = f.item;
    // 下一个结点
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    // 修改头结点指向源头结点的下一个结点
    first = next;
    // 原表中只有一个元素
    if (next == null)
        last = null;
    // 新的头结点的前一个结点为空
    else
        next.prev = null;
    size--;
    modCount++;
    // 返回被删除的头结点
    return element;
}

2. 删除表尾元素

public E removeLast() {
    final Node<E> l = last;
    // 判空
    if (l == null)
        throw new NoSuchElementException();
    // 真正的删除逻辑
    return unlinkLast(l);
}

// 删除非空的尾结点,调用该方法前需要确保 l == last && l != null;
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    // 获取表尾元素
    final E element = l.item;
    // 获取尾结点的前一个结点
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    // 将原来的尾结点的前一个结点作为新的尾节点
    last = prev;
    // 原表只有一个元素
    if (prev == null)
        first = null;
    // 将新的尾节点的下一个结点置空
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

3. 删除特定的元素

删除表中第一个出现的给定元素,如果它存在的话,不存在则没有动作

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

// 删除指定的非空结点,调用该方法前需要确保 x != null;
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;

    // 要删除的是头结点
    if (prev == null) {
        first = next;
        // 将要删除的结点的下一个结点指向要删除元素后一个结点
    } else {
        // 处理前一个结点
        prev.next = next;
        x.prev = null;
    }

    // 要删除的是尾结点
    if (next == null) {
        last = prev;
    } else {
        // 处理后一个结点
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

六. 获取元素

1. 获取表头元素

public E getFirst() {
    // 复制头指针引用
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

2. 获取表尾元素

public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

七. 清空表

清空链表看似没有必要,不过这样做可以帮助垃圾收集

/** 
 * Clearing all of the links between nodes is "unnecessary", but
 * helps a generational GC if the discarded nodes inhabit
 *  more than one generation
 *	is sure to free memory even if there is a reachable Iterator
 */  	
public void clear() {
    for (Node<E> x = first; x != null; ) {
        // 获取当前结点的下一个结点
        Node<E> next = x.next;
        // 置空数据
        x.item = null;
        x.next = null;
        x.prev = null;
        // 指向下一个结点
        x = next;
    }
    // 置空头尾结点
    first = last = null;
    size = 0;
    modCount++;
}

八. 问题

1. local final

为什么很多方法设计到对头尾指针的操作时,都是先将这些指针复制到本地并声明为final

定义成本地变量的原因

  • 使用虚拟机栈上的引用比使用堆上的引用要快。所以建议这样做,尤其是当你在方法中多次使用该引用时。
  • 在多线程访问的情况有些操作可能会报空指针异常

用fianl修饰的原因

  • 将成员变量复制成本地成员能稍微简化字节码,从宏观上来看使得编码更接近机器本身
  • 虚拟机会对final变量进行一些优化