Java容器框架分析(三)——LinkedList源码分析

2017/2/23 posted in  Java  

LinkedList简介

LinkedList同时实现了List接口和Deque接口,所以它可以看作一个顺序容器,又可以看作是一个队列(Queue),同时又可以看作为一个栈(Stack)。所以当你需要使用栈和队列时,可以考虑使用LinkedList,一方面是因为Java官方文档已经声明不建议使用Stack类,而且Java也没有官方的Queue的实现类。关于栈或者队列,现在的首选是ArrayDeque,当作为栈或者队列使用时,它具有更好的性能(相比LinkedList)。
LinkedList的底层通过双向链表作为基础数据结构进行实现。本节将对LinkedList作为线性顺序容器的维护过程予以说明。
双向列表的每个节点用内部类Node表示。LinkedList通过其firstlast引用分别指向链表的第一个和最后一个元素。当链表为空时,firstlast引用均为null

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

LinkedList示意图

鉴于LinkedList的实现方式,所有和下标有关的操作的时间复杂度都是线性的。而在末尾或首部删除元素仅需要常数时间。为追求效率LinkedList没有实现同步,如果需要多个线程并发访问,可以采用Collections.synchronizedList()对其进行包装。

常用方法剖析

add()

add()方法有两个版本,一个是add(E e),该方法在LinkedList的末尾插入元素,因为有last指向链表末尾,在末尾插入元素的花费是常数时间。只需要几个简单的修改几个相关引用即可;另一个是add(int index,E e),该方法是在指定位置插入元素,需要先通过线性查找找到具体位置,然后修改相关引用完成插入操作。
add方法示意

如上图,可以看出add(E e)的逻辑非常简单,代码如下:

public boolean add(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++;
    return true;
}

add(int index,E e)的逻辑相比就复杂一些,可以分成两个部分:先根据index找到需要插入的位置;再修改对应的引用,完成插入操作。代码如下:

public void add(int index, E element) {
     //位置越界检查index >= 0 && index <= size;
    checkPositionIndex(index);
    if (index == size)//插入位置是末尾,包括列表为空的情况
        add(element);
    else{
        Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用,完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

其中node函数的实现有一些小技巧,因为链表是双向的,所以可以从前往后也可以从后往前,具体从那边开始就取决于index< (size >> 1)即index是靠近前端还是后端。

remove()

remove()方法也有两个版本:remove(Object o)删除第一个和对应元素相同的元素;remove(int index)删除指定位置的元素。
两个删除操作都需要:先找到对应的目标元素在修改相关引用,完成删除操作。在寻找被删除元素引用的时候remove(Object o)调用的是元素的equals方法,而remove(int index)使用的是下标计数,两种方式都是线性的时间复杂度。在修改引用过程中,都是通过unlink(Node<E> x)方法完成的,需要特别考虑删除元素是首尾的情况。

E unlink(Node<E> x) {
    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;//let GC work
    size--;
    return element;
}

get()

get(int index)得到指定下标处元素的引用,通过调用上文中提到的node(int index)方法实现。

public E get(int index) {
    //检测index是否越界
    checkElementIndex(index);
    return node(index).item;
}

set()

set(int index,E e)方法将指定下标处的元素修改成指定值,也是先通过node(int index)方法找到对应下标的元素的引用,然后修改Node中的item值。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}

声明

本系列博文装载自:https://github.com/CarpenterLee/JCFInternals
作者:CarpenterLee