什么是数据结构?

数据结构(Data Structure)是计算机存储、组织数据的方式。一个好的数据结构可以让程序运行得更快、占用更少的内存。选择合适的数据结构，是编写高效程序的关键。

数据结构的分类

数据结构按照不同的维度可以分为多种类型:

按存储结构分类

1. 线性结构

数据元素之间存在一对一的线性关系。

  • 数组 (Array)
  • 链表 (LinkedList)
  • 栈 (Stack)
  • 队列 (Queue)

2. 非线性结构

数据元素之间存在一对多或多对多的关系。

  • 树 (Tree)
  • 图 (Graph)
  • 堆 (Heap)

按逻辑结构分类

  • 集合结构: 数据元素之间除了”同属一个集合”外，没有其他关系
  • 线性结构: 数据元素之间是一对一的关系
  • 树形结构: 数据元素之间是一对多的层次关系
  • 图形结构: 数据元素之间是多对多的关系

线性数据结构

数组 (Array)

定义: 数组是最基础的数据结构，用连续的内存空间存储相同类型的元素。

特点:

  • ✅ 支持快速随机访问 (时间复杂度 O(1))
  • ✅ 内存连续，缓存友好
  • ❌ 插入/删除效率低 (需要移动元素)
  • ❌ 大小固定，不易扩展

Java 实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
// 静态数组
int[] array = new int[10];
array[0] = 1;
array[1] = 2;

// 动态数组 - ArrayList (基于数组实现)
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

System.out.println("元素访问: " + list.get(0)); // O(1)
list.remove(0); // O(n) - 需要移动后续元素

时间复杂度:

  • 访问: O(1)
  • 查找: O(n)
  • 插入: O(n) (平均)
  • 删除: O(n) (平均)

应用场景:

  • 需要快速随机访问元素
  • 数据量固定或变化不大
  • 频繁读取，很少修改

ArrayList 扩容机制:

1
2
3
4
5
6
7
8
9
// ArrayList 默认初始容量为 10
// 当容量不足时，会扩容为原来的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

// 示例:扩容过程
// 初始容量: 10
// 第一次扩容: 10 + 5 = 15
// 第二次扩容: 15 + 7 = 22
// 第三次扩容: 22 + 11 = 33

链表 (LinkedList)

定义: 链表是由一系列节点组成的数据结构，每个节点包含数据和指向下一个节点的指针。

分类:

  1. 单向链表: 每个节点只有一个指向下一个节点的指针
  2. 双向链表: 每个节点有两个指针，分别指向前后节点
  3. 循环链表: 尾节点指向头节点，形成环

特点:

  • ✅ 插入/删除效率高 (O(1))
  • ✅ 大小动态可变
  • ❌ 不支持随机访问
  • ❌ 需要额外的内存存储指针

单向链表实现:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// 链表节点
class Node {
    int data;
    Node next;

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

// 单向链表
class LinkedList {
    private Node head;

    // 在头部插入 - O(1)
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 在尾部插入 - O(n)
    public void insertAtTail(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 删除节点 - O(n)
    public void delete(int data) {
        if (head == null) return;

        // 删除头节点
        if (head.data == data) {
            head = head.next;
            return;
        }

        // 删除其他节点
        Node current = head;
        while (current.next != null) {
            if (current.next.data == data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }

    // 查找节点 - O(n)
    public boolean search(int data) {
        Node current = head;
        while (current != null) {
            if (current.data == data) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 打印链表
    public void print() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

// 使用示例
LinkedList list = new LinkedList();
list.insertAtHead(3);
list.insertAtHead(2);
list.insertAtHead(1);
list.insertAtTail(4);
list.print(); // 输出: 1 -> 2 -> 3 -> 4 -> null

list.delete(2);
list.print(); // 输出: 1 -> 3 -> 4 -> 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 双向链表节点
class DoublyNode {
    int data;
    DoublyNode prev;
    DoublyNode next;

    public DoublyNode(int data) {
        this.data = data;
        this.prev = null;
        this.next = null;
    }
}

// 双向链表
class DoublyLinkedList {
    private DoublyNode head;
    private DoublyNode tail;

    // 在头部插入
    public void insertAtHead(int data) {
        DoublyNode newNode = new DoublyNode(data);

        if (head == null) {
            head = tail = newNode;
        } else {
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
        }
    }

    // 在尾部插入
    public void insertAtTail(int data) {
        DoublyNode newNode = new DoublyNode(data);

        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // 正向打印
    public void printForward() {
        DoublyNode current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    // 反向打印
    public void printBackward() {
        DoublyNode current = tail;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.prev;
        }
        System.out.println("null");
    }
}

时间复杂度:

  • 访问: O(n)
  • 查找: O(n)
  • 插入: O(1) (已知位置) / O(n) (需要查找)
  • 删除: O(1) (已知位置) / O(n) (需要查找)

数组 vs 链表:

操作 数组 链表
随机访问 O(1) O(n)
插入/删除 O(n) O(1)
内存占用 连续空间 分散空间 + 指针
缓存友好性 好 差

栈 (Stack)

定义: 栈是一种后进先出(LIFO - Last In First Out)的数据结构。

核心操作:

  • push(): 入栈 - 将元素压入栈顶
  • pop(): 出栈 - 弹出栈顶元素
  • peek(): 查看栈顶元素(不删除)
  • isEmpty(): 判断栈是否为空

基于数组实现:

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
45
46
47
48
49
50
51
52
53
54
55
class ArrayStack {
    private int[] array;
    private int top;
    private int capacity;

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

    // 入栈 - O(1)
    public void push(int data) {
        if (top == capacity - 1) {
            throw new StackOverflowError("栈已满");
        }
        array[++top] = data;
    }

    // 出栈 - O(1)
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空");
        }
        return array[top--];
    }

    // 查看栈顶元素 - O(1)
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空");
        }
        return array[top];
    }

    // 判断是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 获取栈大小
    public int size() {
        return top + 1;
    }
}

// 使用示例
ArrayStack stack = new ArrayStack(5);
stack.push(1);
stack.push(2);
stack.push(3);

System.out.println("栈顶元素: " + stack.peek()); // 3
System.out.println("出栈: " + stack.pop());       // 3
System.out.println("出栈: " + stack.pop());       // 2

基于链表实现:

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
45
46
47
48
class LinkedStack {
    private Node top;
    private int size;

    private class Node {
        int data;
        Node next;

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

    // 入栈 - O(1)
    public void push(int data) {
        Node newNode = new Node(data);
        newNode.next = top;
        top = newNode;
        size++;
    }

    // 出栈 - O(1)
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空");
        }
        int data = top.data;
        top = top.next;
        size--;
        return data;
    }

    // 查看栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        return size;
    }
}

Java 标准库中的栈:

1
2
3
4
5
6
7
8
9
10
11
// 方式1: 使用 Stack 类(不推荐，已过时)
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.pop();

// 方式2: 使用 Deque 接口(推荐)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.pop();

应用场景:

  1. 函数调用栈: 程序运行时的函数调用记录
  2. 表达式求值: 后缀表达式计算
  3. 括号匹配: 检查括号是否匹配
  4. 浏览器历史: 后退功能
  5. 撤销操作: Ctrl+Z 功能

经典题目: 括号匹配:

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 isValidParentheses(String s) {
    Deque<Character> stack = new ArrayDeque<>();

    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 != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }

    return stack.isEmpty();
}

// 测试
System.out.println(isValidParentheses("()[]{}"));     // true
System.out.println(isValidParentheses("([)]"));       // false
System.out.println(isValidParentheses("{[]}"));       // true

队列 (Queue)

定义: 队列是一种先进先出(FIFO - First In First Out)的数据结构。

核心操作:

  • enqueue() / offer(): 入队 - 在队尾添加元素
  • dequeue() / poll(): 出队 - 从队头移除元素
  • peek(): 查看队头元素(不删除)
  • isEmpty(): 判断队列是否为空

基于数组实现(循环队列):

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class CircularQueue {
    private int[] array;
    private int front;  // 队头指针
    private int rear;   // 队尾指针
    private int size;   // 当前元素个数
    private int capacity;

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.array = new int[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    // 入队 - O(1)
    public void enqueue(int data) {
        if (isFull()) {
            throw new IllegalStateException("队列已满");
        }
        rear = (rear + 1) % capacity; // 循环利用空间
        array[rear] = data;
        size++;
    }

    // 出队 - O(1)
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        int data = array[front];
        front = (front + 1) % capacity;
        size--;
        return data;
    }

    // 查看队头元素
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return array[front];
    }

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

    public boolean isFull() {
        return size == capacity;
    }

    public int size() {
        return size;
    }
}

// 使用示例
CircularQueue queue = new CircularQueue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

System.out.println("队头元素: " + queue.peek()); // 1
System.out.println("出队: " + queue.dequeue());   // 1
System.out.println("出队: " + queue.dequeue());   // 2

基于链表实现:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class LinkedQueue {
    private Node front;
    private Node rear;
    private int size;

    private class Node {
        int data;
        Node next;

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

    // 入队 - O(1)
    public void enqueue(int data) {
        Node newNode = new Node(data);

        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    // 出队 - O(1)
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }

        int data = front.data;
        front = front.next;

        if (front == null) {
            rear = null;
        }

        size--;
        return data;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空");
        }
        return front.data;
    }

    public boolean isEmpty() {
        return front == null;
    }

    public int size() {
        return size;
    }
}

Java 标准库中的队列:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 1. LinkedList 实现 Queue 接口
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.poll();

// 2. ArrayDeque (推荐，性能更好)
Queue<Integer> queue2 = new ArrayDeque<>();
queue2.offer(1);
queue2.offer(2);
queue2.poll();

// 3. PriorityQueue (优先队列)
Queue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
pq.offer(2);
System.out.println(pq.poll()); // 1 (最小的元素优先出队)

特殊队列:

双端队列 (Deque - Double Ended Queue)

可以在两端进行插入和删除操作。

1
2
3
4
5
6
7
8
9
10
11
Deque<Integer> deque = new ArrayDeque<>();

// 队头操作
deque.addFirst(1);
deque.removeFirst();
deque.peekFirst();

// 队尾操作
deque.addLast(2);
deque.removeLast();
deque.peekLast();

优先队列 (Priority Queue)

元素按照优先级出队，而不是按照插入顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 最小堆(默认)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);
minHeap.offer(1);
minHeap.offer(2);
System.out.println(minHeap.poll()); // 1

// 最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
System.out.println(maxHeap.poll()); // 3

应用场景:

  1. 任务调度: 按顺序处理任务
  2. 消息队列: Kafka、RabbitMQ
  3. 广度优先搜索: BFS 算法
  4. 打印队列: 打印机任务队列
  5. 线程池: 任务等待队列

非线性数据结构

树 (Tree)

定义: 树是一种层次结构的数据结构，由节点和边组成。每个节点包含数据和指向子节点的指针。

基本概念:

  • 根节点: 树的顶端节点
  • 父节点: 有子节点的节点
  • 子节点: 某个节点的下一层节点
  • 叶子节点: 没有子节点的节点
  • 深度: 从根节点到某节点的边数
  • 高度: 从某节点到叶子节点的最长路径

二叉树 (Binary Tree)

定义: 每个节点最多有两个子节点(左子节点和右子节点)。

二叉树节点定义:

1
2
3
4
5
6
7
8
9
10
11
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

二叉树的分类:

  1. 满二叉树: 所有非叶子节点都有两个子节点，且所有叶子节点在同一层
  2. 完全二叉树: 除最后一层外，其他层都是满的，最后一层从左到右连续
  3. 平衡二叉树: 任意节点的左右子树高度差不超过 1

二叉树的遍历:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class BinaryTree {
    TreeNode root;

    // 前序遍历: 根 -> 左 -> 右
    public void preOrder(TreeNode node) {
        if (node == null) return;

        System.out.print(node.val + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    // 中序遍历: 左 -> 根 -> 右
    public void inOrder(TreeNode node) {
        if (node == null) return;

        inOrder(node.left);
        System.out.print(node.val + " ");
        inOrder(node.right);
    }

    // 后序遍历: 左 -> 右 -> 根
    public void postOrder(TreeNode node) {
        if (node == null) return;

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + " ");
    }

    // 层序遍历(广度优先)
    public void levelOrder(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
}

// 构建示例树
//       1
//      / \
//     2   3
//    / \
//   4   5
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

BinaryTree tree = new BinaryTree();
tree.root = root;

System.out.print("前序遍历: ");
tree.preOrder(root); // 1 2 4 5 3

System.out.print("\n中序遍历: ");
tree.inOrder(root);  // 4 2 5 1 3

System.out.print("\n后序遍历: ");
tree.postOrder(root); // 4 5 2 3 1

System.out.print("\n层序遍历: ");
tree.levelOrder(root); // 1 2 3 4 5

二叉搜索树 (BST - Binary Search Tree)

定义: 一种特殊的二叉树，满足以下性质:

  • 左子树的所有节点值 < 根节点值
  • 右子树的所有节点值 > 根节点值
  • 左右子树也都是二叉搜索树

BST 实现:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
class BST {
    TreeNode root;

    // 插入节点 - 平均 O(log n)，最坏 O(n)
    public TreeNode insert(TreeNode node, int val) {
        if (node == null) {
            return new TreeNode(val);
        }

        if (val < node.val) {
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        }

        return node;
    }

    // 查找节点 - 平均 O(log n)，最坏 O(n)
    public boolean search(TreeNode node, int val) {
        if (node == null) {
            return false;
        }

        if (val == node.val) {
            return true;
        } else if (val < node.val) {
            return search(node.left, val);
        } else {
            return search(node.right, val);
        }
    }

    // 删除节点
    public TreeNode delete(TreeNode node, int val) {
        if (node == null) {
            return null;
        }

        if (val < node.val) {
            node.left = delete(node.left, val);
        } else if (val > node.val) {
            node.right = delete(node.right, val);
        } else {
            // 找到要删除的节点

            // 情况1: 叶子节点
            if (node.left == null && node.right == null) {
                return null;
            }

            // 情况2: 只有一个子节点
            if (node.left == null) {
                return node.right;
            }
            if (node.right == null) {
                return node.left;
            }

            // 情况3: 有两个子节点
            // 找到右子树的最小节点(后继节点)
            TreeNode successor = findMin(node.right);
            node.val = successor.val;
            node.right = delete(node.right, successor.val);
        }

        return node;
    }

    // 找到最小节点
    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}

// 使用示例
BST bst = new BST();
bst.root = bst.insert(bst.root, 50);
bst.insert(bst.root, 30);
bst.insert(bst.root, 70);
bst.insert(bst.root, 20);
bst.insert(bst.root, 40);
bst.insert(bst.root, 60);
bst.insert(bst.root, 80);

//       50
//      /  \
//    30    70
//   / \   / \
//  20 40 60 80

System.out.println(bst.search(bst.root, 40)); // true
System.out.println(bst.search(bst.root, 90)); // false

bst.root = bst.delete(bst.root, 30);

BST 的优缺点:

  • ✅ 查找、插入、删除的平均时间复杂度为 O(log n)
  • ✅ 中序遍历可以得到有序序列
  • ❌ 在最坏情况下(退化为链表)，时间复杂度为 O(n)

堆 (Heap)

定义: 堆是一种特殊的完全二叉树，分为最大堆和最小堆。

堆的性质:

  • 最大堆: 父节点的值 ≥ 子节点的值，根节点是最大值
  • 最小堆: 父节点的值 ≤ 子节点的值，根节点是最小值

堆的存储: 通常用数组实现，对于索引 i 的节点:

  • 父节点索引: (i - 1) / 2
  • 左子节点索引: 2 * i + 1
  • 右子节点索引: 2 * i + 2

最小堆实现:

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.heap = new int[capacity];
        this.size = 0;
    }

    // 获取父节点索引
    private int parent(int i) {
        return (i - 1) / 2;
    }

    // 获取左子节点索引
    private int leftChild(int i) {
        return 2 * i + 1;
    }

    // 获取右子节点索引
    private int rightChild(int i) {
        return 2 * i + 2;
    }

    // 交换元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 插入元素 - O(log n)
    public void insert(int val) {
        if (size == capacity) {
            throw new IllegalStateException("堆已满");
        }

        // 在数组末尾插入新元素
        heap[size] = val;
        int current = size;
        size++;

        // 上浮操作，维护堆性质
        while (current > 0 && heap[current] < heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    // 删除最小元素 - O(log n)
    public int extractMin() {
        if (size == 0) {
            throw new IllegalStateException("堆为空");
        }

        int min = heap[0];

        // 将最后一个元素移到根节点
        heap[0] = heap[size - 1];
        size--;

        // 下沉操作，维护堆性质
        heapify(0);

        return min;
    }

    // 下沉操作
    private void heapify(int i) {
        int minIndex = i;
        int left = leftChild(i);
        int right = rightChild(i);

        // 找到最小的节点
        if (left < size && heap[left] < heap[minIndex]) {
            minIndex = left;
        }
        if (right < size && heap[right] < heap[minIndex]) {
            minIndex = right;
        }

        // 如果最小节点不是当前节点，交换并继续下沉
        if (minIndex != i) {
            swap(i, minIndex);
            heapify(minIndex);
        }
    }

    // 获取最小元素(不删除) - O(1)
    public int getMin() {
        if (size == 0) {
            throw new IllegalStateException("堆为空");
        }
        return heap[0];
    }

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

    public int size() {
        return size;
    }
}

// 使用示例
MinHeap heap = new MinHeap(10);
heap.insert(5);
heap.insert(3);
heap.insert(7);
heap.insert(1);

System.out.println("最小元素: " + heap.getMin()); // 1
System.out.println("删除: " + heap.extractMin());  // 1
System.out.println("最小元素: " + heap.getMin()); // 3

堆的应用:

  1. 优先队列: Java 的 PriorityQueue 就是基于堆实现的
  2. 堆排序: 时间复杂度 O(n log n)
  3. Top K 问题: 找出最大/最小的 K 个元素
  4. 任务调度: 按优先级调度任务

经典问题: 查找第 K 大的元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findKthLargest(int[] nums, int k) {
    // 使用最小堆，保持堆的大小为 k
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // 移除最小的元素
        }
    }

    return minHeap.peek(); // 堆顶就是第 K 大的元素
}

// 测试
int[] nums = {3, 2, 1, 5, 6, 4};
System.out.println(findKthLargest(nums, 2)); // 5

哈希表 (Hash Table)

定义: 哈希表是根据键(Key)直接访问值(Value)的数据结构。通过哈希函数将键映射到数组的索引位置。

核心概念:

  • 哈希函数: 将键转换为数组索引的函数
  • 哈希冲突: 不同的键映射到同一个索引
  • 负载因子: 元素个数 / 数组容量

解决哈希冲突的方法:

1. 链地址法 (Separate Chaining)

每个数组位置存储一个链表，冲突的元素都存在同一个链表中。

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
class HashTable {
    private class Entry {
        String key;
        int value;
        Entry next;

        Entry(String key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Entry[] table;
    private int capacity;
    private int size;

    public HashTable(int capacity) {
        this.capacity = capacity;
        this.table = new Entry[capacity];
        this.size = 0;
    }

    // 哈希函数
    private int hash(String key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    // 插入/更新 - 平均 O(1)
    public void put(String key, int value) {
        int index = hash(key);
        Entry entry = table[index];

        // 查找是否已存在
        while (entry != null) {
            if (entry.key.equals(key)) {
                entry.value = value; // 更新
                return;
            }
            entry = entry.next;
        }

        // 插入新节点(头插法)
        Entry newEntry = new Entry(key, value);
        newEntry.next = table[index];
        table[index] = newEntry;
        size++;
    }

    // 查找 - 平均 O(1)
    public Integer get(String key) {
        int index = hash(key);
        Entry entry = table[index];

        while (entry != null) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
            entry = entry.next;
        }

        return null; // 未找到
    }

    // 删除 - 平均 O(1)
    public void remove(String key) {
        int index = hash(key);
        Entry entry = table[index];
        Entry prev = null;

        while (entry != null) {
            if (entry.key.equals(key)) {
                if (prev == null) {
                    table[index] = entry.next;
                } else {
                    prev.next = entry.next;
                }
                size--;
                return;
            }
            prev = entry;
            entry = entry.next;
        }
    }

    public int size() {
        return size;
    }
}

// 使用示例
HashTable ht = new HashTable(10);
ht.put("apple", 1);
ht.put("banana", 2);
ht.put("orange", 3);

System.out.println(ht.get("apple"));   // 1
System.out.println(ht.get("banana"));  // 2

ht.remove("banana");
System.out.println(ht.get("banana"));  // null

2. 开放地址法 (Open Addressing)

当发生冲突时，寻找下一个空闲位置。

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
45
46
47
48
49
50
51
52
class OpenAddressingHashTable {
    private String[] keys;
    private Integer[] values;
    private int capacity;
    private int size;

    public OpenAddressingHashTable(int capacity) {
        this.capacity = capacity;
        this.keys = new String[capacity];
        this.values = new Integer[capacity];
        this.size = 0;
    }

    private int hash(String key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    // 线性探测
    public void put(String key, int value) {
        if (size >= capacity * 0.75) {
            throw new IllegalStateException("哈希表负载过高");
        }

        int index = hash(key);

        // 线性探测找到空位或相同key
        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                values[index] = value; // 更新
                return;
            }
            index = (index + 1) % capacity;
        }

        keys[index] = key;
        values[index] = value;
        size++;
    }

    public Integer get(String key) {
        int index = hash(key);

        while (keys[index] != null) {
            if (keys[index].equals(key)) {
                return values[index];
            }
            index = (index + 1) % capacity;
        }

        return null;
    }
}

Java 中的哈希表:

1
2
3
4
5
6
7
8
9
10
11
// HashMap - 基于哈希表实现
Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
System.out.println(map.get("apple")); // 1

// HashSet - 基于 HashMap 实现
Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
System.out.println(set.contains("apple")); // true

HashMap 的工作原理:

  1. 计算 key 的 hashCode
  2. 通过哈希函数计算数组索引: (n - 1) & hash
  3. 如果没有冲突，直接存入
  4. 如果有冲突:
    • JDK 1.7: 使用链表
    • JDK 1.8+: 链表长度 ≤ 8 时使用链表，> 8 时转为红黑树

时间复杂度:

  • 平均情况: O(1)
  • 最坏情况: O(n) (所有元素都冲突)

应用场景:

  1. 缓存系统: LRU Cache
  2. 数据库索引: 快速查找
  3. 去重: HashSet
  4. 统计频率: 字符/单词频率统计

经典问题: 两数之和:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }

    return null;
}

// 测试
int[] nums = {2, 7, 11, 15};
int[] result = twoSum(nums, 9);
System.out.println(Arrays.toString(result)); // [0, 1]

时间复杂度和空间复杂度

时间复杂度

时间复杂度用大O表示法描述算法执行时间与输入规模的关系。

常见时间复杂度(从快到慢):

  1. O(1) - 常数时间: 数组随机访问、哈希表查找
  2. O(log n) - 对数时间: 二分查找、平衡二叉树操作
  3. O(n) - 线性时间: 遍历数组、链表查找
  4. O(n log n) - 线性对数时间: 快速排序、归并排序、堆排序
  5. O(n²) - 平方时间: 冒泡排序、选择排序、插入排序
  6. O(n³) - 立方时间: 三层嵌套循环
  7. O(2^n) - 指数时间: 递归计算斐波那契数列
  8. O(n!) - 阶乘时间: 旅行商问题(暴力解法)

时间复杂度对比:

1
2
3
4
5
6
7
n = 100 时:
O(1)      = 1
O(log n)  ≈ 7
O(n)      = 100
O(n log n)≈ 700
O(n²)     = 10,000
O(2^n)    ≈ 1.27 × 10³⁰

空间复杂度

空间复杂度描述算法占用内存空间与输入规模的关系。

常见空间复杂度:

  1. O(1) - 常数空间: 几个变量
  2. O(n) - 线性空间: 一个数组
  3. O(n²) - 平方空间: 二维数组

数据结构对比总结

数据结构 访问 查找 插入 删除 空间复杂度
数组 O(1) O(n) O(n) O(n) O(n)
链表 O(n) O(n) O(1) O(1) O(n)
栈 O(n) O(n) O(1) O(1) O(n)
队列 O(n) O(n) O(1) O(1) O(n)
哈希表 - O(1) O(1) O(1) O(n)
二叉搜索树 O(log n) O(log n) O(log n) O(log n) O(n)
堆 O(1) O(n) O(log n) O(log n) O(n)

注: 表中的时间复杂度为平均情况。

如何选择合适的数据结构?

  1. 需要快速随机访问 → 数组、ArrayList
  2. 频繁插入/删除 → 链表、LinkedList
  3. 后进先出 → 栈
  4. 先进先出 → 队列
  5. 快速查找/去重 → 哈希表(HashMap/HashSet)
  6. 有序数据 → 二叉搜索树、TreeMap/TreeSet
  7. 优先级处理 → 堆、PriorityQueue
  8. 图相关问题 → 邻接表、邻接矩阵

总结

数据结构是程序设计的基石，理解和掌握常用数据结构对于编写高效程序至关重要。

学习建议:

  1. 理解原理: 不要只记API，要理解底层实现
  2. 动手实践: 自己实现一遍各种数据结构
  3. 刷题巩固: 通过 LeetCode 等平台练习算法题
  4. 分析复杂度: 养成分析时间和空间复杂度的习惯
  5. 阅读源码: 研究 JDK 集合框架的源码实现

推荐资源:

掌握数据结构，从理解概念开始，通过实践加深理解，最终做到灵活运用!