背景

本文是《Java 后端从小白到大神》修仙系列第四篇，正式进入Java后端世界，本篇文章主要聊Java基础中的数据结构。若想详细学习请点击首篇博文，我们开始吧。

章节概览

  1. 数组
  2. 链表

1. 数组（Array）

数组是Java中最基本的数据结构，用于存储固定大小的同类型元素，是其他高级数据结构的基础。

1. 普通数组

描述：数组是Java中的一种线性数据结构，用于存储固定大小的同类型元素，属于Java语言的内置类型，不属于Java集合框架（Java Collections Framework）。

  • 特点：
    • 内存连续：元素在内存中连续分配，支持快速随机访问（时间复杂度O(1)）。
    • 固定长度：数组长度在初始化时确定，不可动态扩容。
    • 支持基本类型：可以存储int、char等基本数据类型，而集合框架只能存储对象（需装箱，如Integer）。
    • 轻量高效：无需额外对象封装，内存占用和性能优于集合类（如ArrayList）。

代码示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 1. 声明并初始化数组
int[] intArray = new int[3];       // 默认值 [0, 0, 0]
String[] strArray = {"A", "B", "C"};

// 2. 访问和修改元素
intArray[0] = 10;
System.out.println(intArray[0]);   // 输出 10

// 3. 遍历数组
for (int i = 0; i < strArray.length; i++) { // 数组从0开始，自然从0循环
    System.out.println(strArray[i]); // 输出 A B C
}

// 4. 多维数组（以二维为例）
int[][] matrix = {{1, 2}, {3, 4}};
System.out.println(matrix[1][0]);  // 输出 3

实际应用场景：

  • 数值计算：存储和处理大量数值数据
  • 图像处理：存储像素数据
  • 矩阵运算：线性代数中的矩阵操作
  • 固定长度数据：如月份名称、星期几等

与集合框架的对比：

特性 数组 集合类（如ArrayList）
长度 固定，不可变 动态扩容
元素类型 支持基本类型和对象 仅支持对象（需装箱/拆箱）
功能方法 无内置方法（需手动实现遍历、排序） 提供丰富方法（如add(), remove()）
线程安全 无 部分集合类线程安全（如Vector）
内存占用 低 高
访问速度 快 稍慢

为什么数组不在Java集合框架中？ Java集合框架（JCF）设计目标是提供动态大小、对象存储和丰富操作的容器类，而数组作为语言内置类型，更注重底层效率和基本类型支持。两者互为补充：

  • 若需动态扩容或功能方法，优先选集合类（如ArrayList）。
  • 若需高性能或存储基本类型，优先选数组。

数组操作的常见问题：

  1. 数组越界异常：访问超出数组长度的索引
  2. 空指针异常：数组未初始化就使用
  3. 内存浪费：分配的数组空间未完全使用

代码示例：数组排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 冒泡排序
int[] arr = {5, 2, 8, 3, 1};
for (int i = 0; i < arr.length - 1; i++) {
    for (int j = 0; j < arr.length - i - 1; j++) {
        if (arr[j] > arr[j + 1]) {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}

// 使用Arrays工具类排序
import java.util.Arrays;
int[] arr = {5, 2, 8, 3, 1};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr)); // 输出 [1, 2, 3, 5, 8]

总结：

  • 数组是Java核心数据结构，适合固定长度、高性能场景。
  • 集合框架（如List/Set/Map）提供动态操作和高级功能。
  • 根据需求选择：
    • 基本类型 + 固定长度 → 数组
    • 对象存储 + 动态操作 → 集合类

2. 动态数组

在 Java 中，动态数组的实现通常指 ArrayList 类，它是基于数组的动态扩容数据结构，能够自动调整底层数组的容量以适应元素的增减。与普通数组（固定长度）不同，动态数组在需要时会自动扩展内存空间，提供了更灵活的数据存储方式。

动态数组的核心机制：

  • 1. 底层依赖数组

    • ArrayList 内部维护一个 Object[] elementData 数组存储元素。
    • 初始容量默认为 10（无参构造时），也可通过构造函数指定初始容量。

  • 2. 自动扩容

    • 触发条件：当添加元素时，如果当前数组已满（size == capacity），触发扩容。
    • 扩容规则：
      • 新容量 = 旧容量 * 1.5（即 1.5 倍增长）。
      • 若新容量仍不足，直接取所需的最小容量。
    • 扩容步骤：
      1. 创建新数组（大小为计算后的新容量）。
      2. 将旧数组元素复制到新数组（Arrays.copyOf）。
      3. 更新内部数组引用为新数组。

  • 3. 缩容机制

    • ArrayList 不会自动缩小底层数组的容量。
    • 可通过 trimToSize() 手动将容量调整为当前元素数量，释放未使用的内存。

代码示例与解析：

  • 1. 添加元素与扩容

    1
2
3
4
5
6

    ArrayList<Integer> list = new ArrayList<>(); // 初始容量为10
for (int i = 0; i < 15; i++) {
    list.add(i); 
    // 第11次添加时触发扩容：容量从10 → 15（10*1.5）
    // 第16次添加时再次扩容：15 → 22（15*1.5）
}

  • 2. 源码关键逻辑（简化版）

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

    public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 确保容量足够
    elementData[size++] = e; // 添加元素到末尾
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity); // 触发扩容
    }
}

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 计算新容量（1.5倍）
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity; // 直接使用所需的最小容量
    }
    elementData = Arrays.copyOf(elementData, newCapacity); // 复制旧数据到新数组
}

实际应用场景：

  • 动态数据管理：元素数量不确定的场景
  • 频繁访问：需要快速随机访问的场景
  • 集合操作：需要使用集合框架提供的丰富方法
  • 与其他集合交互：与Java集合框架的其他组件配合使用

动态数组的优缺点:

优点 缺点
快速随机访问：通过索引访问元素（时间复杂度 O(1)） 插入/删除效率低：中间位置操作需移动元素（平均时间复杂度 O(n)）
内存紧凑：元素连续存储，缓存友好 扩容成本高：频繁扩容会导致内存复制开销
动态调整容量：无需手动管理内存 内存浪费：预留的未使用容量可能占用额外空间
丰富的方法：提供大量便捷的操作方法 线程不安全：多线程环境下需要额外同步

动态数组 vs 普通数组:

特性 动态数组（ArrayList） 普通数组（int[]）
容量调整 自动扩容 无法扩容
元素类型 仅支持对象 支持基本类型和对象
功能方法 丰富的操作方法 无内置方法
内存占用 较高 较低
适用场景 动态数据，频繁访问 固定大小，高性能需求

使用建议：

  1. 预估容量：如果知道大致元素数量，构造时指定初始容量，减少扩容次数
  2. 及时缩容：当元素数量大幅减少时，使用 trimToSize() 释放内存
  3. 避免频繁插入删除：在需要频繁插入删除的场景，考虑使用 LinkedList
  4. 线程安全：多线程环境下，使用 Collections.synchronizedList() 或 CopyOnWriteArrayList

代码示例：ArrayList的常见操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// 创建并初始化
ArrayList<String> list = new ArrayList<>();

// 添加元素
list.add("Apple");
list.add("Banana");
list.add(1, "Orange"); // 在指定位置插入

// 访问元素
String first = list.get(0);

// 修改元素
list.set(0, "Red Apple");

// 删除元素
list.remove(1);
list.remove("Banana");

// 遍历
for (String fruit : list) {
    System.out.println(fruit);
}

// 其他常用方法
list.size(); // 元素数量
list.contains("Apple"); // 是否包含元素
list.clear(); // 清空列表
list.isEmpty(); // 是否为空

2.链表（Linked List）

链表是一种重要的线性数据结构，由一系列节点通过指针连接组成，适合频繁插入删除操作的场景。

描述：是一种线性数据结构，由一系列节点（Node）通过指针连接组成。每个节点包含数据域和指针域（指向下一个或前一个节点）。

链表的核心特点：

  1. 动态内存分配：无需预先分配固定内存空间，可动态增删节点。
  2. 非连续存储：节点在内存中离散分布，通过指针链接。
  3. 高效插入/删除：时间复杂度为 O(1)（已知节点位置时）。
  4. 低效随机访问：必须从头节点遍历，时间复杂度为 O(n)。

链表的分类：

1. 单链表

  • 结构：单链表（Singly Linked List）每个节点包含数据域和指向下一节点的指针。

  • 操作特点：

    • 只能单向遍历（从头到尾）。
    • 插入/删除需维护前驱节点的指针。

  • 代码示例：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

      // 单链表节点定义
  class Node<T> {
      T data;
      Node<T> next;
      public Node(T data) {
          this.data = data;
          this.next = null;
      }
  }

  // 正序打印链表
  public static <T> void printLinkedList(Node<T> node) {
      Node<T> cur = node;
      while (cur != null) {
          System.out.print(cur.data + (cur.next == null ? "" : " -> "));
          cur = cur.next;
      }
      System.out.println();
  }

  // 先打印、后递归 → 正序；
  // 先递归、后打印 → 逆序；
  public static <T> void printRecursive(Node<T> node) {
      if (node == null) {
          System.out.println("NULL");
          return;
      }
      System.out.print(node.data + " -> ");
      printRecursive(node.next); // 递归调用
      // System.out.print(node.data + " -> "); // 逆序打印
  }

// 单链表操作示例
  public static void main(String[] args) {
      // 构建链表：1 -> 2 -> 3
      Node<Integer> head = new Node<>(1);
      head.next = new Node<>(2);
      head.next.next = new Node<>(3);

      // 打印链表
      printLinkedList(head); // 输出：1 -> 2 -> 3
      // 递归打印
      printRecursive(head); // 1 -> 2 -> 3 -> NULL
  }

单链表常见操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// 插入节点到链表头部
public static <T> Node<T> insertAtHead(Node<T> head, T data) {
    Node<T> newNode = new Node<>(data);
    newNode.next = head;
    return newNode;
}

// 插入节点到链表尾部
public static <T> Node<T> insertAtTail(Node<T> head, T data) {
    Node<T> newNode = new Node<>(data);
    if (head == null) {
        return newNode;
    }
    Node<T> current = head;
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
    return head;
}

// 删除指定值的节点
public static <T> Node<T> deleteNode(Node<T> head, T value) {
    // 1. 边界条件：空链表，直接返回null（没的删）
    if (head == null) return null;
    
    // 2. 特殊场景：要删的是头节点
    if (head.data.equals(value)) return head.next;
    
    // 3. 找待删节点的“前驱节点”（current最终会停在待删节点的前一个节点）
    Node<T> current = head; // 从head开始遍历
    // 循环条件：current的下一个节点不为空，且下一个节点的数据不是要删的值
    while (current.next != null && !current.next.data.equals(value)) {
        current = current.next; // 往后走，找前驱节点
    }
    
    // 4. 如果找到待删节点（current.next不为空），执行删除
    if (current.next != null) {
        current.next = current.next.next; // 前驱节点跳过待删节点，指向待删节点的下一个
    }
    
    // 5. 返回处理后的头节点（如果没删头，就是原头；删头的话步骤2已经返回了）
    return head;
}

2. 双向链表

  • 结构：双向链表（Doubly Linked List）每个节点包含数据域、前驱指针（prev）和后继指针（next）。

  • 操作特点：

    • 支持双向遍历（从头到尾或从尾到头）。
    • 插入/删除需同时维护前驱和后继指针。

  • 代码示例：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

    // 双向链表节点定义
class DNode<T> {
    T data;
    DNode<T> prev;
    DNode<T> next;
    public DNode(T data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// Java中的双向链表实现：LinkedList
LinkedList<String> list = new LinkedList<>();
list.add("A"); // 添加节点到链表尾部
list.addFirst("B"); // 添加节点到头部

3. 循环链表

  • 结构：循环链表（Circular Linked List）尾节点的指针指向头节点，形成环形结构。

  • 操作特点：

    • 适合环形遍历场景（如轮询调度）。
    • 需注意终止条件，避免无限循环。

  • 代码示例：

    1
2
3
4
5

    // 循环单链表示例
Node<Integer> node1 = new Node<>(1);
Node<Integer> node2 = new Node<>(2);
node1.next = node2;
node2.next = node1; // 尾节点指向头节点

4. Java内置的链表

核心特性：

  • 实现方式：Java中的链表实现（LinkedList）为双向链表（每个节点包含prev和next指针）。
  • 功能支持：
    • 可作为List、Queue或Deque（双端队列）使用。
    • 提供addFirst()、addLast()、pollFirst()等方法。
  • 线程安全：非线程安全，需手动同步（如使用Collections.synchronizedList）。

常用操作示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

// 添加元素
linkedList.add("A");      // 添加到尾部
linkedList.addFirst("B"); // 添加到头部
linkedList.addLast("C");  // 等同于add()

// 删除元素
linkedList.removeFirst(); // 移除头部元素
linkedList.removeLast();  // 移除尾部元素

// 访问元素（低效，需遍历）
String first = linkedList.get(0); // O(n)

// 迭代遍历（推荐方式）
for (String s : linkedList) {
    System.out.println(s);
}

5. 链表打印

1. 逆序打印不修改链表结构

（1）使用栈（Stack）实现：

  • 原理：利用栈的**后进先出（LIFO）**特性，遍历链表时将节点值压入栈，再依次弹出栈元素实现逆序。

  • 时间复杂度：O(n)（遍历链表 + 出栈操作）。

  • 空间复杂度：O(n)（需要额外栈空间）。

  • 代码示例：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    public static <T> void printReverseWithStack(Node<T> head) {
    if (head == null) {
        System.out.println("链表为空");
        return;
    }
    Stack<T> stack = new Stack<>();
    Node<T> current = head;
    // 压栈
    while (current != null) {
        stack.push(current.data);
        current = current.next;
    }
    // 出栈打印
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}

（2）递归实现：

  • 原理：通过递归深入链表尾部，再逐层返回时打印节点值（天然栈结构）。

  • 时间复杂度：O(n)。

  • 空间复杂度：O(n)（递归调用栈深度）。

  • 代码示例：

    1
2
3
4
5

    public static <T> void printReverseRecursive(Node<T> head) {
    if (head == null) return;
    printReverseRecursive(head.next); // 先递归到链表末尾
    System.out.print(head.data + " "); // 从后往前打印，逆序打印
}

2. 逆序打印修改链表结构

（1）反转链表（迭代法）：

  • 原理：通过修改节点的指针方向，将链表反转，再顺序打印。

  • 时间复杂度：O(n)。

  • 空间复杂度：O(1)（原地反转，无需额外空间）。

  • 代码示例：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

      // 节点1->节点2->节点3->null，定义prev和current两个标签。核心思想就是让current的next指向prev，并让prev和current向前移动
  // 第一次循环：prev=null, current=1, next=2, 1->null, prev=1, current=2
  // 第二次循环：prev=1, current=2, next=3, 2->1, prev=2, current=3
  // 第三次循环：prev=2, current=3, next=null, 3->2, prev=3, current=null
  public static <T> Node<T> reverseLinkedList(Node<T> head) {
      Node<T> prev = null;
      Node<T> current = head;
      while (current != null) {
          Node<T> next = current.next; // 暂存下一个节点
          current.next = prev;         // 反转指针
          prev = current;              // 前移prev
          current = next;              // 前移current
      }
      return prev; // 返回新头节点
  }

// 使用示例
Node<Integer> head = new Node<>(1);
head.next = new Node<>(2);
head.next.next = new Node<>(3);
Node<Integer> reversedHead = reverseLinkedList(head);
printLinkedList(reversedHead); // 输出：3 -> 2 -> 1

（2）反转链表（递归法）：

  • 原理：递归到链表末尾，逐层反转指针。head.next.next = head将节点 3 的 next 指向 2，但 2 的 next 仍指向 3，形成环，head.next = null断开环。

  • 代码示例：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

      public static <T> Node<T> reverseRecursive(Node<T> head) {
      // 终止条件：空链表 或 只剩一个节点（直接返回，这是反转后的新头）
      if (head == null || head.next == null) {
          return head;
      }
      // 递归深入：找下一个节点的反转结果（直到找到最后一个节点）
      Node<T> newHead = reverseRecursive(head.next);
      // 核心操作：反转当前节点和下一个节点的指针
      head.next.next = head; 
      head.next = null;      
      // 返回新头（始终是原链表的最后一个节点，比如3）
      return newHead;
  }

3. LinkedList 的逆序打印

Java 的 LinkedList 是双向链表，可直接从尾部遍历，无需反转：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");

// 方法1：反向迭代器
Iterator<String> reverseIterator = list.descendingIterator();
while (reverseIterator.hasNext()) {
    System.out.print(reverseIterator.next() + " "); // 输出：C B A
}

// 方法2：反转链表（会修改原链表）
Collections.reverse(list);
System.out.println(list); // 输出：[C, B, A]

4. LinkedList 的正序打印

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 方法1：使用 for-each 循环
for (String s : list) {
    System.out.print(s + " ");
}
// 输出：A B C

// 方法2：使用迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.print(iterator.next() + " ");
}

方法对比与选择：

方法 是否修改链表 时间复杂度 空间复杂度 适用场景
栈 否 O(n) O(n) 需保留原链表结构
递归 否 O(n) O(n) 链表较短，避免栈溢出
反转链表迭代 是 O(n) O(1) 允许修改链表，内存敏感场景
反向迭代器 否 O(n) O(1) Java内置双向链表

6. 链表的应用场景

  1. 频繁插入/删除：如实现撤销操作（每一步操作记录为链表节点）。
  2. 动态数据管理：内存管理中的空闲内存块链表。
  3. 高级数据结构：
    • 栈或队列（LinkedList实现Deque接口）。
    • 图的邻接表表示。
    • 哈希表的冲突解决（链地址法）。
  4. 实际应用：
    • 浏览器的前进/后退功能
    • 文本编辑器的撤销/重做功能
    • 音乐播放器的播放列表
    • 操作系统的进程调度

链表 vs. 数组：

特性 链表 数组
内存分配 动态分配，非连续 静态分配，连续内存
插入/删除 O(1)（已知位置） O(n)（需移动元素）
随机访问 O(n) O(1)
内存开销 每个节点需额外存储指针 无额外开销
适用场景 频繁增删、动态数据 固定大小、高频随机访问

链表的优缺点：

  • 优点：
    • 插入/删除高效（尤其头部和尾部）。
    • 无需预先分配内存，空间利用率高。
    • 动态扩展，无需担心容量限制。
  • 缺点：
    • 不支持快速随机访问。
    • 指针占用额外内存空间。
    • 缓存不友好（内存非连续，无法预加载）。
    • 实现和维护相对复杂。

选择建议：

  • 当需要频繁插入删除操作时，选择链表
  • 当需要频繁随机访问时，选择数组或ArrayList
  • 当元素数量不确定时，选择链表或ArrayList
  • 当内存空间有限时，选择数组

链表通过指针链接实现动态数据管理，适合频繁增删但对随机访问需求低的场景。Java的LinkedList是双向链表的典型实现，可灵活作为列表、队列或栈使用。选择时需权衡其优缺点，结合具体需求选择数据结构。

总结

本文介绍了Java中两种基本的数据结构：数组和链表。

  1. 数组：

    • 普通数组：固定大小，连续内存，支持基本类型，适合频繁随机访问。
    • 动态数组（ArrayList）：自动扩容，基于数组实现，提供丰富的操作方法。

  2. 链表：

    • 单链表：单向遍历，插入/删除效率高。
    • 双向链表：双向遍历，操作更灵活。
    • 循环链表：环形结构，适合特定场景。
    • Java中的LinkedList：基于双向链表实现，可作为List、Queue或Deque使用。

这两种数据结构各有优缺点，选择时应根据具体场景：

  • 需要频繁随机访问时，选择数组或ArrayList
  • 需要频繁增删操作时，选择链表
  • 元素数量固定时，选择数组
  • 元素数量动态变化时，选择ArrayList或LinkedList