数据结构核心总结：线性表、链表、栈与队列 🚀

数据结构是计算机存储、组织数据的方式。好的数据结构能够显著提升程序的运行效率。本文将系统总结线性表、链表、栈和队列这四种最基础且应用最广泛的数据结构，帮助你建立完整的知识体系。

---

📖 目录

1. 线性表基础
2. 顺序表与链表
3. 单向链表
4. 双向链表与循环链表
5. 栈
6. 队列
7. 总结对比

---

线性表基础

什么是线性表？

线性表（Linear List） 是由 n 个具有相同特性的数据元素组成的有序序列。它是数据结构中最简单、最基本的一种结构。

线性表的基本特征：

• 存在唯一的”第一个”元素
• 存在唯一的”最后一个”元素
• 除第一个元素外，每个元素都有且仅有一个前驱元素
• 除最后一个元素外，每个元素都有且仅有一个后继元素

线性表的抽象数据类型

线性表的操作主要包括：

操作	说明
initList()	初始化线性表
length()	获取线性表长度
get(i)	获取第 i 个位置的元素
insert(i, e)	在第 i 个位置插入元素 e
delete(i)	删除第 i 个位置的元素
isEmpty()	判断线性表是否为空
clear()	清空线性表

---

顺序表与链表

线性表有两种主要的存储方式：顺序存储和链式存储。

顺序表（Sequential List）

顺序表使用一段连续的存储单元依次存储线性表中的元素。

优点：

• 🔥 随机访问能力强，查询速度快（时间复杂度 O(1)）
• 🔥 缓存命中率高，因为内存连续

缺点：

• ❌ 插入和删除操作需要移动大量元素（时间复杂度 O(n)）
• ❌ 存储空间固定，大小受限制
• ❌ 需要预先分配足够的连续内存空间

链表（Linked List）

链表通过指针将一系列元素连接起来，每个元素包含数据域和指针域。

优点：

• ✅ 插入和删除操作不需要移动元素（时间复杂度 O(1)）
• ✅ 不需要预先分配固定大小的空间
• ✅ 可以动态扩展

缺点：

• ❌ 不支持随机访问，查询需要遍历（时间复杂度 O(n)）
• ❌ 每个元素需要额外的指针空间
• ❌ 缓存命中率较低

---

单向链表

单向链表结构

单向链表（Singly Linked List）是链表中最简单的一种，每个节点包含数据域和指向下一个节点的指针。

Java 实现单向链表

/**
 * 单向链表节点
 */
class Node<E> {
    E data;       // 数据域
    Node<E> next; // 指针域，指向下一个节点

    public Node(E data) {
        this.data = data;
        this.next = null;
    }
}

/**
 * 单向链表实现
 */
public class SinglyLinkedList<E> {
    private Node<E> head; // 头节点
    private int size;     // 链表长度

    public SinglyLinkedList() {
        this.head = new Node<>(null); // 虚拟头节点
        this.size = 0;
    }

    /**
     * 在链表头部添加元素
     * 时间复杂度：O(1)
     */
    public void addFirst(E element) {
        Node<E> newNode = new Node<>(element);
        newNode.next = head.next;
        head.next = newNode;
        size++;
    }

    /**
     * 在链表尾部添加元素
     * 时间复杂度：O(n)
     */
    public void addLast(E element) {
        Node<E> newNode = new Node<>(element);
        Node<E> current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        size++;
    }

    /**
     * 在指定位置插入元素
     * 时间复杂度：O(n)
     */
    public void add(int index, E element) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> newNode = new Node<>(element);
        Node<E> current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        newNode.next = current.next;
        current.next = newNode;
        size++;
    }

    /**
     * 删除指定位置的元素
     * 时间复杂度：O(n)
     */
    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        Node<E> removedNode = current.next;
        current.next = removedNode.next;
        size--;
        return removedNode.data;
    }

    /**
     * 获取指定位置的元素
     * 时间复杂度：O(n)
     */
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<E> current = head.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    /**
     * 链表长度
     */
    public int size() {
        return size;
    }

    /**
     * 判断链表是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }
}

单向链表操作图解

---

双向链表与循环链表

双向链表

双向链表（Doubly Linked List）的每个节点包含数据域、前驱指针和后继指针。

双向链表 Java 实现

/**
 * 双向链表节点
 */
class DNode<E> {
    E data;
    DNode<E> prev; // 前驱指针
    DNode<E> next; // 后继指针

    public DNode(E data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

/**
 * 双向链表实现
 */
public class DoublyLinkedList<E> {
    private DNode<E> head; // 头节点
    private DNode<E> tail; // 尾节点
    private int size;

    public DoublyLinkedList() {
        this.head = new DNode<>(null);
        this.tail = new DNode<>(null);
        this.head.next = tail;
        this.tail.prev = head;
        this.size = 0;
    }

    /**
     * 在头部添加元素
     */
    public void addFirst(E element) {
        DNode<E> newNode = new DNode<>(element);
        newNode.next = head.next;
        newNode.prev = head;
        head.next.prev = newNode;
        head.next = newNode;
        size++;
    }

    /**
     * 在尾部添加元素
     */
    public void addLast(E element) {
        DNode<E> newNode = new DNode<>(element);
        newNode.next = tail;
        newNode.prev = tail.prev;
        tail.prev.next = newNode;
        tail.prev = newNode;
        size++;
    }

    /**
     * 删除指定节点
     */
    public void remove(DNode<E> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }
}

循环链表

循环链表（Circular Linked List）是链表的一种变形，最后一个节点的指针指向头节点，形成环状结构。

循环链表的特点：

• 🔄 没有 null 指针，所有节点形成闭环
• 🔄 从任意节点出发，都可以遍历整个链表
• 🔄 常用于需要循环遍历的场景（如约瑟夫问题）

---

栈

什么是栈？

栈（Stack） 是一种特殊的线性表，它遵循 LIFO（Last In First Out） 原则——后进先出。

栈的基本操作

操作	说明	时间复杂度
push(e)	将元素压入栈顶	O(1)
pop()	弹出栈顶元素	O(1)
peek()	查看栈顶元素	O(1)
isEmpty()	判断栈是否为空	O(1)
size()	获取栈的大小	O(1)

Java 栈实现

/**
 * 栈接口
 */
public interface Stack<E> {
    void push(E element);  // 压栈
    E pop();               // 弹栈
    E peek();              // 查看栈顶
    int size();            // 大小
    boolean isEmpty();     // 是否为空
}

/**
 * 基于数组的栈实现
 */
public class ArrayStack<E> implements Stack<E> {
    private Object[] elements;
    private int top;           // 栈顶指针
    private int capacity;      // 栈容量

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
        this.top = -1;
    }

    @Override
    public void push(E element) {
        if (top >= capacity - 1) {
            throw new StackOverflowError("Stack is full!");
        }
        elements[++top] = element;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty!");
        }
        return (E) elements[top--];
    }

    @Override
    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty!");
        }
        return (E) elements[top];
    }

    @Override
    public int size() {
        return top + 1;
    }

    @Override
    public boolean isEmpty() {
        return top == -1;
    }
}

栈的应用场景

典型应用：

1. 函数调用栈 - 程序语言的函数调用管理
2. 括号匹配 - 检验表达式中的括号是否合法
3. 表达式求值 - 中缀表达式转后缀表达式
4. 深度优先搜索（DFS） - 图和树的遍历

括号匹配实例

/**
 * 有效的括号匹配
 */
public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);  // 左括号入栈
        } else {
            if (stack.isEmpty()) {
                return false;  // 没有左括号可以匹配
            }
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;  // 括号不匹配
            }
        }
    }
    
    return stack.isEmpty();  // 栈空说明完全匹配
}

---

队列

什么是队列？

队列（Queue） 是一种特殊的线性表，它遵循 FIFO（First In First Out） 原则——先进先出。

队列的基本操作

操作	说明	时间复杂度
enqueue(e)	将元素加入队尾	O(1)
dequeue()	移除队首元素	O(1)
front()	查看队首元素	O(1)
rear()	查看队尾元素	O(1)
isEmpty()	判断队列是否为空	O(1)

Java 队列实现

/**
 * 队列接口
 */
public interface Queue<E> {
    void enqueue(E element);  // 入队
    E dequeue();              // 出队
    E front();                // 查看队首
    boolean isEmpty();        // 是否为空
    int size();               // 大小
}

/**
 * 基于数组的循环队列实现
 */
public class CircularQueue<E> implements Queue<E> {
    private Object[] elements;
    private int front;        // 队首指针
    private int rear;         // 队尾指针
    private int capacity;     // 队列容量
    private int size;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.elements = new Object[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    @Override
    public void enqueue(E element) {
        if (size == capacity) {
            throw new IllegalStateException("Queue is full!");
        }
        elements[rear] = element;
        rear = (rear + 1) % capacity;
        size++;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty!");
        }
        E element = (E) elements[front];
        front = (front + 1) % capacity;
        size--;
        return element;
    }

    @Override
    @SuppressWarnings("unchecked")
    public E front() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty!");
        }
        return (E) elements[front];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int size() {
        return size;
    }
}

循环队列原理图

队列的应用场景

典型应用：

1. 任务调度 - 操作系统中的进程/线程调度
2. 广度优先搜索（BFS） - 图和树的层级遍历
3. 消息队列 - 异步通信、流量削峰
4. 缓存策略 - LRU、LFU 等缓存算法

BFS 遍历实例

/**
 * 使用队列实现二叉树层序遍历
 */
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        result.add(level);
    }
    
    return result;
}

---

总结对比

四种数据结构对比

复杂度对比表

数据结构	访问	插入	删除	空间
顺序表	O(1)	O(n)	O(n)	O(n)
单向链表	O(n)	O(1)*	O(1)*	O(n)
双向链表	O(n)	O(1)*	O(1)*	O(n)
栈	-	O(1)	O(1)	O(n)
队列	-	O(1)	O(1)	O(n)

*注：O(1) 的前提是已经找到目标位置，否则需要 O(n) 的查找时间。

选择建议

选择要点：

• 🔥 查询多、修改少 → 选择 ArrayList（顺序表）
• 🔥 插入删除多、查询少 → 选择 LinkedList（链表）
• 🔥 需要 LIFO → 选择 Stack
• 🔥 需要 FIFO → 选择 Queue

---

📚 最后

线性表、链表、栈、队列是数据结构中最基础的概念，看似简单，却支撑着整个计算机世界的运行。理解它们的原理和适用场景，是成为优秀程序员的必经之路。

希望本文对你有所帮助！如果有任何问题，欢迎留言讨论 💬

---

原创不易，转载请注明出处！