数据结构	是否为线性结构
数组（Array）	是
链表（LinkedList）	是
栈（Stack）	受限的
队列（Queue）	受限的

一、链表

1、认知

  在 JavaScript 中，并没有自带链表结构，需要我们自己实现。

  并且，不同与数组，链表中的元素在内存中不必是连续的空间。

2、特点

  链表中的每一个元素由存储本身的节点和下一个元素的引用（有些语言也称为指针）组成。

缺点是：无法通过下标访问，从头开始访问的方式效率低。

二、单向链表

参考：https://medium.com/swlh/anatomy-of-a-singly-linked-list-in-js-4e7452fec600

1、链表结构

• A Node

// A Node
class LinkedListNode<T> {
  element: T
  next: LinkedListNode<T> | null = null // 默认值为null

  constructor(element: T) {
    this.element = element
  }
}

• A Linked List

// A Linked List
class LinkedList<T> {
  head: LinkedListNode<T> | null = null
  private size: number = 0

  // 根据index获取对应的LinkedListNode节点
  private getNodeByIndex(index: number): LinkedListNode<T> | null {
    let current = this.head

    let num = 0
    while (num++ < index && current) {
      current = current.next // 更新current节点
    }

    return current
  }

  // ---

  // ……

  // ---
}

export default LinkedList

2、设计实现

LeetCode：设计链表 (opens new window)

  在手动编写代码的时候，可以想象一下 splice方法是怎么实现的 😂

class LinkedList<T> {
  // ……

  // ---

  peek(): T | undefined {
    return this.head?.element
  }

  get length(): number {
    return this.size
  }

  isEmpty(): boolean {
    return this.size === 0
  }

  clear(): void {
    this.head = null
  }

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

  // 1、尾部追加
  append(element: T) {
    const newLinkedListNode = new LinkedListNode(element)

    // 判断是否为空链表
    if (this.head === null) {
      this.head = newLinkedListNode
    } else {
      let current = this.head // 临时变量current最终会被销毁

      while (current.next !== null) {
        current = current.next
      }

      // 最后一个element的 next 指向新增的 newLinkedListNode
      current.next = newLinkedListNode
    }

    this.size++
  }

  // 2、遍历element
  traverse(): T[] {
    const result: T[] = []
    let current = this.head

    while (current) {
      result.push(current.element)
      current = current.next
    }

    return result
  }

  // 3、获取元素索引值
  indexOf(checkElement: T): number {
    let current = this.head
    let index = 0

    while (current) {
      if (current.element === checkElement) {
        return index
      }
      current = current.next
      index++
    }

    return -1
  }

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

  // 1、插入元素
  insert(element: T, start: number) {
    // 越界判断
    if (start < 0 || start > this.size) return false

    const newLinkedListNode = new LinkedListNode(element)

    let current = this.head

    // 判断头部插入
    if (start === 0) {
      // 注意顺序
      newLinkedListNode.next = current
      this.head = newLinkedListNode
    } else {
      const previous = this.getNodeByIndex(start - 1)
      current = previous!.next

      previous!.next = newLinkedListNode
      newLinkedListNode!.next = current
    }

    this.size++
  }

  // 2、删除元素
  removeByIndex(index: number): T | null {
    // 越界判断
    if (index < 0 || index > this.size) return null

    let current = this.head

    // 判断头部删除
    if (index === 0) {
      this.head = current?.next ?? null
    } else {
      const previous = this.getNodeByIndex(index - 1)
      current = previous!.next

      previous!.next = current?.next ?? null
    }

    this.size--

    return current?.element ?? null
  }

  // 3、查看元素
  getByIndex(index: number): T | null {
    // 越界判断
    if (index < 0 || index > this.size) return null

    const current = this.getNodeByIndex(index)

    return current?.element ?? null
  }

  // 4、更新元素
  update(index: number, newElement: T) {
    // 越界判断
    if (index < 0 || index >= this.size) return false

    const current = this.getNodeByIndex(index)
    current!.element = newElement

    return true
  }

  // ---
}

3、练习：反转链表

LeetCode：反转链表 (opens new window)

• 栈

function reverseList(head: ListNode | null): ListNode | null {
  if (head === null) return null
  if (head.next === null) return head

  // 初始化一个栈
  const stack: ListNode[] = []

  // 入栈
  let current: ListNode | null = head
  while (current) {
    stack.push(current)
    current = current.next
  }

  // 出栈
  const newHead: ListNode = stack.pop()! // 新链表

  let newCurrent: ListNode | null = newHead
  while (stack.length) {
    newCurrent.next = stack.pop()!
    newCurrent = newCurrent.next
  }
  newCurrent.next = null // 收尾

  return newHead
}

• 迭代

function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head

  let newHead: ListNode | null = null // 新链表

  while (head) {
    let current: ListNode | null = head.next
    head.next = newHead
    newHead = head
    head = current
  }

  return newHead
}

• 递归

function reverseList(head: ListNode | null): ListNode | null {
  if (head === null || head.next === null) return head

  const newHead: ListNode | null = reverseList(head?.next ?? null) // 新链表

  // ListNode节点的next指向（向前推进）
  head.next.next = head
  head.next = null

  return newHead
}

三、循环链表

  在 单向链表 基础上进行拓展的一种数据结构，详见：

https://github.com/Lencamo/note-taking-case/tree/main/data-structure-ts-code/03_LinkedList

图示

四、双向链表

  在 单向链表 基础上进行拓展的一种数据结构，详见：

https://github.com/Lencamo/note-taking-case/tree/main/data-structure-ts-code/03_LinkedList

图示