LinkedList源码解析


1.继承的父类与实现的接口

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

2.类的属性

transient int size = 0;

transient Node<E> first;

transient Node<E> last;

在LinkedList中,定义了如上三个属性。
int size:集合的元素数量
Node<E> first:链表的头元素
Node<E> last:链表的尾元素

3.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的内部类,用以表示一个链表节点。
E item:当前元素
Node<E> next:下一个元素
Node<E> prev:上一个元素
Node(Node<E> prev, E element, Node<E> next):唯一构造函数。每创建一个节点,必须带有前一个节点

4.类的构造函数

public LinkedList() {}

LinkedList():无参构造函数。

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

LinkedList(Collection<? extends E> c):有参构造函数,参数类型为Collection<? extend E>。
由上代码可见,有参构造函数,其实是调用了无参构造函数,以及类中的addAll(Collection)方法,将参数传递进去。

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

而addAll(Collection)方法,内部又是调用了addAll(int,Collection)方法。

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);  //校验index是否下标越界。

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)  //没有添加新的元素,返回false
        return false;

    Node<E> pred, succ;  //建立前节点,后节点
    if (index == size) {  //index==size,说明是在当前集合的末尾插入新数据,因此没有后节点,succ=null,前节点为当前集合的最后一个节点pred=last
        succ = null;
        pred = last;
    } else {
        succ = node(index);  //找到当前下标指代的节点,要在该节点前插入数据,因此令succ等于该节点。
        pred = succ.prev;  //pred则等于succ前面一位的节点。需要注意当index=0时,该点可以为null。
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;  //强制类型转换Object转为E
        Node<E> newNode = new Node<>(pred, e, null);  //创建一个新的节点,节点元素为e,前节点为pred,后节点为null。
        if (pred == null)  //说明index=0,因此新插入的集合的第一个元素,作为first
            first = newNode;
        else
            pred.next = newNode;  //说明index<>0,因此新的节点,作为前节点的后节点(pred.next)
        pred = newNode;  //令当前节点作为前节点,获取下一个元素,循环。
    }

    if (succ == null) {  //说明是从当前集合的末尾开始插入数据,因此数据的最后一个元素,作为当前集合的last
        last = pred;
    } else {  //pred为新插入的最后一个数据,令其的后节点等于之前拆开位置的后节点,succ为之前拆开位置的前节点,令其前节点prev等于新插入的元素的最后一个数据。
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;  //新插入numNew条数据,size增加相应的大小。
    modCount++;
    return true;
}

在addAll(int,Collection)方法中,首先执行checkPositionIndex(int)检验index的合法性(是否在当前对象的size范围内)。

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

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

5.总结

LinkedList重点在于对内部类Node<E>的理解。

每一个元素在LinkedList中都是在Node<E>中存储,每个Node<E>中同时还存储了当前元素的前节点和后节点。

新增元素或集合,只要找到添加的位置,获取该位置的前节点pred,和后节点succ,令pred.next=新插入集合的第一个元素节点,令succ.pred=新插入的集合的最后一个元素节点即可。

删除元素或集合,找到删除的位置,获取该位置的前节点pred,和后节点succ,令pred.next=succ.pred即可。

注意不论是新增还是删除,均要考虑到起始节点没有pred和结束节点没有next的问题。

每一个LinkedList对象中均只存了first和last两个节点,因此当根据索引寻找元素时,代码会判断索引是在前半部分还是后半部分,从而决定从first出发,还是从last出发。

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

声明:半夏有你|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - LinkedList源码解析


年轻的心,是被梦想撑大的