zhangdizhangdi

链表介绍

【学习 JavaScript 数据结构与算法（第 3 版）】第 6 章

链表数据结构

数组的大小是固定的，从数组的起点或中间插入或移除项的成本很高，因为需要移动元素。

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。相对于传统的数组，链表的一个好处在于，添加或移除元素的时候不需要移动其他元素。

在数组中，我们可以直接访问任何位置的任何元素，而要想访问链表中间的一个元素，则需要从起点（表头）开始迭代链表直到找到所需的元素。

代码实现

书的官方代码库

为 leetcode 刷题，自己写的代码

ts
export class Node {
  val: number
  next: Node | null
  constructor(val?: number, next?: Node | null) {
    this.val = val || 0
    this.next = next || null
  }
}

export class LinkedList {
  head: Node | undefined

  constructor(array?: number[]) {
    if (array && array.length > 0) {
      this.create(array)
    }
  }

  create(array: number[]) {
    const node = new Node(-1)
    let cur = node
    for (let i = 0; i < array.length; i++) {
      cur.next = new Node(array[i])
      cur = cur.next

      if (i === 0) {
        this.head = cur
      }
    }
  }

  delete(val: number) {
    let cur = this.head
    while (cur) {
      const next = cur.next
      if (cur.val === val) {
        cur.val = next.val
        cur.next = next.next
        break
      }
      cur = next
    }
  }
}

export class CircularLinkedList extends LinkedList {
  constructor(array?: number[], pos?: number) {
    super()
    this.create(array, pos)
  }

  create(array: number[], pos?: number) {
    const node = new Node(-1)
    let cur = node
    let cycleNode = null
    for (let i = 0; i < array.length; i++) {
      cur.next = new Node(array[i])
      cur = cur.next
      if (pos > -1) {
        if (i === pos) {
          cycleNode = cur
        }
        if (i === array.length - 1) {
          cur.next = cycleNode
        }
      }

      if (i === 0) {
        this.head = cur
      }
    }
  }
}