List 接口的另一个主要实现:链表 LinkedList,以下源码基于 JDK 1.8

继承体系

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

底层数据结构

这一块的内容主要来自极客时间 —— 《数据结构与算法之美》中链表相关内容,个人对顺序进行整理,以及补充了部分内容

关于 数组链表内存中分布的不同:

数组:

数组需要一块连续的内存空间划分,所以对内存的要求较高,如果申请一个 100MB 大小的数组,当内存中没有连续、足够的存储空间时,即使内存的剩余总可用空间大于 100 MB,仍然会申请失败

链表:

链表与数组相反,并不需要连续的内存空间。链表通过 "指针" 将一组零散的内存块串联起来使用,所以申请链表时只要内存空间足够,哪怕不连续也不会有问题。

链表的分类:

前置概念:

  • 结点(节点):对应到 LinkedList 中具体的概念就是 Node,其中存储着链表中的元素,并且存放着指向下一个和上一个节点的指针。
    • 后继指针: 对应到 LinkedList 中就是 next 引用,指向下一个节点。
    • 前驱指针 :对应 LinkedList Node 类中的 prev 引用,指向当前节点的上一个节点。
    • 头节点: : 链表中的第一个节点
    • 尾节点 : 链表中的最后一个节点,尾节点的后继指针指向一个 空地址 NULL

单向链表 从前到后单向用指针串联起来的链表

双向链表 :每个结点有一个后继指针指向后一个节点,和一个前驱指针 prev 指向前一个节点。LinkedList 是一个双向链表)

image-20201017164743055

循环链表: 一种特殊的单向链表,区别是尾部结点指向头结点

image-20201017165026210

链表的 CRUD:

查找(单向链表):

因为链表中的数据在内存中并非连续存储,所以无法支持数组中的根据 首地址下标 ,通过 寻址公式 直接计算出对应内存地址的 O(1) 时间复杂度的随机查询,而是需要一个结点一个结点进行遍历,直到找到对应的节点,链表的随机访问时间复杂度是 O(n)

添加(单向链表)

  • 首先对照一下 数组 的添加元素操作,因为数组需要保持其**内存数据连续**的特性,所以当添加的元素在数组中间时,需要做大量的数据搬移,算下来时间复杂度是 O(n) 。
  • 链表: 因为链表底层的存储空间本身就不是连续的内存,所以在链表中插入或删除一个数据只需要修改附近节点的指针即可,非常快速,下面是示意图:

image-20201018130420897

删除(单向链表):

image-20201018130720608


双向链表与单向链表有很大的不同,下面讲解双向链表的 增删查 操作原理:

删除(双向链表):

实际开发中,删除分为两种情况:

  • 删除节点中"值等于某个给定值" 的节点 ---> 对应 LinkedListremove(Object)
  • 删除给定指针指向的节点 ---> 对应 LinkedListremove(int)

第一种情况: 无论是单链表还是双向链表,为了找到值等于给定值的节点,都需要从头节点开始一个个执行 「 **遍历—对比** 」 的操作,直到找到值等于给定值的节点,再通过之前的指针操作将其删除。

虽然单纯的删除操作的时间复杂度是 O(1) , 但是在执行删除之前要先找到它,所以遍历查找是主要的耗时点,对应时间复杂度 O(n) , 根据时间复杂度分析的加法法则,删除 「值等于给定值的节点」 对应的链表操作总时间复杂度为 O(n)

第二种情况: 首先已经找到了要删除的节点,但是删除某个节点 q 需要知道前驱节点,但是之前的单链表并不能直接获取前驱节点,所以为了找到前驱节点,还是需要从头进行遍历,直到找到 p -> next = q,说明 p 是 q 的前驱节点

但是对于双向链表来说,节点中直接存储了前驱节点的指针,所以不需要像单链表那样再执行一遍从头遍历操作,所以这种情况下, 单链表 的删除时间复杂度仍然为 O(n) , 而 双向链表 的时间复杂度是 O(1)

添加(双向链表)

单向链表的插入新节点操作的时间复杂度是 O(1) ,但是插入新节点需要找到前驱节点,这个寻找前驱节点的遍历操作的时间复杂度是 O(n) ,它拖累了整个操作的速度。

而双向链表的优势是节点中保存了前驱节点的指针,所以省去了遍历操作的耗时,整个添加节点的时间复杂度是 O(1)。

缺点是双向链表占用更多的空间来存放指针。【典型的 空间换时间,所以需要根据业务场景来判断是否值得使用更多的空间来换取插入/删除 速度的提升。】

查找(双向链表)

对于一个 有序链表 来说,双向链表 按值查询效率比单链表高,因为 单链表 只能从前到后遍历查找,最坏情况需要遍历整个链表。

而双向链表可以在链表中心位置设置一个指针,当要查找某元素时先与中心的指针进行对比,这就相当于直接进行了一次 二分 的操作,所以平均只需要查找一半的数据。

但是这个前提是有序链表,有序非常重要。

类注释

Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).

双向链表LinkedList)实现了 ListDeque 接口,并且实现了 List 接口中的所有操作,并且允许 null 元素存在。【读完这句话,看了眼继承结构,我转去看 DequeQueue 的类注释去了,读源码真的是抽丝剥茧,一环套一环】

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse(穿过) the list from the beginning or the end, whichever is closer to the specified index.

类中所有的操作都按照双线链表的预期执行。索引到列表的开头或结尾遍历列表,以最接近指定索引的位置为准。【quest:这句话不太明白,需要去看具体代码】

①:Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list:
List list = Collections.synchronizedList(new LinkedList(...));

②:The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

③:Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
This class is a member of the Java Collections Framework.

上面这几段和 Collection 中的注释一样,就不细写了:

  • ①:LinkedList 非线程安全,如果要获得线程安全的集合,使用 下面的包装器方法 List list = Collections.synchronizedList(new LinkedList(...));
  • ②:迭代器具有快速失败特性,抛出 ConcurrentModificationException 异常
  • ③:快速失败机制不能做出严格的线程安全保证,ConcurrentModificationException 异常只是一种提醒机制

小结:

大部分注释都和 Collection 中的一样,说明了线程安全性、快速失败机制。

LinkedList 独有的双向链表的特性并没有过多体现,于是继续看代码吧。

类结构:

可以看到 LinkedList 中的方法分为几个部分:

  • 实现双端队列 Deque 中的方法
  • 实现 List 中的方法
  • ListIterator 迭代器的方法
  • 数据结构 Node 的定义以及方法
  • 其他非实现接口的方法。

方法不少,一个个来看。

image-20201016021949317

1. 数据结构

容器类最核心的就是底层数据结构的定义,很多容器类特性实际上就是底层数据结构的特性,比如 ArrayList 的随机访问效率极高就是因为底层使用的是数组。

LinkedList 的数据结构: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;
  }
}

可以看到, Node 中可以保存一个对象 item,并且保存了前一个节点后一个节点的引用,形成一条链表。

image-20200620000015294

2. 构造方法

根据 Collection 规范,依旧是至少两个构造函数:一个无参,一个入参为 Collection

public LinkedList() {
}

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

数据存储方法:CRUD

虽然我们总是对 CRUD 好像带着一种鄙视的态度,但是底层数据的核心除了数据结构本身的特性,我觉得从这几个方法下手是一个不错的切入点。

1. 向链表中添加元素

1.1 将传入集合的所有参数添加到当前链表中 ---> addAll

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


public boolean addAll(int index, Collection<? extends E> c) {
  checkPositionIndex(index);
	// 将 Collection 拷贝为数组
  Object[] a = c.toArray();
  int numNew = a.length;
  // 如果要添加的集合为空,则直接返回 false
  if (numNew == 0)
    return false;
	
  // pred 是 index 节点的前置节点,succ 是后置节点
  Node<E> pred, succ;
  // 如果添加元素的索引与链表长度一致,则将该元素放入链表的尾部
  if (index == size) {
    // 队尾的后置节点为null,前置节点为插入之前的队尾
    succ = null;
    pred = last;
  } else {
    // 取出 index 节点,作为后置节点
    succ = node(index);
    // index 前的节点
    pred = succ.prev;
  }
	// 遍历数组,向链表中添加节点
  for (Object o : a) {
    @SuppressWarnings("unchecked") E e = (E) o;
    // 根据之前的构造函数,可以看到将 pred 作为 item,e 是当前数组中的对象 作为 next 节点,前节点传入的是 null 
    Node<E> newNode = new Node<>(pred, e, null);
    // 如果没有前节点,说明插入的位置是链表头部,则将新创建的 Node 赋值给头节点
    if (pred == null)
      first = newNode;
    else
      // 否则的话将前置节点的后置节点设置为新节点
      pred.next = newNode;
    // 将当前节点设置为前置节点,为下次添加新元素做准备
    pred = newNode;
  }
	// 插入元素循环结束后开始判断尾节点,如果节点是 null,则设置尾节点(这块没看懂)
  if (succ == null) {
    last = pred;
  } else {
    // 如果不是在链表尾部插入元素,则说明是在链表中插入,需要更新前置节点为 succ 也就是当前插入的位置,为下次插入做准备
    pred.next = succ;
    // 更新后置节点的前置节点
    succ.prev = pred;
  }
	// 修改链表的大小:原本的大小 + 本次插入集合的大小
  size += numNew;
  modCount++;
  return true;
}


// ---------- addAll 涉及到的 private 方法 ---------- // 

// 1、检查元素索引是否正确:大于0,且小于当前链表长度,都满足为正确的索引数
private void checkPositionIndex(int index) {
  if (!isPositionIndex(index))
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

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



public boolean add(E e) {
  linkLast(e);
  return true;
}


public void add(int index, E element) {
  // 检查索引是否合法
  checkPositionIndex(index);

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

// ----------- //

// Links e as last element. 在链表的尾部追加一个节点
void linkLast(E e) {
  // 将链表当前的尾部节点赋值给 l
  final Node<E> l = last;
  // 创建一个新的节点,prev 节点是当前的 last 节点
  final Node<E> newNode = new Node<>(l, e, null);
  // 更新链表尾部节点
  last = newNode;
  // 如果尾部节点不存在 ---> 链表中没有任何节点
  if (l == null)
    // 于是把新节点设置为头节点
    first = newNode;
  else
    // 将之前的尾部节点的后继指针指向新的节点
    l.next = newNode;
  // 修改容量和计数器
  size++;
  modCount++;
}

// Inserts element e before non-null Node succ. 
// 在 succ 节点之前插入一个新节点 e
// 这里的入参 e 是新增的元素,而 succ 则是根据索引获取到的已经存在的节点 作为后置节点
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++;
}

小结:

链表和数组一样,都是线性数据结构。并且它的特点也非常鲜明:适合频繁插入、删除链表节点的场景,而查询复杂度则较高。

仔细看了下它的 CRUD 方法,配合之前极客时间中的课程以及自己画了一下图,感觉还是很清晰的,没什么比较复杂的地方。

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。