双链表

双链表简介

定义

• 单链接列表中的结点具有 Value 字段，以及用于顺序链接结点的“Next”引用字段。
• 双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，就能够知道当前结点的前一个结点。
  

结点结构

• 双链表中结点结构的典型定义：

  class DoublyListNode {
      int val;
      DoublyListNode next, prev;
      DoublyListNode(int x) {val = x;}
  }
  1
  2
  3
  4
  5

• 与单链接列表类似，我们使用头结点来表示整个列表。

访问链表

• 我们不能在常量级的时间内访问随机位置。
• 我们必须从头部遍历才能得到我们想要的第一个结点。
• 在最坏的情况下，时间复杂度将是 O(N)，其中 N 是链表的长度。

双链表的插入操作

• 如果我们想在现有的结点 prev 之后插入一个新的结点 cur，我们可以将此过程分为两个步骤：
  • 链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；
    
  • 用 cur 重新链接 prev 和 next。
    
  • 与单链表类似，添加操作的时间和空间复杂度都是 O(1)。

双链表删除操作

• 如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。
  • 与单链表不同，使用“prev”字段可以很容易地在常量时间内获得前一个结点。
  • 因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是 O(1)。

单双链表的对比

• 它们都无法在常量时间内随机访问数据。
• 它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点。
• 它们都能够在 O(1) 时间内删除第一个结点。
• 但是删除给定结点(包括最后一个结点)时略有不同。
  • 在单链表中，它无法获取给定结点的前一个结点，因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。
  • 在双链表中，这会更容易，因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。