LinkedList 源码分析

JavaSE
,

TOP 带着问题看源码

  1. LinkedList 采用的数据结构是什么

1. 继承和实现关系

img

  • AbstractSequentialList 实现类

    提供一些围绕着iterator的基础方法

  • List 接口

    提供 list 功能

  • Deque 接口

    提供双端操作功能，以此可以猜出 LinkedList 数据结构是一个双向链表

  • Cloneable 接口

    标记该类对象能够被Object.clone()

  • Serializable 接口

    标记该类是可序列化的

2. 成员变量分析

1
2
3
4
5
6
// 容量
transient int size = 0;
// 首节点
transient Node<E> first;
// 尾节点
transient Node<E> last;

接下来看节点 Node的成员变量

1
2
3
4
5
6
// 节点的值
E item;
// next 指针
Node<E> next;
// prev 指针
Node<E> prev;

回到 TOP 1 问题，根据实现可以明白其数据结构是一个双向链表

3. 构造方法分析

一个是默认无参，一个是带集合内容的。

把传来的集合新增入当前list

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

接下来看节点 Node的构造方法，根据入参默认维护两个指针。

1
2
3
4
5
Node(Node<E> prev, E element, Node<E> next) {
    this.item = element;
    this.next = next;
    this.prev = prev;
}

4. 核心方法分析

4.1 获取元素

先check，然后通过 node(index)方法取

1
2
3
4
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

node 方法通过判断索引 index 的范围(若是大于一半集合容量，则从尾结点向前遍历，若小于则从头结点向后遍历)来尽量高效的取到对应的节点

4.2 新增元素

4.2.1 add(E e)

尾插

1
2
3
4
public boolean add(E e) {
    linkLast(e);
    return true;
}

构建一个next指针是null，prev指针是尾结点的新节点newNode，如果尾结点不为空则将尾结点的next结点指向newNode，否则将头结点指向newNode

1
2
3
4
5
6
7
8
9
10
11
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++;
}

4.2.2 add(int index, E element)

先check，如果插入的还是尾部，则调用 linkLast 方法，否则先获取到索引 index 对应的节点然后调用 linkBefore 方法

1
2
3
4
5
6
7
8
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

构建一个 prev 指针是索引 index - 1 对应节点，next节点是索引 index 对应节点的新节点newNode **(图中绿色部分)**。然后把index节点的prev指向newNode (图中蓝色部分)，如果要插入的是第一个位置，则把 first 指针指向newNode，否则维护剩余的指针关系(index - 1 节点的next指向newNode)(图中红色部分)

img

4.3 更新元素

根据下标位置获取节点，然后把节点的值进行覆盖

1
2
3
4
5
6
7
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

4.4 删除元素

4.4.1 remove(int index)

先check，然后先获取index对应节点最后调用unlink方法

1
2
3
4
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

同按照下标新增那块逻辑差不多，去除一个节点(prev next item置null)，重新维护指针关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
}

4.4.2 remove(Object o)

遍历要找的元素的index，然后调用unlink方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

4.4.3 clear()

遍历赋值null，size重置为0