Shared 函数库

Appearance

LinkedList ​

单向链表数据结构，元素通过指针连接。

函数签名 ​

typescript
function createLinkedList<T>(): LinkedList<T>

interface LinkedList<T> {
  prepend(value: T): void
  append(value: T): void
  insertAt(index: number, value: T): boolean
  removeAt(index: number): T | undefined
  indexOf(value: T): number
  get(index: number): T | undefined
  size(): number
  isEmpty(): boolean
  clear(): void
  toArray(): T[]
  reverse(): void
}

interface ListNode<T> {
  value: T
  next: ListNode<T> | null
}

API 说明 ​

prepend(value: T): void ​

在链表头部添加元素。

参数：

  • value: 要添加的元素

时间复杂度：O(1)

append(value: T): void ​

在链表尾部添加元素。

参数：

  • value: 要添加的元素

时间复杂度：O(n)

insertAt(index: number, value: T): boolean ​

在指定位置插入元素。

参数：

  • index: 插入位置（0-based）
  • value: 要插入的元素

返回值：

  • 插入成功返回 true，索引无效返回 false

时间复杂度：O(n)

removeAt(index: number): T | undefined ​

移除指定位置的元素。

参数：

  • index: 要移除的位置（0-based）

返回值：

  • 被移除的元素，索引无效返回 undefined

时间复杂度：O(n)

indexOf(value: T): number ​

查找元素的索引。

参数：

  • value: 要查找的元素

返回值：

  • 元素的索引，未找到返回 -1

时间复杂度：O(n)

get(index: number): T | undefined ​

获取指定位置的元素。

参数：

  • index: 位置（0-based）

返回值：

  • 该位置的元素，索引无效返回 undefined

时间复杂度：O(n)

size(): number ​

获取链表长度。

返回值：

  • 链表中元素的数量

时间复杂度：O(1)

isEmpty(): boolean ​

检查链表是否为空。

返回值：

  • 链表为空返回 true，否则返回 false

时间复杂度：O(1)

clear(): void ​

清空链表。

时间复杂度：O(1)

toArray(): T[] ​

转换为数组。

返回值：

  • 包含所有元素的数组

时间复杂度：O(n)

reverse(): void ​

反转链表。

时间复杂度：O(n)

使用示例 ​

typescript
import { createLinkedList } from '@shared/functions/data-structures/LinkedList'

// 创建链表
const list = createLinkedList<string>()

// 添加元素
list.append('A')
list.append('B')
list.append('C')
list.prepend('Z')  // 头部添加

console.log(list.toArray())  // ['Z', 'A', 'B', 'C']

// 插入元素
list.insertAt(2, 'X')  // 在索引 2 处插入
console.log(list.toArray())  // ['Z', 'A', 'X', 'B', 'C']

// 查找元素
console.log(list.indexOf('X'))  // 2

// 获取元素
console.log(list.get(2))  // 'X'

// 移除元素
console.log(list.removeAt(2))  // 'X'
console.log(list.toArray())  // ['Z', 'A', 'B', 'C']

// 反转链表
list.reverse()
console.log(list.toArray())  // ['C', 'B', 'A', 'Z']

// 获取大小
console.log(list.size())  // 4

// 清空链表
list.clear()
console.log(list.isEmpty())  // true

工作原理 ​

链表是一种线性数据结构，由一系列节点组成，每个节点包含：

  • 数据部分：存储元素值
  • 指针部分：指向下一个节点

单向链表特点：

  • 不需要连续内存空间
  • 动态大小，可以方便地添加和删除元素
  • 头部插入/删除效率高 O(1)
  • 随机访问效率低 O(n)

实现细节：

  • 维护 head 指针指向第一个节点
  • 维护 length 计数器记录元素数量
  • 遍历链表需要从头节点开始逐个访问

应用场景 ​

  1. 动态内存分配：操作系统中的内存管理
  2. 实现栈和队列：链表可以高效实现这些数据结构
  3. 音乐播放列表：歌曲的顺序播放和循环
  4. 浏览器历史：前进和后退功能
  5. 图的邻接表表示：图论算法
  6. LRU 缓存：结合哈希表实现

链表 vs 数组 ​

特性链表数组
内存分配动态，不连续静态或动态，连续
随机访问O(n)O(1)
头部插入/删除O(1)O(n)
尾部插入/删除O(n)O(1)
空间效率额外指针开销无额外开销

经典算法 ​

检测链表中的环 ​

typescript
function hasCycle<T>(list: LinkedList<T>): boolean {
  // 使用快慢指针
  let slow: ListNode<T> | null = head
  let fast: ListNode<T> | null = head
  
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
    
    if (slow === fast) {
      return true  // 有环
    }
  }
  
  return false  // 无环
}

找到链表的中间节点 ​

typescript
function findMiddle<T>(list: LinkedList<T>): number {
  // 使用快慢指针
  let slow = 0
  let fast = 0
  const size = list.size()
  
  while (fast < size && fast + 1 < size) {
    slow++
    fast += 2
  }
  
  return slow
}

合并两个有序链表 ​

typescript
function mergeSortedLists<T>(
  list1: LinkedList<T>,
  list2: LinkedList<T>,
  compare: (a: T, b: T) => number
): LinkedList<T> {
  const result = createLinkedList<T>()
  const arr1 = list1.toArray()
  const arr2 = list2.toArray()
  
  let i = 0, j = 0
  
  while (i < arr1.length && j < arr2.length) {
    if (compare(arr1[i], arr2[j]) <= 0) {
      result.append(arr1[i++])
    } else {
      result.append(arr2[j++])
    }
  }
  
  while (i < arr1.length) result.append(arr1[i++])
  while (j < arr2.length) result.append(arr2[j++])
  
  return result
}

性能特点 ​

操作时间复杂度说明
头部添加O(1)直接修改 head 指针
尾部添加O(n)需要遍历到末尾
指定位置插入O(n)需要遍历到该位置
删除O(n)需要遍历找到位置
查找O(n)需要遍历链表
反转O(n)需要遍历整个链表

Copyright © 2023-present