什么是数据结构

数据结构是计算机存储、组织数据的方式，它描述了数据元素之间的逻辑关系。好的数据结构设计可以提高算法的效率，是编程的基础。

主要分类

• 线性结构：数组、链表、栈、队列
• 树形结构：二叉树、AVL树、红黑树、B树
• 图形结构：图、邻接矩阵、邻接表
• 散列结构：HashMap、HashSet、布隆过滤器

线性结构

1. 数组（Array）

基本概念

• 连续的内存空间
• 通过索引访问元素
• 固定长度（Java中可变）

Java实现

public class ArrayDemo {
    public static void main(String[] args) {
        // 一维数组
        int[] numbers = {1, 2, 3, 4, 5};
        
        // 二维数组
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        
        // 动态数组
        ArrayList<Integer> dynamicArray = new ArrayList<>();
        dynamicArray.add(1);
        dynamicArray.add(2);
        dynamicArray.add(3);
        
        // 数组操作
        System.out.println("数组长度: " + numbers.length);
        System.out.println("第一个元素: " + numbers[0]);
        System.out.println("最后一个元素: " + numbers[numbers.length - 1]);
    }
}

时间复杂度

• 访问：O(1)
• 查找：O(n)
• 插入：O(n)
• 删除：O(n)

2. 链表（Linked List）

基本概念

• 节点通过指针连接
• 不连续的内存空间
• 支持动态增删

Java实现

// 链表节点
class ListNode {
    int val;
    ListNode next;
    
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

// 单链表
public class LinkedList {
    private ListNode head;
    private int size;
    
    public LinkedList() {
        this.head = null;
        this.size = 0;
    }
    
    // 在头部插入
    public void addFirst(int val) {
        ListNode newNode = new ListNode(val);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // 在尾部插入
    public void addLast(int val) {
        if (head == null) {
            head = new ListNode(val);
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = new ListNode(val);
        }
        size++;
    }
    
    // 删除指定值
    public boolean remove(int val) {
        if (head == null) return false;
        
        if (head.val == val) {
            head = head.next;
            size--;
            return true;
        }
        
        ListNode current = head;
        while (current.next != null) {
            if (current.next.val == val) {
                current.next = current.next.next;
                size--;
                return true;
            }
            current = current.next;
        }
        return false;
    }
    
    // 查找元素
    public boolean contains(int val) {
        ListNode current = head;
        while (current != null) {
            if (current.val == val) {
                return true;
            }
            current = current.next;
        }
        return false;
    }
    
    // 获取大小
    public int size() {
        return size;
    }
    
    // 打印链表
    public void print() {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

时间复杂度

• 访问：O(n)
• 查找：O(n)
• 插入：O(1)（头部）/ O(n)（尾部）
• 删除：O(1)（头部）/ O(n)（尾部）

3. 栈（Stack）

基本概念

• 后进先出（LIFO）
• 只能在一端操作
• 常用于函数调用、表达式求值

Java实现

public class Stack<T> {
    private ArrayList<T> elements;
    
    public Stack() {
        this.elements = new ArrayList<>();
    }
    
    // 入栈
    public void push(T element) {
        elements.add(element);
    }
    
    // 出栈
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return elements.remove(elements.size() - 1);
    }
    
    // 查看栈顶
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return elements.get(elements.size() - 1);
    }
    
    // 判断是否为空
    public boolean isEmpty() {
        return elements.isEmpty();
    }
    
    // 获取大小
    public int size() {
        return elements.size();
    }
}

// 使用示例
public class StackDemo {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        
        // 入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        
        System.out.println("栈大小: " + stack.size());
        System.out.println("栈顶元素: " + stack.peek());
        
        // 出栈
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        System.out.println();
    }
}

时间复杂度

• 入栈：O(1)
• 出栈：O(1)
• 查看栈顶：O(1)

4. 队列（Queue）

基本概念

• 先进先出（FIFO）
• 一端入队，另一端出队
• 常用于广度优先搜索、任务调度

Java实现

public class Queue<T> {
    private ArrayList<T> elements;
    
    public Queue() {
        this.elements = new ArrayList<>();
    }
    
    // 入队
    public void enqueue(T element) {
        elements.add(element);
    }
    
    // 出队
    public T dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return elements.remove(0);
    }
    
    // 查看队首
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return elements.get(0);
    }
    
    // 判断是否为空
    public boolean isEmpty() {
        return elements.isEmpty();
    }
    
    // 获取大小
    public int size() {
        return elements.size();
    }
}

// 使用示例
public class QueueDemo {
    public static void main(String[] args) {
        Queue<String> queue = new Queue<>();
        
        // 入队
        queue.enqueue("任务1");
        queue.enqueue("任务2");
        queue.enqueue("任务3");
        
        System.out.println("队列大小: " + queue.size());
        System.out.println("队首任务: " + queue.peek());
        
        // 出队
        while (!queue.isEmpty()) {
            System.out.println("处理任务: " + queue.dequeue());
        }
    }
}

时间复杂度

• 入队：O(1)
• 出队：O(n)（需要移动元素）
• 查看队首：O(1)

树形结构

1. 二叉树（Binary Tree）

基本概念

• 每个节点最多有两个子节点
• 左子树和右子树
• 常用于搜索和排序

Java实现

// 二叉树节点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 二叉树
public class BinaryTree {
    private TreeNode root;
    
    public BinaryTree() {
        this.root = null;
    }
    
    // 插入节点
    public void insert(int val) {
        root = insertRec(root, val);
    }
    
    private TreeNode insertRec(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        
        if (val < root.val) {
            root.left = insertRec(root.left, val);
        } else if (val > root.val) {
            root.right = insertRec(root.right, val);
        }
        
        return root;
    }
    
    // 中序遍历
    public void inorderTraversal() {
        inorderRec(root);
    }
    
    private void inorderRec(TreeNode root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.val + " ");
            inorderRec(root.right);
        }
    }
    
    // 前序遍历
    public void preorderTraversal() {
        preorderRec(root);
    }
    
    private void preorderRec(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            preorderRec(root.left);
            preorderRec(root.right);
        }
    }
    
    // 后序遍历
    public void postorderTraversal() {
        postorderRec(root);
    }
    
    private void postorderRec(TreeNode root) {
        if (root != null) {
            postorderRec(root.left);
            postorderRec(root.right);
            System.out.print(root.val + " ");
        }
    }
    
    // 层序遍历
    public void levelOrderTraversal() {
        if (root == null) return;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            System.out.print(current.val + " ");
            
            if (current.left != null) {
                queue.offer(current.left);
            }
            if (current.right != null) {
                queue.offer(current.right);
            }
        }
    }
    
    // 查找节点
    public boolean search(int val) {
        return searchRec(root, val);
    }
    
    private boolean searchRec(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root != null;
        }
        
        if (val < root.val) {
            return searchRec(root.left, val);
        }
        return searchRec(root.right, val);
    }
}

时间复杂度

• 查找：O(log n)（平衡树）/ O(n)（不平衡树）
• 插入：O(log n)（平衡树）/ O(n)（不平衡树）
• 删除：O(log n)（平衡树）/ O(n)（不平衡树）

2. 平衡二叉树（AVL Tree）

基本概念

• 自平衡的二叉搜索树
• 左右子树高度差不超过1
• 通过旋转操作保持平衡

Java实现

class AVLNode {
    int val;
    AVLNode left;
    AVLNode right;
    int height;
    
    AVLNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.height = 1;
    }
}

public class AVLTree {
    private AVLNode root;
    
    // 获取节点高度
    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }
    
    // 获取平衡因子
    private int getBalance(AVLNode node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }
    
    // 右旋转
    private AVLNode rightRotate(AVLNode y) {
        AVLNode x = y.left;
        AVLNode T2 = x.right;
        
        x.right = y;
        y.left = T2;
        
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        
        return x;
    }
    
    // 左旋转
    private AVLNode leftRotate(AVLNode x) {
        AVLNode y = x.right;
        AVLNode T2 = y.left;
        
        y.left = x;
        x.right = T2;
        
        x.height = Math.max(height(x.left), height(x.right)) + 1;
        y.height = Math.max(height(y.left), height(y.right)) + 1;
        
        return y;
    }
    
    // 插入节点
    public void insert(int val) {
        root = insertRec(root, val);
    }
    
    private AVLNode insertRec(AVLNode node, int val) {
        if (node == null) {
            return new AVLNode(val);
        }
        
        if (val < node.val) {
            node.left = insertRec(node.left, val);
        } else if (val > node.val) {
            node.right = insertRec(node.right, val);
        } else {
            return node; // 重复值
        }
        
        // 更新高度
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        
        // 获取平衡因子
        int balance = getBalance(node);
        
        // 左左情况
        if (balance > 1 && val < node.left.val) {
            return rightRotate(node);
        }
        
        // 右右情况
        if (balance < -1 && val > node.right.val) {
            return leftRotate(node);
        }
        
        // 左右情况
        if (balance > 1 && val > node.left.val) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        
        // 右左情况
        if (balance < -1 && val < node.right.val) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        
        return node;
    }
}

图形结构

1. 图（Graph）

基本概念

• 由顶点和边组成
• 有向图和无向图
• 常用于网络、社交关系建模

Java实现

import java.util.*;

class Graph {
    private Map<Integer, List<Integer>> adjacencyList;
    
    public Graph() {
        this.adjacencyList = new HashMap<>();
    }
    
    // 添加顶点
    public void addVertex(int vertex) {
        if (!adjacencyList.containsKey(vertex)) {
            adjacencyList.put(vertex, new ArrayList<>());
        }
    }
    
    // 添加边
    public void addEdge(int source, int destination) {
        addVertex(source);
        addVertex(destination);
        adjacencyList.get(source).add(destination);
        // 无向图需要添加反向边
        // adjacencyList.get(destination).add(source);
    }
    
    // 深度优先搜索
    public void dfs(int startVertex) {
        Set<Integer> visited = new HashSet<>();
        dfsRec(startVertex, visited);
    }
    
    private void dfsRec(int vertex, Set<Integer> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");
        
        for (int neighbor : adjacencyList.get(vertex)) {
            if (!visited.contains(neighbor)) {
                dfsRec(neighbor, visited);
            }
        }
    }
    
    // 广度优先搜索
    public void bfs(int startVertex) {
        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        visited.add(startVertex);
        queue.offer(startVertex);
        
        while (!queue.isEmpty()) {
            int vertex = queue.poll();
            System.out.print(vertex + " ");
            
            for (int neighbor : adjacencyList.get(vertex)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
    
    // 检查是否有环
    public boolean hasCycle() {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> recStack = new HashSet<>();
        
        for (int vertex : adjacencyList.keySet()) {
            if (hasCycleUtil(vertex, visited, recStack)) {
                return true;
            }
        }
        return false;
    }
    
    private boolean hasCycleUtil(int vertex, Set<Integer> visited, Set<Integer> recStack) {
        if (recStack.contains(vertex)) {
            return true;
        }
        
        if (visited.contains(vertex)) {
            return false;
        }
        
        visited.add(vertex);
        recStack.add(vertex);
        
        for (int neighbor : adjacencyList.get(vertex)) {
            if (hasCycleUtil(neighbor, visited, recStack)) {
                return true;
            }
        }
        
        recStack.remove(vertex);
        return false;
    }
}

散列结构

1. HashMap

基本概念

• 键值对存储
• 通过哈希函数计算存储位置
• 平均时间复杂度O(1)

Java实现

public class CustomHashMap<K, V> {
    private static final int DEFAULT_CAPACITY = 16;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    private Node<K, V>[] table;
    private int size;
    private float loadFactor;
    
    @SuppressWarnings("unchecked")
    public CustomHashMap() {
        this.table = new Node[DEFAULT_CAPACITY];
        this.size = 0;
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }
    
    // 内部节点类
    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V> next;
        
        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.next = null;
        }
    }
    
    // 计算哈希值
    private int hash(K key) {
        return key == null ? 0 : Math.abs(key.hashCode() % table.length);
    }
    
    // 放入键值对
    public V put(K key, V value) {
        int index = hash(key);
        
        if (table[index] == null) {
            table[index] = new Node<>(key, value);
        } else {
            Node<K, V> current = table[index];
            while (current.next != null) {
                if (Objects.equals(current.key, key)) {
                    V oldValue = current.value;
                    current.value = value;
                    return oldValue;
                }
                current = current.next;
            }
            
            if (Objects.equals(current.key, key)) {
                V oldValue = current.value;
                current.value = value;
                return oldValue;
            }
            
            current.next = new Node<>(key, value);
        }
        
        size++;
        
        // 检查是否需要扩容
        if ((float) size / table.length >= loadFactor) {
            resize();
        }
        
        return null;
    }
    
    // 获取值
    public V get(K key) {
        int index = hash(key);
        Node<K, V> current = table[index];
        
        while (current != null) {
            if (Objects.equals(current.key, key)) {
                return current.value;
            }
            current = current.next;
        }
        
        return null;
    }
    
    // 删除键值对
    public V remove(K key) {
        int index = hash(key);
        Node<K, V> current = table[index];
        Node<K, V> prev = null;
        
        while (current != null) {
            if (Objects.equals(current.key, key)) {
                if (prev == null) {
                    table[index] = current.next;
                } else {
                    prev.next = current.next;
                }
                size--;
                return current.value;
            }
            prev = current;
            current = current.next;
        }
        
        return null;
    }
    
    // 检查是否包含键
    public boolean containsKey(K key) {
        return get(key) != null;
    }
    
    // 获取大小
    public int size() {
        return size;
    }
    
    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    
    // 扩容
    @SuppressWarnings("unchecked")
    private void resize() {
        Node<K, V>[] oldTable = table;
        table = new Node[table.length * 2];
        size = 0;
        
        for (Node<K, V> node : oldTable) {
            while (node != null) {
                put(node.key, node.value);
                node = node.next;
            }
        }
    }
}

最佳实践

1. 选择合适的数据结构

// 需要快速访问：使用数组或HashMap
int[] numbers = new int[1000];
HashMap<String, Integer> cache = new HashMap<>();

// 需要频繁插入删除：使用链表
LinkedList<String> tasks = new LinkedList<>();

// 需要后进先出：使用栈
Stack<String> undoStack = new Stack<>();

// 需要先进先出：使用队列
Queue<String> taskQueue = new LinkedList<>();

// 需要排序和搜索：使用树
TreeSet<Integer> sortedNumbers = new TreeSet<>();

2. 性能优化

// 预分配容量
ArrayList<Integer> list = new ArrayList<>(1000);
HashMap<String, Integer> map = new HashMap<>(1000, 0.75f);

// 使用迭代器而不是索引
for (Integer num : list) {
    System.out.println(num);
}

// 避免装箱拆箱
int[] primitiveArray = new int[1000]; // 而不是 Integer[]

3. 内存管理

// 及时清理引用
public void cleanup() {
    // 清理不再使用的数据结构
    list.clear();
    map.clear();
    stack.clear();
    queue.clear();
}

// 使用弱引用避免内存泄漏
WeakHashMap<String, Object> weakMap = new WeakHashMap<>();