小菜鸟

java菜鸟号正在起航

0%

LinkedList详解

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 6.5k 阅读时长 ≈ 6 分钟

LinkedList详解

LinkedList是List接口的一个主要的实现类之一，基于链表的实现。以java8为例来了解一下LinkedList的源码实现

继承关系

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

LinkedList

继承了AbstractSequentialList，实现了List接口、Deque接口、Cloneable接口、Serializable接口

关键变量

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
/**
* 链表的长度
*/
transient int size = 0;

/**
 * 头节点
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * 尾节点
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

// 这里用到了一个内部类Node，看到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;
  }
}

构造器

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
73
74
75
76
// 无参默认构造器
public LinkedList() {
}

/**
 * 传入一个集合作为参数
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

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

public boolean addAll(int index, Collection<? extends E> c) {
  // 检查是否越界
  checkPositionIndex(index);

  Object[] a = c.toArray();
  // 新增元素的数量
  int numNew = a.length;
  if (numNew == 0)
    return false;
    // 前置节点和后置节点
  Node<E> pred, succ;
  // index == size时表示是从链表尾部添加元素，所以前置节点为当前链表的尾节点
  if (index == size) {
    succ = null;
    pred = last;
  } else { // 不是从链表尾部添加，需要修改前置节点和后置节点
    succ = node(index);
    pred = succ.prev;
  }

  for (Object o : a) {
    @SuppressWarnings("unchecked") E e = (E) o;
    Node<E> newNode = new Node<>(pred, e, null);
    // 前置节点为null，表示这是头节点
    if (pred == null)
      first = newNode;
    else
      pred.next = newNode;
    pred = newNode;
  }
    // succ == null,说明是从尾部添加的，将最后一个节点赋给尾节点
  if (succ == null) {
    last = pred;
  } else {
    pred.next = succ;
    succ.prev = pred;
  }

  size += numNew;
  modCount++;
  return true;
}

// 获取index位置的节点
Node<E> node(int index) {
  // assert isElementIndex(index);
    // index小于链表长度的一半，从链表头部开始遍历
  if (index < (size >> 1)) {
    Node<E> x = first;
    for (int i = 0; i < index; i++)
      x = x.next;
    return x;
  } else { // index不小于链表长度的一半，从链表尾部开始遍历
    Node<E> x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

add方法

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
// 逻辑比较简单，与上边addAll类似，一通插
public void add(int index, E element) {
    checkPositionIndex(index);
        // index == size表示在链表尾部添加
    if (index == size)
        linkLast(element);
    else // 否则在中间插入  先找到index所在位置的节点
        linkBefore(element, node(index));
}

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

void linkBefore(E e, Node<E> succ) {
  // assert succ != null;
  final Node<E> pred = succ.prev;
  final Node<E> newNode = new Node<>(pred, e, succ);
  succ.prev = newNode;
  if (pred == null)
      first = newNode;
  else
      pred.next = newNode;
  size++;
  modCount++;
}

remove方法

LinkedList的remove方法比较简单

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
public E remove(int index) {
      // 检测该索引位置是否符合要求  index >= 0 && index < size
    checkElementIndex(index);
    return unlink(node(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;
  }
}

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;
    // 前驱节点为null，表示为头节点，头节点指向后继节点即可
  if (prev == null) {
    first = next;
  } else {
    // 前驱节点的后继节点指向该元素的后继节点
    prev.next = next;
    x.prev = null;
  }
    // 后继节点为null，表示为尾节点，尾节点指向前驱节点即可
  if (next == null) {
    last = prev;
  } else {
    // 后继节点的前驱节点指向该元素的前驱节点
    next.prev = prev;
    x.next = null;
  }

  x.item = null;
  size--;
  modCount++;
  return element;
}

迭代器

LinkedList使用的迭代器是其父类AbstractSequentialList中的iterator方法，其迭代器是双向的，可以正向也可以反向

1
2
3
4
5
6
7
8
9
10
// AbstractSequentialList类方法
public Iterator<E> iterator() {
    return listIterator();
}

// LinkedList类方法
public ListIterator<E> listIterator(int index) {
  checkPositionIndex(index);
  return new ListItr(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
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//  与ArrayList的迭代器不同的是，ArrayList的迭代器实现的是Iterator接口 而LinkedList为ListIterator接口，相当于ArrayList的listIterator()方法
//  Iterator只能向前遍历，ListIterator可以向前也可以向后
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        checkForComodification();
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (modCount == expectedModCount && nextIndex < size) {
            action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
相关文章

欢迎关注我的其它发布渠道