前端面试题库

链表、数组、栈、队列的区别

11分钟阅读

我来详细介绍链表、数组、栈、队列这四种基础数据结构的区别。

1. 数组（Array）

特点

  • 连续内存存储：元素在内存中连续排列
  • 随机访问：可以通过索引直接访问任意元素
  • 固定类型：通常存储相同类型的元素

JavaScript实现

// 数组的基本操作
const arr = [1, 2, 3, 4, 5];
 
// 访问元素 - O(1)
console.log(arr[2]); // 3
 
// 插入元素
arr.push(6);        // 末尾插入 - O(1)
arr.unshift(0);     // 开头插入 - O(n)
arr.splice(2, 0, 1.5); // 中间插入 - O(n)
 
// 删除元素
arr.pop();          // 末尾删除 - O(1)
arr.shift();        // 开头删除 - O(n)
arr.splice(2, 1);   // 中间删除 - O(n)
 
// 查找元素
const index = arr.indexOf(3); // O(n)

时间复杂度

// 数组操作复杂度分析
class ArrayAnalysis {
    constructor() {
        this.arr = [];
    }
    
    // 访问 - O(1)
    access(index) {
        return this.arr[index];
    }
    
    // 搜索 - O(n)
    search(value) {
        for (let i = 0; i < this.arr.length; i++) {
            if (this.arr[i] === value) return i;
        }
        return -1;
    }
    
    // 末尾插入 - O(1)
    appendInsert(value) {
        this.arr.push(value);
    }
    
    // 任意位置插入 - O(n)
    insert(index, value) {
        this.arr.splice(index, 0, value);
    }
    
    // 末尾删除 - O(1)
    appendDelete() {
        return this.arr.pop();
    }
    
    // 任意位置删除 - O(n)
    delete(index) {
        return this.arr.splice(index, 1)[0];
    }
}

2. 链表（Linked List）

特点

  • 非连续内存：节点通过指针连接
  • 动态大小：可以在运行时改变大小
  • 顺序访问：只能从头节点开始遍历

JavaScript实现

// 链表节点
class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}
 
// 单向链表
class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    // 头部插入 - O(1)
    prepend(val) {
        const newNode = new ListNode(val);
        newNode.next = this.head;
        this.head = newNode;
        this.size++;
    }
    
    // 尾部插入 - O(n)
    append(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++;
    }
    
    // 指定位置插入 - O(n)
    insert(index, val) {
        if (index === 0) {
            this.prepend(val);
            return;
        }
        
        const newNode = new ListNode(val);
        let current = this.head;
        
        for (let i = 0; i < index - 1; i++) {
            if (!current) throw new Error('Index out of bounds');
            current = current.next;
        }
        
        newNode.next = current.next;
        current.next = newNode;
        this.size++;
    }
    
    // 删除指定值 - O(n)
    remove(val) {
        if (!this.head) return false;
        
        if (this.head.val === val) {
            this.head = this.head.next;
            this.size--;
            return true;
        }
        
        let current = this.head;
        while (current.next && current.next.val !== val) {
            current = current.next;
        }
        
        if (current.next) {
            current.next = current.next.next;
            this.size--;
            return true;
        }
        
        return false;
    }
    
    // 查找 - O(n)
    find(val) {
        let current = this.head;
        let index = 0;
        
        while (current) {
            if (current.val === val) return index;
            current = current.next;
            index++;
        }
        
        return -1;
    }
    
    // 访问指定位置 - O(n)
    get(index) {
        if (index < 0 || index >= this.size) return null;
        
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next;
        }
        
        return current.val;
    }
    
    // 转换为数组（用于显示）
    toArray() {
        const result = [];
        let current = this.head;
        while (current) {
            result.push(current.val);
            current = current.next;
        }
        return result;
    }
}

双向链表

class DoublyListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}
 
class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    
    // 头部插入 - O(1)
    prepend(val) {
        const newNode = new DoublyListNode(val);
        
        if (!this.head) {
            this.head = this.tail = newNode;
        } else {
            newNode.next = this.head;
            this.head.prev = newNode;
            this.head = newNode;
        }
        this.size++;
    }
    
    // 尾部插入 - O(1)
    append(val) {
        const newNode = new DoublyListNode(val);
        
        if (!this.tail) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.size++;
    }
    
    // 删除节点 - O(1) 如果有节点引用
    removeNode(node) {
        if (node.prev) {
            node.prev.next = node.next;
        } else {
            this.head = node.next;
        }
        
        if (node.next) {
            node.next.prev = node.prev;
        } else {
            this.tail = node.prev;
        }
        
        this.size--;
    }
}

3. 栈（Stack）

特点

  • LIFO：后进先出（Last In First Out）
  • 限制访问：只能在栈顶进行插入和删除操作
  • 递归天然结构：适合处理递归问题

JavaScript实现

// 基于数组的栈实现
class ArrayStack {
    constructor() {
        this.items = [];
    }
    
    // 入栈 - O(1)
    push(item) {
        this.items.push(item);
    }
    
    // 出栈 - O(1)
    pop() {
        if (this.isEmpty()) return undefined;
        return this.items.pop();
    }
    
    // 查看栈顶 - O(1)
    peek() {
        if (this.isEmpty()) return undefined;
        return this.items[this.items.length - 1];
    }
    
    // 判断是否为空 - O(1)
    isEmpty() {
        return this.items.length === 0;
    }
    
    // 获取大小 - O(1)
    size() {
        return this.items.length;
    }
    
    // 清空栈 - O(1)
    clear() {
        this.items = [];
    }
}
 
// 基于链表的栈实现
class LinkedStack {
    constructor() {
        this.top = null;
        this.length = 0;
    }
    
    // 入栈 - O(1)
    push(item) {
        const newNode = new ListNode(item);
        newNode.next = this.top;
        this.top = newNode;
        this.length++;
    }
    
    // 出栈 - O(1)
    pop() {
        if (!this.top) return undefined;
        
        const item = this.top.val;
        this.top = this.top.next;
        this.length--;
        return item;
    }
    
    // 查看栈顶 - O(1)
    peek() {
        return this.top ? this.top.val : undefined;
    }
    
    isEmpty() {
        return this.length === 0;
    }
    
    size() {
        return this.length;
    }
}

栈的应用示例

// 1. 括号匹配
function isValidParentheses(s) {
    const stack = new ArrayStack();
    const pairs = { '(': ')', '[': ']', '{': '}' };
    
    for (let char of s) {
        if (pairs[char]) {
            stack.push(char);
        } else if (Object.values(pairs).includes(char)) {
            if (stack.isEmpty() || pairs[stack.pop()] !== char) {
                return false;
            }
        }
    }
    
    return stack.isEmpty();
}
 
// 2. 表达式求值（后缀表达式）
function evaluatePostfix(tokens) {
    const stack = new ArrayStack();
    
    for (let token of tokens) {
        if (['+', '-', '*', '/'].includes(token)) {
            const b = stack.pop();
            const a = stack.pop();
            let result;
            
            switch (token) {
                case '+': result = a + b; break;
                case '-': result = a - b; break;
                case '*': result = a * b; break;
                case '/': result = Math.floor(a / b); break;
            }
            
            stack.push(result);
        } else {
            stack.push(parseInt(token));
        }
    }
    
    return stack.pop();
}
 
// 3. 函数调用栈模拟
function factorial(n) {
    const stack = new ArrayStack();
    stack.push({ n, state: 'compute' });
    let result = 1;
    
    while (!stack.isEmpty()) {
        const frame = stack.pop();
        
        if (frame.n <= 1) {
            result *= 1;
        } else {
            result *= frame.n;
            stack.push({ n: frame.n - 1, state: 'compute' });
        }
    }
    
    return result;
}

4. 队列（Queue）

特点

  • FIFO：先进先出（First In First Out）
  • 两端操作：一端插入（队尾），一端删除（队头）
  • 广度优先：适合BFS等算法

JavaScript实现

// 基于数组的队列（使用双指针优化）
class ArrayQueue {
    constructor() {
        this.items = [];
        this.front = 0;
    }
    
    // 入队 - O(1)
    enqueue(item) {
        this.items.push(item);
    }
    
    // 出队 - 均摊O(1)
    dequeue() {
        if (this.isEmpty()) return undefined;
        
        const item = this.items[this.front];
        this.front++;
        
        // 定期清理数组
        if (this.front > this.items.length / 2) {
            this.items = this.items.slice(this.front);
            this.front = 0;
        }
        
        return item;
    }
    
    // 查看队首 - O(1)
    peek() {
        if (this.isEmpty()) return undefined;
        return this.items[this.front];
    }
    
    isEmpty() {
        return this.front >= this.items.length;
    }
    
    size() {
        return this.items.length - this.front;
    }
}
 
// 基于链表的队列
class LinkedQueue {
    constructor() {
        this.front = null;  // 队头
        this.rear = null;   // 队尾
        this.length = 0;
    }
    
    // 入队 - O(1)
    enqueue(item) {
        const newNode = new ListNode(item);
        
        if (this.rear) {
            this.rear.next = newNode;
        } else {
            this.front = newNode;
        }
        
        this.rear = newNode;
        this.length++;
    }
    
    // 出队 - O(1)
    dequeue() {
        if (!this.front) return undefined;
        
        const item = this.front.val;
        this.front = this.front.next;
        
        if (!this.front) {
            this.rear = null;
        }
        
        this.length--;
        return item;
    }
    
    peek() {
        return this.front ? this.front.val : undefined;
    }
    
    isEmpty() {
        return this.length === 0;
    }
    
    size() {
        return this.length;
    }
}

队列的应用示例

// 1. 二叉树层序遍历
function levelOrder(root) {
    if (!root) return [];
    
    const result = [];
    const queue = new LinkedQueue();
    queue.enqueue(root);
    
    while (!queue.isEmpty()) {
        const node = queue.dequeue();
        result.push(node.val);
        
        if (node.left) queue.enqueue(node.left);
        if (node.right) queue.enqueue(node.right);
    }
    
    return result;
}
 
// 2. 任务调度系统
class TaskScheduler {
    constructor() {
        this.taskQueue = new LinkedQueue();
    }
    
    addTask(task) {
        this.taskQueue.enqueue(task);
    }
    
    processNext() {
        if (!this.taskQueue.isEmpty()) {
            const task = this.taskQueue.dequeue();
            console.log(`Processing task: ${task.name}`);
            return task;
        }
        return null;
    }
    
    getPendingCount() {
        return this.taskQueue.size();
    }
}
 
// 3. 缓存系统（FIFO淘汰策略）
class FIFOCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.queue = new LinkedQueue();
    }
    
    get(key) {
        return this.cache.get(key);
    }
    
    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.set(key, value);
        } else {
            if (this.cache.size >= this.capacity) {
                const oldestKey = this.queue.dequeue();
                this.cache.delete(oldestKey);
            }
            
            this.cache.set(key, value);
            this.queue.enqueue(key);
        }
    }
}

5. 综合对比表

数据结构访问搜索插入删除空间复杂度特点
数组O(1)O(n)O(n)O(n)O(n)随机访问，连续内存
链表O(n)O(n)O(1)*O(1)*O(n)动态大小，非连续内存
栈O(n)O(n)O(1)O(1)O(n)LIFO，限制访问
队列O(n)O(n)O(1)O(1)O(n)FIFO，两端操作

*注：链表的插入/删除在已知节点位置时为O(1)

6. 选择指南

何时使用数组：

// 1. 需要随机访问元素
function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;
}
 
// 2. 内存使用效率要求高
// 3. 缓存友好的顺序访问

何时使用链表：

// 1. 频繁插入/删除操作
class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        // 使用双向链表维护访问顺序
        this.head = new DoublyListNode(0);
        this.tail = new DoublyListNode(0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    
    // ... LRU实现
}
 
// 2. 大小动态变化
// 3. 不需要随机访问

何时使用栈：

// 1. 递归问题的迭代解法
// 2. 表达式求值
// 3. 函数调用管理
// 4. 撤销操作（Undo）
class UndoRedoManager {
    constructor() {
        this.undoStack = new ArrayStack();
        this.redoStack = new ArrayStack();
    }
    
    execute(action) {
        action.execute();
        this.undoStack.push(action);
        this.redoStack.clear();
    }
    
    undo() {
        if (!this.undoStack.isEmpty()) {
            const action = this.undoStack.pop();
            action.undo();
            this.redoStack.push(action);
        }
    }
    
    redo() {
        if (!this.redoStack.isEmpty()) {
            const action = this.redoStack.pop();
            action.execute();
            this.undoStack.push(action);
        }
    }
}

何时使用队列：

// 1. BFS算法
// 2. 任务调度
// 3. 缓冲区管理
// 4. 生产者-消费者模式
class ProducerConsumer {
    constructor() {
        this.buffer = new LinkedQueue();
        this.maxSize = 100;
    }
    
    produce(item) {
        if (this.buffer.size() < this.maxSize) {
            this.buffer.enqueue(item);
            return true;
        }
        return false; // 缓冲区满
    }
    
    consume() {
        return this.buffer.dequeue();
    }
}

这四种数据结构各有特色，选择时需要根据具体的使用场景、性能要求和操作特点来决定。