LinkedList源码分析

小管
源码

发布于：Apr 23, 2021
次浏览

3.4k words

15 min
0  

LinkedList特性

LinkedList内部使用双向链表作为存储结构,LinkedLIst可以理解为链表的扩展对象,简单封装了常用和非常用的操作链表的方法,以及在通过索引获取元素时的简单优化.LinkedList的特点如下：

  • 根据索引在链表中检索数据的时间复杂度时O(n).
  • 在链表的头部和尾部写入或删除元素效率高
  • 实现了List和Duque的全部功能,可以把它当作一个集合或队列使用
  • 链表中允许保存NULL
  • 链表是非线程安全

源码

重要成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//链表中元素的数量
transient int size = 0;
///链表头节点
transient Node<E> first;
//链表尾节点
transient Node<E> last;

// 链表元素的定义
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;
    }
}

Node的数据结构是一个双向链表

构造函数

1
2
3
4
5
6
7
8
9
//默认构造函数
public LinkedList(){
}

//根据哟个Collection初始化链表
public LinkedList(Collection<? entends E> c){
  this();
  addAll(c);
}

常用方法

add、addFirst与addLast

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 在链表头部添加元素
public void addFirst(E e) {
  linkFirst(e);
}
// 在链表尾部添加元素
public void addLast(E e) {
  linkLast(e);
}
// 添加方法，默认添加到尾部
public boolean add(E e) {
  linkLast(e);
  return true;
}

private void linkFirst(E e) {
  // 添加e之前的第一个元素
  final Node<E> f = first;
  // 创建一个node节点，prev=null,next=f
  final Node<E> newNode = new Node<>(null, e, f);
  first = newNode;
  // 判断是否是第一个添加到链表中的元素
  // 如果是则last也等于该元素
  // 如果不是，则与f进行关联
  if (f == null)
    last = newNode;
  else
    f.prev = newNode;
  // 长度+1
  size++;
  modCount++;
}

void linkLast(E e) {
  // 添加e之前的最后一个元素
  final Node<E> l = last;
  // 创建一个node节点，prev=l,next=null
  final Node<E> newNode = new Node<>(l, e, null);
  last = newNode;
  // 判断是否是第一个添加到链表中的元素
  // 如果是则first也等于该元素
  // 如果不是，则与l进行关联
  if (l == null)
    first = newNode;
  else
    l.next = newNode;
  // 长度+1
  size++;
  modCount++;
}

add(int index, E element)

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 在指定位置添加元素
public void add(int index, E element) {
  // 判断索引正确
  checkPositionIndex(index);
  // 如果在链表最后面添加，则调用linkLast将元素添加到尾部
  // 否则先通过node(index)获取到元素，然后将element添加到该元素前面
  if (index == size)
    linkLast(element);
  else
    linkBefore(element, node(index));
}

// 索引越界会返回IndexOutOfBoundsException异常
private void checkPositionIndex(int index) {
  if (!isPositionIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// index在0-size之间
private boolean isPositionIndex(int index) {
  return index >= 0 && index <= size;
}

// 根据索引查找Node节点
Node<E> node(int index) {
  // index < (size >> 1)最多只遍历一般的Node节点
  // 如果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;
  }
}

void linkBefore(E e, Node<E> succ) {
  // 涉及到了3个Node的关系
  final Node<E> pred = succ.prev;
  // 创建一个新的Node，prev=[index].prev，next=[index]
  final Node<E> newNode = new Node<>(pred, e, succ);
  // index对应的Node的prev=新Node
  succ.prev = newNode;
  // 判断是否在first位添加了e，如果是，则把first=新Node
  if (pred == null)
    first = newNode;
  // 否则[index-1].next等于新Node
  else
    pred.next = newNode;
  size++;
  modCount++;
}

在指定位置add一个元素,其性能要比在头和尾add一个元素满.

原因在于需要遍历链表,找到index位置的元素,然后将要添加的元素、index位置的元素、以及index-1位置的元素重新建立关系.

源码中的优化:

  • 如果index==size,直接添加到尾部,不进行遍历链表.
  • 遍历时,先判断index在链表的前部还是后部,然后采取从前向后遍历还是从后向前遍历.

addAll

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 从链表尾部添加c中的所有元素，构造函数使用的就是这个addAll
public boolean addAll(Collection<? extends E> c) {
  return addAll(size, c);
}

// 从index位置之后，添加c中的所有元素
public boolean addAll(int index, Collection<? extends E> c) {
  // 检查索引是否越界
  checkPositionIndex(index);
  // 判断c中是否有元素，如果没有则返回false
  Object[] a = c.toArray();
  int numNew = a.length;
  if (numNew == 0)
    return false;

  // 添加c之前的准备工作，准备好上一个node和下一个node
  Node<E> pred, succ;
  if (index == size) {
    // 如果从尾部添加c
    // 则保存last到pred变量，作为要添加节点的上一个Node
    // succ变量为null，从尾部添加没有next
    succ = null;
    pred = last;
  } else {
    // 如果从链表其他部分添加c
    // 则获取index位置的元素，设置位下一个Node
    // pred为index位置的元素的prev
    succ = node(index);
    pred = succ.prev;
  }

  // 循环a数组开始添加到链表
  for (Object o : a) {
    @SuppressWarnings("unchecked") E e = (E) o;
    // 创建要添加的node
    Node<E> newNode = new Node<>(pred, e, null);
    if (pred == null)
      first = newNode; // 是否要更新first变量
    else
      pred.next = newNode; // 添加node到链表
    // 更新上一个node的变量
    pred = newNode;
  }

  if (succ == null) {
    // 如果是从链表尾部添加，则last变量=最后一个node
    last = pred;
  } else {
    // 否则将最后一个添加的node的next设置为succ，succ的prev=最后一个node
    pred.next = succ;
    succ.prev = pred;
  }
  // 更新链表长度
  size += numNew;
  modCount++;
  return true;
}

set(int index, E element)

1
2
3
4
5
6
7
8
9
10
public E set(int index, E element){
  // 验证索引越界
  checkElementIndex(index);
  // 获取指定位置的元素
  Node<E> x = node(index);
  // 更新值，并返回旧值
  E oldVal = x.item;
  x.item = element;
  return oldVal;
}

removeFirst,removeLast

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 删除第一个元素
public E removeFirst() {
  final Node<E> f = first;
  if (f == null)
    throw new NoSuchElementException();
  return unlinkFirst(f);
}

// 删除最后一个元素
public E removeLast() {
  final Node<E> l = last;
  if (l == null)
    throw new NoSuchElementException();
  return unlinkLast(l);
}

private E unlinkFirst(Node<E> f) {
  final E element = f.item;
  // 获取f的下一个元素保存到next变量
  final Node<E> next = f.next;
  // 置空，便于GC回收
  f.item = null;
  f.next = null; // help GC
  // 把first设置成next，并且判断next是否为null
  // 如果next为null，则说明删除了f后，链表中没有元素了，那么把last设置成null
  // 否则，把next的prev设置成null，代表他是第一个元素
  first = next;
  if (next == null)
    last = null;
  else
    next.prev = null;
  // 链表长度-1
  size--;
  modCount++;
  return element;
}

private E unlinkLast(Node<E> l) {
  final E element = l.item;
  // 获取上一个元素保存到prev变量
  final Node<E> prev = l.prev;
  // 置空，便于GC回收
  l.item = null;
  l.prev = null; // help GC
  // 把last设置成prev，并且判断prev是否为null
  // 如果prev为null，则说明删除了l后，链表中没有元素了，那么把first设置成null
  // 否则，把prev的next设置成null，代表他是第最后一个元素
  last = prev;
  if (prev == null)
    first = null;
  else
    prev.next = null;
  // 链表长度-1
  size--;
  modCount++;
  return element;
}

remove(int index)

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
29
30
31
32
33
34
35
36
37
// 删除指定索引位置的元素
public E remove(int index) {
  // 判断索引是否越界
  checkElementIndex(index);
  return unlink(node(index));
}

E unlink(Node<E> x) {

  final E element = x.item;
  final Node<E> next = x.next;
  final Node<E> prev = x.prev;

  // 判断要删除的node是否是第一个node
  // 如果是就更新first变量
  // 否则断开这个node与前一个node的关联关系
  if (prev == null) {
    first = next;
  } else {
    prev.next = next;
    x.prev = null;
  }
  // 判断要删除的node是否是最后一个node
  // 如果是就更新last变量
  // 否则断开这个node与后一个node的关联关系
  if (next == null) {
    last = prev;
  } else {
    next.prev = prev;
    x.next = null;
  }
  // 便于GC
  x.item = null;
  size--;
  modCount++;
  return element;
}

在指定位置删除元素,依旧会遍历找到index对应的元素,然后断开这个元素的前后node.对这个元素是否时头节点和尾节点进行了优化.

remove(Object o)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean remove(Object o) {
  // 判断要删除的元素是否是null，如果是，则用 == null进行判断，然后调用unlink
  if (o == null) {
    for (Node<E> x = first; x != null; x = x.next) {
      if (x.item == null) {
        unlink(x);
        return true;
      }
    }
  } else {
    // 如果不是null，则用item.eq判断，然后调用unlink
    for (Node<E> x = first; x != null; x = x.next) {
      if (o.equals(x.item)) {
        unlink(x);
        return true;
      }
    }
  }
  return false;
}

根据对象删除元素比根据index删除元素的效率可能还要低,因为没办法判断index < (size>>1),就只能从前向后一直遍历.

removeFirstOccurrence和removeLastOccurrence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 从链表前段开始删除元素，其实就是调用的remove(o)，因为remove(o)是正向循环
public boolean removeFirstOccurrence(Object o) {
  return remove(o);
}
// 从链表尾部删除元素，做法与remove(o)相反，是反向循环查找元素
public boolean removeLastOccurrence(Object o) {
  if (o == null) {
    for (Node<E> x = last; x != null; x = x.prev) {
      if (x.item == null) {
        unlink(x);
        return true;
      }
    }
  } else {
    for (Node<E> x = last; x != null; x = x.prev) {
      if (o.equals(x.item)) {
        unlink(x);
        return true;
      }
    }
  }
  return false;
}

这两个方法是JDK1.6提供的,弥补了remove(o)方法无法从链表尾部开始循环带来的极端情况下,时间复杂度为O(n)的问题

clear

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void clear() {
  // 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
  // 循环清空链表
  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，链表长度=0
  first = last = null;
  size = 0;
  modCount++;
}

getFirst,getLast,get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 获取链表的第一个元素，如果为null会抛出异常
public E getFirst() {
  final Node<E> f = first;
  if (f == null)
    throw new NoSuchElementException();
  return f.item;
}

// 获取链表的最后一个元素，如果为null会抛出异常
public E getLast() {
  final Node<E> l = last;
  if (l == null)
    throw new NoSuchElementException();
  return l.item;
}

// 获取指定位置的元素，判断索引是否越界
public E get(int index) {
  checkElementIndex(index);
  return node(index).item;
}

如果这是一个空链表,这两个方法获取元素会抛出异常

注意,代码中判断的是fitst和last,并不是元素的item,所以链表中是可以保存null的.

其他函数

contains
1
2
3
4
public boolean contains(Object o) {
  // 调用indexOf(o)方法
  return indexOf(o) != -1;
}
size
1
2
3
public int size(){
  return size;
}
indexOf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int indexOf(Object o) {
  int index = 0;
  // 为null的判断
  if (o == null) {
    for (Node<E> x = first; x != null; x = x.next) {
      if (x.item == null)
        return index;
      index++;
    }
  } else {
    // 不为空的判断
    for (Node<E> x = first; x != null; x = x.next) {
      if (o.equals(x.item))
        return index;
      index++;
    }
  }
  return -1;
}

从前往后循环,查找匀速出现的第一次索引.

lastIndexOf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 类似indexOf，只不过是从后向前查找
public int lastIndexOf(Object o) {
  int index = size;
  if (o == null) {
    for (Node<E> x = last; x != null; x = x.prev) {
      index--;
      if (x.item == null)
        return index;
    }
  } else {
    for (Node<E> x = last; x != null; x = x.prev) {
      index--;
      if (o.equals(x.item))
        return index;
    }
  }
  return -1;
}

从后往前循环,查找元素出现的最后一次索引.

Deque方法

Linkedlist不仅实现了链表,还实现了Deque(双端队列)接口.

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 返回头元素，不存在返回null
public E peek() {
  final Node<E> f = first;
  return (f == null) ? null : f.item;
}

// 返回头元素，不存在抛出异常
public E element() {
  return getFirst();
}

// 弹出头元素，不存在返回null
public E poll() {
  final Node<E> f = first;
  return (f == null) ? null : unlinkFirst(f);
}

// 弹出头元素，不存在抛出异常
public E remove() {
  return removeFirst();
}

// 添加元素到头部
public boolean offer(E e) {
  return add(e);
}

// 添加元素到头部
public boolean offerFirst(E e) {
  addFirst(e);
  return true;
}

// 添加元素到尾部
public boolean offerLast(E e) {
  addLast(e);
  return true;
}

// 返回头元素，不存在返回null
public E peekFirst() {
  final Node<E> f = first;
  return (f == null) ? null : f.item;
}

// 返回尾元素，不存在返回null
public E peekLast() {
  final Node<E> l = last;
  return (l == null) ? null : l.item;
}

// 弹出头元素，不存在返回null
public E pollFirst() {
  final Node<E> f = first;
  return (f == null) ? null : unlinkFirst(f);
}

// 弹出尾元素，不存在返回null
public E pollLast() {
  final Node<E> l = last;
  return (l == null) ? null : unlinkLast(l);
}

// 添加元素到头部
public void push(E e) {
  addFirst(e);
}

// 弹出头部元素，不存在抛出异常
public E pop() {
  return removeFirst();
}

总结

  • LinkedList内部使用双向链表作为数据结构存储数据，一切符合链表的特性都对它生效；
  • LinkedList从头部，尾部添加删除元素的时间复杂度是O(1)，在中间位置插入或删除元素时不会产生ArrayList的扩容问题，但需要遍历到指定Node；
  • LinkedList通过index检索元素进行了index < (size >> 1)的优化，但通过object检索元素并没有优化；
  • LinkedList基于双向链表这种数据结构，对双端队列操作进行了实现；

所以，LinkedList适合在频繁的写入和删除，但检索相对较少的场景。因为写入和删除不会进行扩容，若在头部和尾部写入或删除元素，不会进行检索，时间复杂度是O(1)，就算进行检索，经过了index < (size >> 1)的优化，时间复杂度最多会是O(n/2)。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gleaming.cn/LinkedList-source-code/

更新于：Jul 28, 2022

评论




Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

载入天数...载入时分秒... Use Volantis as theme

Copyright © 2019-2022 XXX

鲁ICP备20003069号