链表基础

为什么前端开发要学习链表？

链表在前端开发中有很多实际应用：

• 实现浏览器的前进/后退功能
• 组件更新队列管理
• 事件循环任务队列
• 文件系统的目录结构
• 撤销/重做功能实现

链表 vs 数组

数组的局限性

1. 固定大小，扩容成本高
2. 插入和删除需要移动元素
3. 连续内存空间要求高

链表的优势

1. 动态大小，按需分配内存
2. O(1)时间复杂度的插入和删除
3. 灵活的内存使用

链表实现

1. 节点定义

class ListNode {
    constructor(val) {
        this.val = val;      // 节点值
        this.next = null;    // 指向下一个节点的指针
    }
}

2. 链表类实现

class LinkedList {
    constructor() {
        this.head = null;    // 头节点
        this.size = 0;       // 链表大小
    }
    
    // 在头部添加节点
    addAtHead(val) {
        const newNode = new ListNode(val);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }
    
    // 在尾部添加节点
    addAtTail(val) {
        const newNode = new ListNode(val);
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }
    
    // 在指定位置添加节点
    addAtIndex(index, val) {
        if (index < 0 || index > this.size) return;
        if (index === 0) {
            this.addAtHead(val);
            return;
        }
        
        const newNode = new ListNode(val);
        let current = this.head;
        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
        this.size++;
    }
    
    // 删除指定位置的节点
    deleteAtIndex(index) {
        if (index < 0 || index >= this.size) return;
        if (index === 0) {
            this.head = this.head.next;
            this.size--;
            return;
        }
        
        let current = this.head;
        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }
        current.next = current.next.next;
        this.size--;
    }
    
    // 获取指定位置的节点值
    get(index) {
        if (index < 0 || index >= this.size) return -1;
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next;
        }
        return current.val;
    }
}

实际应用示例

1. 实现简单的撤销/重做功能

class UndoRedoManager {
    constructor() {
        this.undoStack = new LinkedList();
        this.redoStack = new LinkedList();
    }
    
    // 执行操作
    execute(action) {
        this.undoStack.addAtHead(action);
        this.redoStack = new LinkedList(); // 清空重做栈
    }
    
    // 撤销操作
    undo() {
        if (this.undoStack.size === 0) return null;
        const action = this.undoStack.get(0);
        this.undoStack.deleteAtIndex(0);
        this.redoStack.addAtHead(action);
        return action;
    }
    
    // 重做操作
    redo() {
        if (this.redoStack.size === 0) return null;
        const action = this.redoStack.get(0);
        this.redoStack.deleteAtIndex(0);
        this.undoStack.addAtHead(action);
        return action;
    }
}

2. 实现LRU缓存

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.list = new LinkedList();
    }
    
    get(key) {
        if (!this.cache.has(key)) return -1;
        
        // 将访问的节点移到头部
        const value = this.cache.get(key);
        this.list.deleteAtIndex(this.list.indexOf(key));
        this.list.addAtHead(key);
        
        return value;
    }
    
    put(key, value) {
        if (this.cache.has(key)) {
            this.list.deleteAtIndex(this.list.indexOf(key));
        } else if (this.cache.size >= this.capacity) {
            const lastKey = this.list.get(this.list.size - 1);
            this.cache.delete(lastKey);
            this.list.deleteAtIndex(this.list.size - 1);
        }
        
        this.cache.set(key, value);
        this.list.addAtHead(key);
    }
}

常见链表操作技巧

1. 双指针技巧

// 检测环形链表
function hasCycle(head) {
    let slow = head;
    let fast = head;
    
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    
    return false;
}

2. 反转链表

function reverseList(head) {
    let prev = null;
    let current = head;
    
    while (current) {
        const next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

性能优化建议

1. 使用尾指针优化尾部操作
2. 适当使用双向链表
3. 注意内存泄漏问题
4. 合理使用虚拟头节点

常见面试题

1. 如何检测链表中的环？
2. 如何找到链表的中间节点？
3. 如何合并两个有序链表？

推荐练习

1. LeetCode 206: 反转链表
2. LeetCode 141: 环形链表
3. LeetCode 21: 合并两个有序链表