链表结构

认识链表结构

链表与数组优缺点

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同

数组有很多缺点:

数组的创建通常需要申请一段 连续的内存空间（一整块的内存），并且大小是固定的（大多数编程语言数组都是固定的），所以当当前数组 不能满足容量需求 时，需要扩容。(一般情况下是申请一个更大的数组，比如 2 倍。然后将原数组中的元素复制过去)
而且在 数组开头或中间位置插入数据的成本很高，需要 进行大量元素的位移
尽管 JavaScript 的 Array 底层可以帮我们做这些事，但背后的原理依然是这样

要存储多个元素，另外一个选择就是链表

但不同于数组，链表中的元素在内存中不必是连续的空间
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有些语言称为指针或者链接）组成

相对于数组，链表有一些优点:

内存空间不是必须连续的
- 可以充分利用计算机的内存，实现灵活的内存动态管理口
链表不必在创建时就 确定大小，并且大小可以 无限的延伸 下去口
链表在 插入和删除 数据时，时间复杂度 可以达到 O(1)
- 相对数组效率高很多

相对于数组，链表有一些缺点:

链表访问任何一个位置的元素时，都需要 从头开始访问。(无法跳过第一个元素访问任何一个元素)
无法通过下标直接访问元素，需要从头一个个访问，直到找到对应的元素

链表概念

什么是链表呢?

其实上面我们已经简单的提过了链表的结构，我们这里更加详细的分析一下
链表类似于火车：有一个火车头，火车头会连接一个节点，节点上有乘客（类似于数据），并且这个节点会连接下一个节点，以此类推

实现链表

封装一个 Node 类，用于封装每一个节点上的信息 (包括值和指向下一个节点的引用)，它是一个泛型类
封装一个 LinkedList 类，用于表示我们的链表结构。(和 Java 中的链表同名，不同 Java 中的这个类是一个双向链表)
链表中我们保存两个属性，一个是链表的长度，一个是链表中第一个节点

typescript

class Node<T> {
  value: T
  next: Node<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}

class LinkedList<T> {
  private head: Node<T> | null = null
  private size: number = 0
  get length() {
    return this.size
  }
}

链表完整代码

append(element)：向链表尾部添加一个新的项
insert(position，element)：向链表的特定位置插入一个新的项
get(position)：获取对应位置的元素indexOf(element): 返回元素在链表中的索引。如果链表中没有该元素则返回 -1
update(position，element)：修改某个位置的元素
removeAt(position)：从链表的特定位置移除一项
remove(element)：从链表中移除一项
isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false
size()：返回链表包含的元素个数。与数组的 length 属性类似

向链表尾部追加数据可能有两种情况

链表本身为空，新添加的数据时唯一的节点
链表不为空，需要向其他节点后面追加节点

typescript

class Node<T> {
  value: T
  next: Node<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}

class LinkedList<T> {
  private head: Node<T> | null = null
  private size: number = 0
  get length() {
    return this.size
  }
  // 根据position获取到当前的节点（不是节点的value，而是获取节点）
  private getNode(position: number): Node<T> | null {
    let index = 0
    let current = this.head
    while (index++ < position && current) {
      current = current.next
    }
    return current
  }

  append(value: T) {
    // 1.根据value创建一个新节点
    const newNode = new Node(value)
    // 2.判断this.head是否为null
    if (!this.head) {
      this.head = newNode
    } else {
      let current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = newNode
    }
    this.size++
  }

  traverse() {
    const values: T[] = []
    let current = this.head
    while (current) {
      values.push(current.value)
      current = current.next
    }
    console.log(values.join('->'))
  }

  insert(value: T, position: number): boolean {
    // 1.越界的判断
    if (position < 0 || position > this.size) return false
    // 2.根据value创建新的节点
    const newNode = new Node(value)
    // 3.判断是否需要插入头部
    if (position === 0) {
      // 新节点next指向头部节点、头部
      newNode.next = this.head
      this.head = newNode
    } else {
      const previous = this.getNode(position - 1)
      newNode.next = previous?.next ?? null
      previous!.next = newNode
    }
    this.size++
    return true
  }

  removeAt(position: number): T | null {
    // 1.越界的判断
    if (position < 0 || position >= this.size) return null
    // 2.判断是否是删除第一个节点
    let current = this.head
    if (position === 0) {
      this.head = current?.next ?? null
    } else {
      const previous = this.getNode(position - 1)
      current = previous!.next
      previous!.next = previous?.next?.next ?? null
    }
    this.size--
    return current?.value ?? null
  }

  get(position: number): T | null {
    // 1.越界的判断
    if (position < 0 || position >= this.size) return null
    // 2.查找元素，并且返回元素
    return this.getNode(position)?.value ?? null
  }

  update(value: T, position: number): boolean {
    if (position < 0 || position >= this.size) return false
    const currentNode = this.getNode(position)
    // 获取对应位置的节点，直接更新即可
    currentNode!.value = value
    return true
  }

  indexOf(value: T): number {
    let current = this.head
    let index = 0
    while (current) {
      if (current.value === value) {
        return index
      }
      current = current.next
      index++
    }
    return -1
  }

  remove(value: T): T | null {
    const index = this.indexOf(value)
    return this.removeAt(index)
  }

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

链表题型

设计链表

707. 设计链表

你可以选择使用单链表或者双链表，设计并实现自己的链表

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点

抽离接口方法

typescript

interface IList<T> {
  peek(): T | undefined
  isEmpty(): boolean
  size(): number
}

interface ILinkedList<T> extends IList<T> {
  append(value: T): void
  traverse(): void
  insert(value: T, position: number): boolean
  get(position: number): T | null
  update(value: T, position: number): boolean
  indexOf(value: T): number
  remove(value: T): T | null
}

删除链表中的节点

237. 删除链表中的节点

有一个单链表的 head，我们想删除它其中的一个节点 node

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中
链表中的节点数应该减少 1
node 前面的所有值顺序相同
node 后面的所有值顺序相同

typescript

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

function deleteNode(node: ListNode | null): void {
  node!.val = node!.next!.val
  node!.next = node!.next!.next
}

反转链表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

利用栈结构解决

typescript

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
  }
  let newHead: ListNode = stack.pop()!
  let newHeadCurrent = newHead
  while (stack.length) {
    const node = stack.pop()!
    newHeadCurrent.next = node
    newHeadCurrent = newHeadCurrent.next
  }
  // 注意：获取到最后一个节点时，一定要将节点的 next 置为 null
  newHeadCurrent.next = null
  return newHead
}

const node1 = new ListNode(1)
node1.next = new ListNode(2)
node1.next.next = new ListNode(3)
const newHead = reverseList(node1)
let current = newHead
while (current) {
  console.log(current.val)
  current = current.next
}

非递归方式

让 current 指向下一个节点
- 目的：保留着下一个节点的引用，可以拿到，并且不会销毁
改变 head 当前指向的节点，指向 newHead
- 对于第一个节点来说，指向 newHead 就是指向 null
让 newHead 指向 head 节点
- 目的是下一次遍历时，第二步操作，可以让下一个节点指向第一个节点
让 head 移向下一个节点，指向 current

typescript

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
}

递归方式

第一次进入 const newHead 下面的代码是倒数第二个节点，因为倒数第一个节点的 next 为 null

typescript

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

链表结构 ​

认识链表结构 ​

链表与数组优缺点 ​

链表概念 ​

实现链表 ​

链表完整代码 ​

链表题型 ​

设计链表 ​

删除链表中的节点 ​

反转链表 ​

利用栈结构解决 ​

非递归方式 ​

递归方式 ​

链表结构

认识链表结构

链表与数组优缺点

链表概念

实现链表

链表完整代码

链表题型

设计链表

删除链表中的节点

反转链表

利用栈结构解决

非递归方式

递归方式