数据结构之线性结构

数据结构之线性结构：从基础概念到实现细节

线性结构是数据结构中最基础也最常用的一类，其核心特征是数据元素之间存在一对一的线性关系。常见的线性结构包括线性表（顺序表、链表）、队列、栈等。它们在逻辑上形成一条 “直线”，每个元素（除首尾外）有唯一的前驱和后继。

线性结构的核心特征

线性结构的元素间关系可概括为：

• 存在唯一的 “首元素”（第一个元素）和 “尾元素”（最后一个元素）。
• 除首元素外，每个元素有且仅有一个 “前驱”（前一个元素）。
• 除尾元素外，每个元素有且仅有一个 “后继”（后一个元素）。

这种结构使得数据的遍历可以按线性顺序依次进行（如从首到尾）。

线性表：线性结构的基础

线性表是由零个或多个数据元素组成的有限序列，是线性结构的抽象模型。根据存储方式的不同，线性表可分为顺序表（顺序存储）和链表（链式存储）。

1. 顺序表（Sequential List）

顺序表是用连续的存储空间存储元素的线性表，逻辑上的顺序与物理存储顺序一致（类似数组）。

实现原理

• 底层依赖数组，元素在内存中连续排列，通过下标直接访问。
• 容量固定（可动态扩容），元素个数（size）≤ 容量（capacity）。

核心操作及时间复杂度

操作	实现逻辑	时间复杂度
访问（get）	通过下标直接定位元素	O(1)
插入（add）	若插入中间位置，需移动后续元素腾出空间	O(n)
删除（remove）	若删除中间元素，需移动后续元素填补空位	O(n)
扩容（ensureCapacity）	复制原数组到更大的新数组	O (n)（触发时）

优缺点

• 优点：
  • 访问速度快（O (1)），适合频繁查询的场景。
  • 无需额外存储指针，空间利用率高。
• 缺点：
  • 插入 / 删除需移动大量元素，效率低（O (n)）。
  • 初始容量难以确定，过小易溢出，过大浪费空间。

代码示例解析（Java）

public class ShunXuBiao<T> {
    private Object[] array; // 存储元素的数组
    private int size; // 当前元素个数
    private int capacity; // 容量

    // 初始化容量
    public ShunXuBiao(int capacity) {
        this.array = new Object[capacity];
        this.size = 0;
        this.capacity = capacity;
    }

    // 添加元素到末尾
    public void add(T element) {
        ensureCapacity(); // 检查扩容
        array[size++] = element; // 直接存到尾部，O(1)
    }

    // 在指定位置插入元素
    public void add(int index, T element) {
        ensureCapacity();
        // 从index开始，后续元素后移一位（O(n)）
        for (int i = size - 1; i >= index; i--) {
            array[i + 1] = array[i];
        }
        array[index] = element;
        size++;
    }

    // 删除指定位置元素
    public void remove(int index) {
        // 从index+1开始，元素前移一位（O(n)）
        for (int i = index; i < size - 1; i++) {
            array[i] = array[i + 1];
        }
        array[size - 1] = null;
        size--;
    }

    // 动态扩容（容量翻倍）
    private void ensureCapacity() {
        if (size >= capacity) {
            capacity *= 2;
            array = Arrays.copyOf(array, capacity); // 复制数组，O(n)
        }
    }
}

2. 链表（Linked List）

链表是用非连续的存储空间存储元素的线性表，元素（节点）通过指针（引用）关联，形成逻辑上的顺序。

节点结构

每个节点包含两部分：

• data：存储元素值。
• next：指向后继节点的引用（单链表）；双向链表还包含 prev（指向前驱节点）。

常见类型

• 单链表：每个节点仅含 next 指针，尾节点 next 为 null。
• 双向链表：每个节点含 prev 和 next 指针，可双向遍历。
• 循环链表：尾节点 next 指向头节点，形成环，可从任一节点遍历全表。

核心操作及时间复杂度

操作	实现逻辑	时间复杂度
访问（get）	从表头遍历到目标位置	O(n)
插入（add）	找到插入位置，修改前后节点的指针	O (1)（已知位置时）
删除（remove）	找到删除位置，修改前后节点的指针	O (1)（已知位置时）

优缺点

• 优点：
  • 插入 / 删除效率高（O (1)，已知位置时），无需移动元素。
  • 无需预分配空间，元素个数可动态增长。
• 缺点：
  • 访问效率低（O (n)），需从头遍历。
  • 每个节点需额外存储指针，空间开销略大。

单链表代码示例解析（Java）

public class LianBiao<E> {
    // 节点内部类
    private static class Node<E> {
        E data; // 元素值
        Node<E> next; // 后继节点引用

        Node(E data) {
            this.data = data;
        }
    }

    private Node<E> head; // 头节点
    private int size; // 元素个数

    // 添加元素到末尾
    public void addElement(E element) {
        Node<E> newNode = new Node<>(element);
        if (head == null) { // 空链表，新节点作为头节点
            head = newNode;
        } else {
            Node<E> temp = head;
            while (temp.next != null) { // 遍历到尾节点（O(n)）
                temp = temp.next;
            }
            temp.next = newNode; // 尾节点指向新节点
        }
        size++;
    }

    // 删除指定索引的节点
    public void deleteElement(int index) {
        if (index == 0) { // 删除头节点
            head = head.next;
        } else {
            Node<E> prev = head;
            // 找到前驱节点（O(n)）
            for (int i = 1; i < index; i++) {
                prev = prev.next;
            }
            prev.next = prev.next.next; // 跳过目标节点
        }
        size--;
    }

    // 获取指定索引的元素
    public E getElement(int index) {
        Node<E> temp = head;
        for (int i = 0; i < index; i++) { // 遍历到目标节点（O(n)）
            temp = temp.next;
        }
        return temp.data;
    }
}

顺序表 vs 链表：关键对比

维度	顺序表	链表
存储方式	连续内存数组	非连续节点 + 指针
访问效率	O (1)（下标直接访问）	O (n)（需遍历）
插入 / 删除效率	O (n)（需移动元素）	O (1)（已知位置时）
空间利用率	无额外开销，但可能浪费空间	需存储指针，空间开销略大
动态扩容	需要复制数组（O (n)）	无需扩容，动态增长

队列（Queue）：先进先出的线性表

队列是仅允许在一端插入、另一端删除的特殊线性表，遵循 “先进先出（FIFO，First In First Out）” 原则。

核心概念

• 队尾（rear）：允许插入元素的一端。
• 队头（front）：允许删除元素的一端。
• 空队列：不含任何元素的队列。

基本操作

• 入队（enqueue）：在队尾添加元素。
• 出队（dequeue）：从队头移除元素。
• peek ：查看队头元素（不删除）。

实现方式

• 顺序队列：基于数组实现，需处理 “假溢出”（可通过循环队列优化）。
• 链式队列：基于链表实现，队头为头节点，队尾为尾节点。

应用场景

• 任务调度（如线程池任务队列）。
• 缓冲处理（如 IO 缓冲区）。
• 广度优先搜索（BFS）。

栈（Stack）：后进先出的线性表

栈是仅允许在一端插入和删除的特殊线性表，遵循 “后进先出（LIFO，Last In First Out）” 原则。

核心概念

• 栈顶（top）：允许插入和删除的一端。
• 栈底（bottom）：固定的一端，不允许操作。
• 空栈：不含任何元素的栈。

基本操作

• 入栈（push）：在栈顶添加元素。
• 出栈（pop）：从栈顶移除元素。
• peek ：查看栈顶元素（不删除）。

实现方式

• 顺序栈：基于数组实现，栈顶指针跟踪栈顶位置。
• 链式栈：基于链表实现，栈顶为头节点。

应用场景

• 函数调用（调用栈）。
• 表达式求值（后缀表达式）。
• 括号匹配校验。
• 深度优先搜索（DFS）