LinkedList分析

发表于 | 更新于 | 分类于 ， | 阅读次数：
本文字数： 2.2k | 阅读时长 ≈ 2 分钟

LinkedList 底层是基于双向链表 Deque 实现的，也是实现了 List 接口，所以也拥有 List 的一些特点，出场率不高，了解一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

即类似如下形式：

first.prev == null && first.next == a <——> a.prev = first&& a.next == last <——> last.prev == a && last.next == null

add

每次插入都是移动指针，和 ArrayList 的拷贝数组相比效率提升不少。

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
26
/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
/**
 * Links e as last element.
 */
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++;
}

get

利用了双向链表的特性，使用空间来换取时间。如果索引值小于链表大小的一半，即 index 离链表头比较近，就从节点头部遍历，否则将从尾结点开始遍历。这就导致效率降低，特别是当 index 越接近 size 的中间值时。

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
26
27
28
/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
/**
 * Returns the (non-null) Node at the specified element index.
 */
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;
    }
}

总结

  • LinkedList 插入，删除都是移动指针效率很高。
  • 查找需要进行遍历查询，效率较低。