快速掌握Java线性数据结构：数组、链表、栈与队列

非线性数据结构：快速掌握Java非线性数据结构：树(二叉树、平衡二叉树、多路平衡树)、堆、图

概率型数据结构：快速掌握Java概率型数据结构：布隆过滤器

一、引子

数据结构是算法的基石，更是高效解决实际问题的关键工具。本文详解Java中五大核心线性数据结构：数组(Array)、链表(Linked List)、栈(Stack)、队列(Queue)和双端队列(Deque)。通过代码实例、时间复杂度分析和应用场景对比，助你掌握不同场景下的最优选择策略。

二、 数组 (Array)

概念： 数组是最基础且重要的线性数据结构。它在内存中分配连续的存储空间，用于存储相同类型元素的集合。数组通过从0开始的整数索引直接访问任意元素。

Java实现核心： Java 提供了内置的数组语法（int[] arr）以及功能更强大的 java.util.ArrayList 类（基于数组的动态扩容实现）。

  1. 基本数组声明与初始化：

    // 声明并初始化一个固定大小的整型数组
int[] staticArray = new int[5]; // 初始化为默认值0
staticArray[0] = 10; // 赋值
staticArray[1] = 20;

// 声明并直接初始化
String[] names = {"Alice", "Bob", "Charlie"};

  2. ArrayList (动态数组)：

    import java.util.ArrayList;

// 创建一个存储整数的动态数组
ArrayList<Integer> dynamicArray = new ArrayList<>();

// 添加元素 (自动扩容)
dynamicArray.add(10); // O(1) 摊销时间复杂度
dynamicArray.add(20);
dynamicArray.add(1, 15); // 在索引1处插入15, 后续元素后移 O(n)

// 访问元素
int firstElement = dynamicArray.get(0); // O(1)

// 修改元素
dynamicArray.set(1, 25); // O(1)

// 删除元素 (移除索引1处的元素)
dynamicArray.remove(1); // 后续元素前移 O(n)

// 获取大小
int size = dynamicArray.size(); // O(1)

核心操作时间复杂度：

  • 访问 (Access by Index): O(1) - 直接计算内存地址偏移。
  • 搜索 (Search): O(n) - 最坏情况下需要遍历整个数组（无序时）。
  • 插入 (Insertion):
    • 在末尾插入 (add(elem)): O(1) 摊销 (Amortized) - 大多数情况下很快，扩容时O(n)。
    • 在指定索引插入 (add(index, elem)): O(n) - 需要移动后续元素。
  • 删除 (Deletion):
    • 删除末尾元素: O(1)。
    • 删除指定索引元素 (remove(index)): O(n) - 需要移动后续元素。

特点与适用场景：

  • 优点： 随机访问极快；内存连续，缓存友好（Cache Locality）；实现简单。
  • 缺点： 大小固定（基本数组）或扩容有成本（ArrayList）；在非末尾位置插入/删除效率低（需要移动元素）。
  • 典型应用：
    • 存储已知大小或变化不大的数据集。
    • 需要频繁随机访问元素的场景（如通过下标获取）。
    • 作为其他数据结构（如堆、哈希表）的基础实现。
    • 多维数组表示矩阵、图像像素等。

三、 链表 (Linked List)

概念： 链表由一系列结点 (Node) 组成，每个结点包含数据域 (data) 和指向下一个结点地址的指针域 (next)。结点在内存中不必连续存储。链表主要有两种基本形式：单向链表 (Singly Linked List) 和双向链表 (Doubly Linked List)。

Java实现核心： Java 标准库提供了 java.util.LinkedList（基于双向链表）。理解链表原理通常需要手动实现结点类。

  1. 结点类定义 (单向链表)：

    class ListNode<T> {
    T data;           // 存储的数据
    ListNode<T> next; // 指向下一个结点的引用

    ListNode(T data) {
        this.data = data;
        this.next = null;
    }
}

  2. 手动实现链表基本操作示例：

    public class SinglyLinkedList<T> {
    private ListNode<T> head; // 头结点引用
    private int size;

    // 在链表头部插入
    public void addFirst(T data) {
        ListNode<T> newNode = new ListNode<>(data);
        newNode.next = head;
        head = newNode;
        size++;
    } // O(1)

    // 在链表尾部插入 (需遍历找到尾结点)
    public void addLast(T data) {
        ListNode<T> newNode = new ListNode<>(data);
        if (head == null) {
            head = newNode;
        } else {
            ListNode<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    } // O(n)

    // 查找元素 (按值)
    public boolean contains(T data) {
        ListNode<T> current = head;
        while (current != null) {
            if (current.data.equals(data)) {
                return true;
            }
            current = current.next;
        }
        return false;
    } // O(n)

    // 删除第一个匹配项 (按值)
    public boolean remove(T data) {
        if (head == null) return false;
        if (head.data.equals(data)) {
            head = head.next;
            size--;
            return true;
        }
        ListNode<T> prev = head;
        ListNode<T> current = head.next;
        while (current != null) {
            if (current.data.equals(data)) {
                prev.next = current.next;
                size--;
                return true;
            }
            prev = current;
            current = current.next;
        }
        return false;
    } // O(n)
}

  3. 使用 LinkedList：

    import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();

// 添加元素
list.add("Apple"); // 尾部添加 O(1)
list.addFirst("Banana"); // 头部添加 O(1)
list.addLast("Cherry"); // 尾部添加 O(1)
list.add(1, "Orange"); // 指定索引插入 O(n)

// 访问元素
String first = list.getFirst(); // O(1)
String last = list.getLast();   // O(1)
String elem = list.get(2);      // O(n) - 需要遍历

// 删除元素
list.removeFirst(); // O(1)
list.removeLast();  // O(1)
list.remove("Orange"); // O(n) - 按值查找
list.remove(0);        // O(1) - 移除头/尾是O(1), 中间是O(n)

核心操作时间复杂度 (双向链表 LinkedList):

  • 访问 (Access by Index): O(n) - 需要从头或尾（取决于哪个更近）遍历。
  • 搜索 (Search): O(n) - 需要遍历。
  • 插入 (Insertion):
    • 在头部 (addFirst, push): O(1)
    • 在尾部 (addLast, add): O(1)
    • 在指定索引 (add(index, elem)): O(n) - 需要遍历到该位置。
  • 删除 (Deletion):
    • 删除头部 (removeFirst, pop, poll): O(1)
    • 删除尾部 (removeLast): O(1)
    • 删除指定索引 (remove(index)): O(n) - 需要遍历到该位置。
    • 删除指定元素 (remove(Object)): O(n) - 需要查找。

特点与适用场景：

  • 优点： 动态大小，插入/删除操作（尤其在头尾）效率高（O(1)）；不需要连续内存空间。
  • 缺点： 随机访问慢（O(n)）；需要额外空间存储指针；缓存局部性较差。
  • 典型应用：
    • 实现栈、队列、双端队列等抽象数据类型。
    • 需要频繁在列表头部或尾部进行插入/删除的场景。
    • 内存分配管理（如操作系统内存池）。
    • 实现图结构的邻接表表示法。
    • LinkedList 在需要频繁操作头尾或作为队列/栈使用时效率很高。

四、 栈 (Stack)

概念： 栈是一种遵循 后进先出 (Last-In-First-Out, LIFO) 原则的线性数据结构。元素的添加（压栈，Push）和移除（弹栈，Pop）操作都发生在同一端，称为栈顶 (Top)。另一端称为栈底 (Bottom)。

Java实现核心： Java 提供了 java.util.Stack 类（继承自 Vector，线程安全但通常不推荐），更常用的是 java.util.Deque 接口的实现类（如 ArrayDeque, LinkedList）来模拟栈，因为它们提供了更高效和一致的 API。

  1. 使用 Deque 作为栈 (推荐)：

    import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> stack = new ArrayDeque<>(); // 通常用ArrayDeque, 效率高

// 压栈 (Push)
stack.push(10); // 或 stack.addFirst(10)
stack.push(20);
stack.push(30);

// 查看栈顶元素 (Peek) - 不移除
int top = stack.peek(); // 返回30, 栈不变
System.out.println("Top element: " + top);

// 弹栈 (Pop) - 移除并返回栈顶元素
int popped = stack.pop(); // 返回30并移除
System.out.println("Popped: " + popped);

// 检查栈是否为空
boolean isEmpty = stack.isEmpty(); // false

// 获取栈大小
int size = stack.size(); // 2

  2. 使用 Stack 类 (了解)：

    import java.util.Stack;

Stack<String> legacyStack = new Stack<>();
legacyStack.push("Java");
legacyStack.push("Python");
String topLang = legacyStack.peek(); // "Python"
String removedLang = legacyStack.pop(); // "Python"

核心操作时间复杂度 (ArrayDeque/LinkedList):

  • 压栈 (Push): O(1) 摊销 (ArrayDeque) / O(1) (LinkedList)
  • 弹栈 (Pop): O(1) (ArrayDeque / LinkedList)
  • 查看栈顶 (Peek): O(1) (ArrayDeque / LinkedList)
  • 判空 (isEmpty): O(1)
  • 大小 (Size): O(1)

特点与适用场景：

  • 优点： LIFO 特性简单直观；核心操作高效。
  • 缺点： 只能访问栈顶元素；随机访问受限。
  • 典型应用：
    • 函数调用栈： 存储函数调用信息（参数、返回地址、局部变量）。
    • 表达式求值： 中缀表达式转后缀表达式，后缀表达式求值。
    • 括号匹配： 检查代码中括号(), [], {}是否成对且嵌套正确。
    • 浏览器历史记录： 后退功能。
    • 撤销 (Undo) 操作： 将操作压栈，撤销时弹栈执行逆操作。
    • 深度优先搜索 (DFS)： 图的遍历算法。

五、 队列 (Queue)

概念： 队列是一种遵循 先进先出 (First-In-First-Out, FIFO) 原则的线性数据结构。元素从队尾 (Rear/Tail) 添加（入队，Enqueue），从队头 (Front/Head) 移除（出队，Dequeue）。

Java实现核心： Java 提供了 java.util.Queue 接口。常用实现类有：

  • LinkedList: 基于链表，支持所有队列操作。
  • ArrayDeque: 基于可扩容数组，也可高效实现队列（以及栈）。
  • PriorityQueue: 基于堆，实现优先级队列（非标准FIFO）。
  1. 使用 Queue 接口 (LinkedList/ArrayDeque): 
    import java.util.LinkedList;
import java.util.Queue;

Queue<String> queue = new LinkedList<>(); // 或 new ArrayDeque<>()

// 入队 (Enqueue/Offer)
queue.offer("Task1"); // 或 queue.add("Task1")
queue.offer("Task2");
queue.offer("Task3");

// 查看队头元素 (Peek) - 不移除
String head = queue.peek(); // 返回"Task1"
System.out.println("Head of queue: " + head);

// 出队 (Dequeue/Poll) - 移除并返回队头元素
String processedTask = queue.poll(); // 返回"Task1"并移除
System.out.println("Processed: " + processedTask);

// 检查队列是否为空
boolean isEmpty = queue.isEmpty(); // false

// 获取队列大小
int size = queue.size(); // 2

核心操作时间复杂度 (LinkedList/ArrayDeque):

  • 入队 (Offer/Add): O(1) 摊销 (ArrayDeque) / O(1) (LinkedList)
  • 出队 (Poll/Remove): O(1) (ArrayDeque / LinkedList)
  • 查看队头 (Peek/Element): O(1) (ArrayDeque / LinkedList)
  • 判空 (isEmpty): O(1)
  • 大小 (Size): O(1)

特点与适用场景：

  • 优点： FIFO 特性公平；核心操作高效。
  • 缺点： 只能访问队头和队尾（需特定实现如 Deque）；随机访问受限。
  • 典型应用：
    • 任务调度： 操作系统进程调度、线程池任务队列。
    • 消息传递： 消息队列系统（如 RabbitMQ, Kafka 的核心抽象）。
    • 广度优先搜索 (BFS)： 图的遍历算法。
    • 打印任务队列： 多台打印机共享一个打印队列。
    • 缓冲区 (Buffering)： 数据流传输中的临时存储（如 IO 缓冲区、网络数据包队列）。
    • 模拟现实排队： 银行柜台、超市收银台。

六、 双端队列 (Deque - Double Ended Queue)

概念： 双端队列是栈和队列的结合体。它允许在队头 (Front/Head) 和队尾 (Rear/Tail) 两端高效地进行元素的插入和删除操作。因此，它既可以作为栈使用（只操作一端），也可以作为队列使用（一端入队，另一端出队），或者同时利用两端进行操作。

Java实现核心： Java 提供了 java.util.Deque 接口。主要实现类：

  • ArrayDeque: 基于可扩容循环数组，通常是性能最佳的选择（尤其用作栈或普通队列时）。
  • LinkedList: 基于双向链表，也实现了 Deque。
  1. 使用 Deque： 
    import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> deque = new ArrayDeque<>();

// 在队尾操作 (类似Queue)
deque.offerLast(10); // 入队尾 (等价于queue.offer())
deque.offerLast(20);
int last = deque.peekLast(); // 查看队尾: 20
int removedLast = deque.pollLast(); // 出队尾: 20 (类似栈的pop)

// 在队头操作
deque.offerFirst(5); // 入队头
int first = deque.peekFirst(); // 查看队头: 5
int removedFirst = deque.pollFirst(); // 出队头: 5 (类似队列的poll)

// 同时作为栈使用 (推荐用push/pop操作队头)
deque.push(30); // 等价于 offerFirst(30)
int top = deque.peek(); // 等价于 peekFirst() -> 30
int popped = deque.pop(); // 等价于 pollFirst() -> 30

// 同时作为队列使用 (推荐用offer/poll/peek操作队尾入队头出)
deque.offer(40); // 等价于 offerLast(40)
int head = deque.peek(); // 等价于 peekFirst() -> 40 (队头)
int processed = deque.poll(); // 等价于 pollFirst() -> 40

核心操作时间复杂度 (ArrayDeque):

  • 在队头/队尾插入/删除/查看: O(1) 摊销。

特点与适用场景：

  • 优点： 操作灵活，两端高效；可替代栈和普通队列。
  • 缺点： 随机访问仍是 O(n)。
  • 典型应用：
    • 需要同时用到栈和队列特性的场景。
    • 滑动窗口算法（如求滑动窗口最大值）。
    • 实现撤销/重做 (Undo/Redo) 功能（通常需要两个栈，用双端队列模拟更灵活）。
    • 工作窃取算法 (Work-Stealing Algorithm) 中的任务队列。

七、 总结

  1. 核心特性对比

    结构 访问 插入/删除 特点 典型场景
    数组 O(1) 末尾O(1), 中间O(n) 内存连续、缓存友好 随机访问、固定数据集
    链表 O(n) 头尾O(1), 中间O(n) 动态内存、指针开销 频繁头尾操作、队列/栈基础
    栈 仅栈顶 O(1) LIFO后进先出 函数调用、括号匹配
    队列 仅队头 O(1) FIFO先进先出 任务调度、BFS算法
    双端队列 仅两端 头尾O(1) 栈+队列融合体 滑动窗口、工作窃取

  2. 选择原则

    • 需随机访问 → 选择数组（或ArrayList）
    • 需频繁插入删除 → 链表（尤其头尾操作）
    • 需LIFO逻辑（回溯/撤销） → 栈
    • 需FIFO逻辑（任务排队） → 队列
    • 需两端操作 → 双端队列（ArrayDeque最优）

  3. Java库最佳实践

    • 动态数组 → ArrayList
    • 链表操作 → LinkedList
    • 栈/队列 → 优先使用ArrayDeque（效率高于Stack和LinkedList）
    • 线程安全 → ConcurrentLinkedDeque或ArrayBlockingQueue

只有深度掌握数据结构，才能构建出高效、优雅的算法解决方案。

# 算法 # 数据结构 # java # java-ee # 链表
Logo
长沙城市开发者社区

惟楚有才，于斯为盛。欢迎来到长沙！！！ 茶颜悦色、臭豆腐、CSDN和你一个都不能少~

更多推荐

cover

2025 科技前沿全景：从量子突破到星际凝望的文明跃迁

avatar 长沙城市开发者社区

Maple Mono多语言支持：简繁中日字符集兼容

在当今全球化开发环境中，开发者经常需要处理包含简体中文、繁体中文、日文和英文的混合代码。传统等宽字体往往无法完美支持这种多语言场景，导致：- 中英文字符宽度比例失调，表格对齐困难- 标点符号显示不一致，影响代码可读性- 特殊符号和连字功能在多语言环境下失效- 终端图标与中文字符兼容性问题Maple Mono字体通过创新的技术方案，彻底解决了这些痛点，为多语言开发者提供了完美的字体...

avatar 长沙城市开发者社区

Graphite直方图分析：图形色彩分布的视觉化工具

还在为图像色彩分布不均衡而烦恼？想要精确掌握图像中的色彩构成却无从下手？Graphite的直方图分析功能为你提供了一套完整的色彩分布视觉化解决方案，让你能够深入理解图像的色彩特性并进行精准的色彩调整。## 什么是直方图分析？直方图（Histogram）是数字图像处理中用于表示像素值分布的重要工具。在Graphite中，直方图分析能够：- **可视化色彩分布**：直观展示RGB各通道的像...

avatar 长沙城市开发者社区