链表

2023-06-26 18:27:58

链表是一种线性数据结构，其每个元素都是一个节点对象，各个节点之间通过指针连接，在前节点通过指针可以访问到下一个节点。由于指针记录了下个节点的内存地址，因此无需保证在内存地址中的连续性，从而可以将各个节点分散存储在内存各处。

链表的每个节点包含两项数据，一是节点「值 Value」，二是指向下一节点的「指针 Pointer」，或称「引用 Reference」。

class ListNode {
  val: number
  next: ListNode | null
  constructor(val, next) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

初始化链表

建立链表第一步是初始化各个节点，第二步是构建各节点的指针引用关系。

// 初始化各个节点
const n0 = new ListNode(1)
const n1 = new ListNode(3)
const n2 = new ListNode(2)
const n3 = new ListNode(5)
const n4 = new ListNode(4)
// 构建引用指向
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4

初始化后的链表顺序为 1 -> 3 -> 2 -> 5 -> 4，可以从链表的头节点出发，通过指针 next 依次访问所有节点。

链表的优点

链表中插入与删除节点的操作效率高。例如，如果我们想在链表中间的两个节点 A , B 之间插入一个新节点 P ，我们只需要改变两个节点指针即可，将 A.next 指向 P，将 P.next 指向 B，时间复杂度为 O(1)，相比之下，数组的插入操作效率要低得多。

function insert(n0: ListNode, P: ListNode) {
  // 保存要插入位置的后一个节点指针
  const n1 = n0.next
  // 将其赋值给插入节点的next
  P.next = n1
  // 将插入位置的前一个节点的next赋值为插入节点
  n0.next = P
}

链表的缺点

链表访问节点效率较低。数组可以通过下标在 O(1) 时间下访问任意元素。但是链表无法直接访问任意节点，这是因为链表需要从头节点出发，逐个向后遍历直至找到目标节点。例如，若要访问链表索引为 index（即第 index + 1 个）的节点，则需要向后遍历 index 轮。

// 访问链表中索引为 index 的节点
function access(head: ListNode | null, index: number): ListNode | null {
  // 索引为index 循环index次
  for (let i = 0; i < index; i++) {
    if (!head) {
      return null
    }
    head = head.next
  }
  return head
}

链表的内存占用较大。链表以节点为单位，每个节点除了保存值之外，还需额外保存指针，这意味着在相同数据量的情况下，链表比数组需要占用更多的内存空间。

链表类型

• 单向链表。即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的指针（引用）两项数据。我们将首个节点称为头节点，将最后一个节点成为尾节点，尾节点指向空。

• 环形链表。令单向链表的尾节点指向头节点，得到一个环形链表。在环形链表中，任意节点都可以视作头节点。

• 双向链表。与单向链表相比，双向链表记录了两个方向的指针。双向链表的节点定义同时包含指向下一节点和上一节点的指针。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

遍历链表查找

遍历链表，查找链表内值为 target 的节点，输出节点在链表中的索引

function find(head: ListNode | null, target: number): number {
  let index = 0
  while (head !== null) {
    if (head.val === target) {
      return index
    }
    head = head.next
    index += 1
  }
  return -1
}