2025-12-26-Javascript/TypeScript 的顺序表，链表实现

1
class LRUCache {
2
    /**
3
     * 构造函数
4
     * @param {number} capacity - 缓存的最大容量
5
     */
6
    constructor(capacity) {
7
        this.capacity = capacity;        // 缓存容量
8
        this.cache = new Map();          // 使用 Map 作为哈希表，保持插入顺序并支持 O(1) 操作
9
        this.head = {};                  // 双向链表的虚拟头节点
10
        this.tail = {};                  // 双向链表的虚拟尾节点
11
        this.head.next = this.tail;      // 初始化链表：head <-> tail
12
        this.tail.prev = this.head;
13
    }
14

15
    /**
16
     * 将节点移动到链表头部（表示最近使用）
17
     * @private
18
     * @param {Object} node - 要移动的节点
19
     */
20
    _moveToHead(node) {
21
        // 先从当前位置移除
22
        node.prev.next = node.next;
23
        node.next.prev = node.prev;
24

25
        // 插入到头部
26
        node.next = this.head.next;
27
        node.prev = this.head;
28
        this.head.next.prev = node;
29
        this.head.next = node;
30
    }
31

32
    /**
33
     * 从链表尾部移除节点（淘汰最久未使用的）
34
     * @private
35
     * @returns {Object} 被移除的节点
36
     */
37
    _removeTail() {
38
        const lastNode = this.tail.prev;
39
        lastNode.prev.next = this.tail;
40
        this.tail.prev = lastNode.prev;
41
        return lastNode;
42
    }
43

44
    /**
45
     * 获取缓存值
46
     * @param {any} key - 键
47
     * @returns {any} 值，如果不存在返回 -1
48
     */
49
    get(key) {
50
        const node = this.cache.get(key);
51
        if (!node) {
52
            return -1;  // 未找到
53
        }
54
        // 刷新访问顺序：将节点移到头部
55
        this._moveToHead(node);
56
        return node.value;
57
    }
58

59
    /**
60
     * 放入缓存
61
     * @param {any} key - 键
62
     * @param {any} value - 值
63
     */
64
    put(key, value) {
65
        const existingNode = this.cache.get(key);
66

67
        if (existingNode) {
68
            // 已存在：更新值并移到头部
69
            existingNode.value = value;
70
            this._moveToHead(existingNode);
71
        } else {
72
            // 不存在：创建新节点
73
            const newNode = { key, value, prev: null, next: null };
74
            this.cache.set(key, newNode);
75

76
            // 插入到头部
77
            newNode.next = this.head.next;
78
            newNode.prev = this.head;
79
            this.head.next.prev = newNode;
80
            this.head.next = newNode;
81

82
            // 检查容量是否超出
83
            if (this.cache.size > this.capacity) {
84
                const tailNode = this._removeTail();  // 移除尾部节点
85
                this.cache.delete(tailNode.key);      // 从哈希表中删除
86
            }
87
        }
88
    }
89

90
    // 可选：打印当前缓存顺序（用于调试）
91
    printCache() {
92
        const result = [];
93
        let current = this.head.next;
94
        while (current !== this.tail) {
95
            result.push(`${current.key}:${current.value}`);
96
            current = current.next;
97
        }
98
        console.log('LRU Cache (most recent -> least recent):', result.join(' -> '));
99
    }
100
}
101

102
// 使用示例
103
const cache = new LRUCache(3);
104
cache.put(1, 1);
105
cache.put(2, 2);
106
cache.put(3, 3);
107
cache.printCache();  // 3:3 -> 2:2 -> 1:1
108

109
console.log(cache.get(2));  // 2（刷新顺序）
110
cache.printCache();         // 2:2 -> 3:3 -> 1:1
111

112
cache.put(4, 4);            // 容量满，淘汰最久未使用的 1
113
cache.printCache();         // 4:4 -> 2:2 -> 3:3

1
// 双向链表节点接口
2
interface Node<K, V> {
3
    key: K;
4
    value: V;
5
    prev: Node<K, V> | null;
6
    next: Node<K, V> | null;
7
}
8

9
class LRUCache<K = number, V = number> {
10
    private capacity: number;                // 缓存容量
11
    private cache: Map<K, Node<K, V>>;        // 哈希表：键到节点的映射
12
    private head: Node<K, V>;                // 虚拟头节点
13
    private tail: Node<K, V>;                // 虚拟尾节点
14

15
    constructor(capacity: number) {
16
        this.capacity = capacity;
17
        this.cache = new Map<K, Node<K, V>>();
18
        this.head = { key: null as any, value: null as any, prev: null, next: null };
19
        this.tail = { key: null as any, value: null as any, prev: null, next: null };
20
        this.head.next = this.tail;
21
        this.tail.prev = this.head;
22
    }
23

24
    // 将节点移动到头部（最近使用）
25
    private moveToHead(node: Node<K, V>): void {
26
        // 从当前位置移除
27
        node.prev!.next = node.next;
28
        node.next!.prev = node.prev!;
29

30
        // 插入头部
31
        node.next = this.head.next;
32
        node.prev = this.head;
33
        this.head.next!.prev = node;
34
        this.head.next = node;
35
    }
36

37
    // 移除尾部节点（最久未使用）
38
    private removeTail(): Node<K, V> {
39
        const lastNode = this.tail.prev!;
40
        lastNode.prev!.next = this.tail;
41
        this.tail.prev = lastNode.prev;
42
        return lastNode;
43
    }
44

45
    // 获取值
46
    get(key: K): V | -1 {
47
        const node = this.cache.get(key);
48
        if (!node) {
49
            return -1;
50
        }
51
        this.moveToHead(node);  // 刷新访问顺序
52
        return node.value;
53
    }
54

55
    // 放入键值对
56
    put(key: K, value: V): void {
57
        const existingNode = this.cache.get(key);
58

59
        if (existingNode) {
60
            existingNode.value = value;  // 更新值
61
            this.moveToHead(existingNode);
62
        } else {
63
            const newNode: Node<K, V> = { key, value, prev: null, next: null };
64
            this.cache.set(key, newNode);
65

66
            // 插入头部
67
            newNode.next = this.head.next;
68
            newNode.prev = this.head;
69
            this.head.next!.prev = newNode;
70
            this.head.next = newNode;
71

72
            // 超出容量时淘汰
73
            if (this.cache.size > this.capacity) {
74
                const tailNode = this.removeTail();
75
                this.cache.delete(tailNode.key);
76
            }
77
        }
78
    }
79

80
    // 调试：打印缓存顺序（最近 -> 最久）
81
    printCache(): void {
82
        const result: string[] = [];
83
        let current = this.head.next;
84
        while (current !== this.tail) {
85
            result.push(`${current!.key}:${current!.value}`);
86
            current = current!.next;
87
        }
88
        console.log('LRU Cache:', result.join(' -> '));
89
    }
90
}
91

92
// 使用示例
93
const cache = new LRUCache<number, number>(3);
94
cache.put(1, 1);
95
cache.put(2, 2);
96
cache.put(3, 3);
97
cache.printCache();  // 3:3 -> 2:2 -> 1:1
98
console.log(cache.get(2));  // 2
99
cache.printCache();         // 2:2 -> 3:3 -> 1:1

1
// 单向链表节点定义
2
class ListNode {
3
    constructor(val = null, next = null) {
4
        this.val = val;
5
        this.next = next;
6
    }
7
}
8

9
// 创建链表的辅助函数
10
function createLinkedList(arr) {
11
    if (arr.length === 0) return null;
12
    let head = new ListNode(arr[0]);
13
    let current = head;
14
    for (let i = 1; i < arr.length; i++) {
15
        current.next = new ListNode(arr[i]);
16
        current = current.next;
17
    }
18
    return head;
19
}
20

21
// 打印链表的辅助函数
22
function printLinkedList(head) {
23
    const result = [];
24
    let current = head;
25
    while (current) {
26
        result.push(current.val);
27
        current = current.next;
28
    }
29
    console.log('LinkedList:', result.join(' -> '));
30
}
31

32
// 方法一：迭代反转（推荐，空间复杂度 O(1)）
33
function reverseListIterative(head) {
34
    let prev = null;         // 前驱指针
35
    let current = head;      // 当前指针
36
    let next = null;         // 临时存储下一节点
37

38
    while (current !== null) {
39
        next = current.next; // 保存下一节点
40
        current.next = prev; // 反转指针
41
        prev = current;      // 前驱前进
42
        current = next;      // 当前前进
43
    }
44
    return prev;  // prev 成为新头节点
45
}
46

47
// 方法二：递归反转
48
function reverseListRecursive(head) {
49
    // 递归终止条件：空链表或只有一个节点
50
    if (head === null || head.next === null) {
51
        return head;
52
    }
53

54
    // 递归反转后续链表
55
    const newHead = reverseListRecursive(head.next);
56

57
    // 反转当前节点与下一节点的指向
58
    head.next.next = head;
59
    head.next = null;
60

61
    return newHead;  // 新头节点始终是原链表的尾节点
62
}
63

64
// 使用示例
65
const list = createLinkedList([1, 2, 3, 4, 5]);
66
printLinkedList(list);  // 1 -> 2 -> 3 -> 4 -> 5
67

68
const reversedIterative = reverseListIterative(list);
69
printLinkedList(reversedIterative);  // 5 -> 4 -> 3 -> 2 -> 1
70

71
const list2 = createLinkedList([6, 7, 8]);
72
printLinkedList(list2);  // 6 -> 7 -> 8
73

74
const reversedRecursive = reverseListRecursive(list2);
75
printLinkedList(reversedRecursive);  // 8 -> 7 -> 6

1
// 单向链表节点类型
2
class ListNode {
3
    val: number;
4
    next: ListNode | null;
5
    constructor(val?: number, next?: ListNode) {
6
        this.val = val ?? 0;
7
        this.next = next ?? null;
8
    }
9
}
10

11
// 创建链表辅助函数
12
function createLinkedList(arr: number[]): ListNode | null {
13
    if (arr.length === 0) return null;
14
    const head = new ListNode(arr[0]);
15
    let current = head;
16
    for (let i = 1; i < arr.length; i++) {
17
        current.next = new ListNode(arr[i]);
18
        current = current.next;
19
    }
20
    return head;
21
}
22

23
// 打印链表辅助函数
24
function printLinkedList(head: ListNode | null): void {
25
    const result: number[] = [];
26
    let current = head;
27
    while (current) {
28
        result.push(current.val);
29
        current = current.next;
30
    }
31
    console.log('LinkedList:', result.join(' -> '));
32
}
33

34
// 迭代反转（推荐，空间 O(1)）
35
function reverseListIterative(head: ListNode | null): ListNode | null {
36
    let prev: ListNode | null = null;
37
    let current: ListNode | null = head;
38

39
    while (current !== null) {
40
        const next = current.next;  // 保存下一节点
41
        current.next = prev;        // 反转指针
42
        prev = current;             // 前驱前进
43
        current = next;             // 当前前进
44
    }
45
    return prev;  // 新头节点
46
}
47

48
// 递归反转
49
function reverseListRecursive(head: ListNode | null): ListNode | null {
50
    if (head === null || head.next === null) {
51
        return head;
52
    }
53
    const newHead = reverseListRecursive(head.next);
54
    head.next.next = head;
55
    head.next = null;
56
    return newHead;
57
}
58

59
// 使用示例
60
const list = createLinkedList([1, 2, 3, 4, 5]);
61
printLinkedList(list);  // 1 -> 2 -> 3 -> 4 -> 5
62

63
const reversedIter = reverseListIterative(list);
64
printLinkedList(reversedIter);  // 5 -> 4 -> 3 -> 2 -> 1
65

66
const list2 = createLinkedList([6, 7, 8]);
67
const reversedRec = reverseListRecursive(list2);
68
printLinkedList(reversedRec);  // 8 -> 7 -> 6