背景

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

文章概览

数据结构

数据结构

1. 数组（Array）

1. 普通数组

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

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

代码示例：

// 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++) {
    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）。
若需高性能或存储基本类型，优先选数组。

总结：

数组是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. 添加元素与扩容

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. 源码关键逻辑（简化版）

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); // 复制旧数据到新数组
}

动态数组的优缺点:

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

动态数组 vs 普通数组:

特性	动态数组（`ArrayList`）	普通数组（`int[]`）
容量调整	自动扩容	无法扩容

2.链表（Linked List）

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

链表的核心特点：

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

链表的分类：

1. 单链表（Singly Linked List）

结构：每个节点包含数据域和指向下一节点的指针。
操作特点：
- 只能单向遍历（从头到尾）。
- 插入/删除需维护前驱节点的指针。

代码示例：

// 单链表节点定义
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> head) {
  Node<T> current = head;
  while (current != null) {
      System.out.print(current.data);
      if (current.next != null) {
          System.out.print(" -> "); // 用箭头连接节点
      }
      current = current.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); // 递归调用
  }

// 单链表操作示例
  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
  }

2. 双向链表（Doubly Linked List）

结构：每个节点包含数据域、前驱指针（prev）和后继指针（next）。
操作特点：
- 支持双向遍历（从头到尾或从尾到头）。
- 插入/删除需同时维护前驱和后继指针。

代码示例：

// 双向链表节点定义
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）

结构：尾节点的指针指向头节点，形成环形结构。
操作特点：
- 适合环形遍历场景（如轮询调度）。
- 需注意终止条件，避免无限循环。

代码示例：

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

4. Java中的链表实现：`LinkedList`

核心特性：

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

常用操作示例：

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)（需要额外栈空间）。

代码示例：

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)（递归调用栈深度）。

代码示例：

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)（原地反转，无需额外空间）。

代码示例：

  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断开环。

代码示例：

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;      // 断开原指针
    return newHead;
}

3. Java 内置 `LinkedList` 的逆序打印

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

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. Java 内置 `LinkedList` 的正序打印

// 方法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. 链表的应用场景

频繁插入/删除：如实现撤销操作（每一步操作记录为链表节点）。
动态数据管理：内存管理中的空闲内存块链表。
高级数据结构：
- 栈或队列（LinkedList实现Deque接口）。
- 图的邻接表表示。
- 哈希表的冲突解决（链地址法）。

链表 vs. 数组：

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

链表的优缺点：

优点：
- 插入/删除高效（尤其头部和尾部）。
- 无需预先分配内存，空间利用率高。
缺点：
- 不支持快速随机访问。
- 指针占用额外内存空间。
- 缓存不友好（内存非连续，无法预加载）。

总结：

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

3. List（有序集合，允许重复）

1. `ArrayList`：像一列火车

类比描述：

车厢连续排列：ArrayList 的底层是动态数组，元素像火车车厢一样连续存储在内存中，基于动态数组实现，支持快速随机访问，增删元素效率较低。
快速定位：可以通过索引直接跳到任意车厢（时间复杂度 O(1)）。
扩容机制：当车厢不够时，整列火车会换到更长的轨道（新建更大的数组并复制数据）。

操作特性：

操作	类比	时间复杂度
访问元素（`get`）	直接走到第 `n` 节车厢	O(1)
插入元素（`add`）	在中间插入一节车厢 → 后续车厢全部后移	O(n)
删除元素（`remove`）	移除中间一节车厢 → 后续车厢全部前移	O(n)

代码示例：

// ArrayList（火车式结构）
List<String> arrayList = new ArrayList<>();
arrayList.add("A"); // 添加到末尾
arrayList.add(0, "B"); // 插入到头部 → 其他元素后移
System.out.println(arrayList.get(1)); // 直接访问第2节车厢 → 输出 "A"

2. `LinkedList`：像一条链条

类比描述：

链环逐个连接：LinkedList 的底层是双向链表，每个元素像链环一样离散存储在内存中，通过“链条”（指针）连接。
灵活增删：插入或移除一个链环时，只需调整相邻链环的链接，无需整体移动。
顺序访问：要找到第 n 个链环，必须从头或尾逐个计数（时间复杂度 O(n)）。

操作特性：

操作	类比	时间复杂度
访问元素（`get`）	从链条头/尾逐个查找第 `n` 个链环	O(n)
插入元素（`add`）	断开相邻链环 → 插入新链环 → 重新连接	O(1)（已知位置）
删除元素（`remove`）	断开目标链环 → 直接连接前后链环	O(1)（已知位置）

// LinkedList（链条式结构）
List<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.addFirst("B"); // 插入到头部 → 只需调整指针
System.out.println(linkedList.get(1)); // 必须从头遍历 → 输出 "A"

对比总结：

特性	`ArrayList`（火车）	`LinkedList`（链条）
内存结构	连续内存（车厢紧密排列）	离散内存（链环通过指针连接）
适用场景	高频随机访问，少增删	高频增删，少随机访问
优势操作	`get(int index)`	`addFirst()`, `removeLast()`
劣势操作	中间插入/删除	按索引访问

现实场景类比：

ArrayList 的缺点：
就像在火车中间插入一节车厢时，必须推开后面所有车厢，腾出位置。
LinkedList 的优点：
就像在链条中插入一个链环，只需拆开相邻链环，插入后重新扣上。

3. Vector（线程安全）

描述：类似ArrayList但线程安全，性能较差，已逐渐被取代。

代码示例：

1
2
3

Vector<String> vector = new Vector<>();
vector.add("Element");
System.out.println(vector.get(0));

4. Stack（后进先出）

描述：继承自Vector，提供push、pop方法实现栈。

代码示例：

Stack<String> stack = new Stack<>();
stack.push("A");
stack.push("B");
System.out.println(stack.pop()); // 输出 B

4. Set（无序集合，元素唯一）

1. HashSet

描述：基于哈希表实现，元素无序，查询效率O(1)。

代码示例：

Set<String> set = new HashSet<>();
set.add("A");
set.add("A"); // 重复元素被忽略
System.out.println(set.size()); // 输出 1

2. LinkedHashSet

描述：维护插入顺序的哈希表，迭代顺序可预测。

代码示例：

Set<String> linkedSet = new LinkedHashSet<>();
linkedSet.add("B");
linkedSet.add("A");
linkedSet.forEach(System.out::println); // 输出 B A（插入顺序）

3. TreeSet

描述：基于红黑树实现，元素自然排序或自定义排序。

代码示例：

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
System.out.println(treeSet.first()); // 输出 1（排序后最小值）

5. Map（键值对集合）

1. HashMap

描述：基于哈希表，键唯一，允许null键/值，无序。

代码示例：

1
2
3

Map<String, Integer> map = new HashMap<>();
map.put("Key", 100);
System.out.println(map.get("Key")); // 输出 100

2. LinkedHashMap

描述：维护插入顺序或访问顺序（LRU缓存）。

代码示例：

Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("A", 1);
linkedMap.put("B", 2);
linkedMap.keySet().forEach(System.out::println); // 输出 A B

3. TreeMap

描述：基于红黑树，按键自然排序或自定义排序。

代码示例：

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("B", 2);
treeMap.put("A", 1);
System.out.println(treeMap.firstKey()); // 输出 A

4. Hashtable（线程安全）

描述：类似HashMap但线程安全，不允许null键/值。

代码示例：

1
2
3

Hashtable<String, Integer> table = new Hashtable<>();
table.put("Key", 10);
System.out.println(table.get("Key"));

6. Queue/Deque（队列/双端队列）

1. PriorityQueue

描述：基于优先级堆，元素按自然顺序或Comparator出队。

代码示例：

Queue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
System.out.println(pq.poll()); // 输出 1（最小优先）

2. ArrayDeque

描述：基于循环数组的双端队列，高效实现队列和栈。

代码示例：

Deque<String> deque = new ArrayDeque<>();
deque.offerLast("End");
deque.offerFirst("Start");
System.out.println(deque.pollFirst()); // 输出 Start

总结

Java基础，需要熟练掌握。

背景

文章概览

数据结构

1. 数组（Array）

1. 普通数组

2. 动态数组

2.链表（Linked List）

1. 单链表（Singly Linked List）

2. 双向链表（Doubly Linked List）

3. 循环链表（Circular Linked List）

4. Java中的链表实现：LinkedList

5. 链表打印

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

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

3. Java 内置 LinkedList 的逆序打印

4. Java 内置 LinkedList 的正序打印

6. 链表的应用场景

3. List（有序集合，允许重复）

1. ArrayList：像一列火车

2. LinkedList：像一条链条

3. Vector（线程安全）

4. Stack（后进先出）

4. Set（无序集合，元素唯一）

1. HashSet

2. LinkedHashSet

3. TreeSet

5. Map（键值对集合）

1. HashMap

2. LinkedHashMap

3. TreeMap

4. Hashtable（线程安全）

6. Queue/Deque（队列/双端队列）

1. PriorityQueue

2. ArrayDeque

总结

4. Java中的链表实现：`LinkedList`

3. Java 内置 `LinkedList` 的逆序打印

4. Java 内置 `LinkedList` 的正序打印

1. `ArrayList`：像一列火车

2. `LinkedList`：像一条链条