数据结构

---

1. 数组 (Array)

特点：连续内存，随机访问 O(1)，插入/删除 O(n)。

常见操作

// 遍历
int[] arr = {1, 2, 3, 4, 5};
for (int i = 0; i < arr.length; i++) System.out.print(arr[i] + " ");

// 查找（线性查找）
public static int find(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

// 插入（指定位置）
public static int[] insert(int[] arr, int pos, int val) {
    int[] newArr = new int[arr.length + 1];
    for (int i = 0, j = 0; i < newArr.length; i++) {
        if (i == pos) newArr[i] = val;
        else newArr[i] = arr[j++];
    }
    return newArr;
}

// 删除（指定位置）
public static int[] delete(int[] arr, int pos) {
    int[] newArr = new int[arr.length - 1];
    for (int i = 0, j = 0; i < arr.length; i++) {
        if (i == pos) continue;
        newArr[j++] = arr[i];
    }
    return newArr;
}

// 反转
public static void reverse(int[] arr) {
    int i = 0, j = arr.length - 1;
    while (i < j) {
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        i++; j--;
    }
}

---

2. 链表 (Linked List)

特点：动态存储，插入/删除 O(1)，随机访问 O(n)。

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

// 遍历
public static void traverse(ListNode head) {
    for (ListNode p = head; p != null; p = p.next)
        System.out.print(p.val + " ");
}

// 插入（头插）
public static ListNode insertHead(ListNode head, int val) {
    ListNode node = new ListNode(val);
    node.next = head;
    return node;
}

// 插入（指定节点后）
public static void insertAfter(ListNode node, int val) {
    if (node == null) return;
    ListNode newNode = new ListNode(val);
    newNode.next = node.next;
    node.next = newNode;
}

// 删除（按值）
public static ListNode delete(ListNode head, int target) {
    if (head == null) return null;
    if (head.val == target) return head.next;
    ListNode p = head;
    while (p.next != null) {
        if (p.next.val == target) {
            p.next = p.next.next; break;
        }
        p = p.next;
    }
    return head;
}

// 反转
public static ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

---

3. 栈 (Stack)

特点：LIFO，常用数组或链表实现。

class MyStack {
    private LinkedList<Integer> list = new LinkedList<>();

    public void push(int val) { list.addLast(val); } // 入栈
    public int pop() { return list.removeLast(); }   // 出栈
    public int peek() { return list.getLast(); }     // 查看栈顶
    public boolean isEmpty() { return list.isEmpty(); }
}

---

4. 队列 (Queue)

特点：FIFO，可以用链表或循环数组实现。

class MyQueue {
    private LinkedList<Integer> list = new LinkedList<>();

    public void enqueue(int val) { list.addLast(val); } // 入队
    public int dequeue() { return list.removeFirst(); } // 出队
    public int peek() { return list.getFirst(); }       // 查看队首
    public boolean isEmpty() { return list.isEmpty(); }
}

双端队列 Deque

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1); // 头插
deque.addLast(2);  // 尾插
deque.removeFirst();
deque.removeLast();

---

5. 树 (Tree)

以 二叉树 为例。

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

// 前序遍历 (根-左-右)
public static void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorder(root.left);
    preorder(root.right);
}

// 中序遍历 (左-根-右)
public static void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);
    System.out.print(root.val + " ");
    inorder(root.right);
}

// 后序遍历 (左-右-根)
public static void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    System.out.print(root.val + " ");
}

// 层序遍历 (BFS)
public static void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        System.out.print(node.val + " ");
        if (node.left != null) q.add(node.left);
        if (node.right != null) q.add(node.right);
    }
}

---

6. 堆 (Heap)

常用 最小堆 / 最大堆，一般用数组实现。

import java.util.PriorityQueue;

// 最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(3);
minHeap.add(1);
minHeap.add(5);
System.out.println(minHeap.poll()); // 1

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

---

7. 图 (Graph)

常见表示：邻接表。

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adj = new HashMap<>();

    public void addEdge(int u, int v) {
        adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u); // 无向图
    }

    // BFS 遍历
    public void bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        visited.add(start);
        while (!q.isEmpty()) {
            int node = q.poll();
            System.out.print(node + " ");
            for (int nei : adj.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(nei)) {
                    visited.add(nei);
                    q.add(nei);
                }
            }
        }
    }

    // DFS 遍历
    public void dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        dfsHelper(start, visited);
    }

    private void dfsHelper(int node, Set<Integer> visited) {
        if (visited.contains(node)) return;
        visited.add(node);
        System.out.print(node + " ");
        for (int nei : adj.getOrDefault(node, new ArrayList<>())) {
            dfsHelper(nei, visited);
        }
    }
}