【0.3 漫画数据结构与算法】

📚 漫画数据结构与算法

🎯 学习目标：掌握计算机科学基础的数据结构与算法，为后续技术学习打下坚实基础

🏗️ 第一章：线性数据结构篇

📋 数组与动态数组

📋 数组特性解析：

内存布局：
┌─────────────────────────────────────────┐
│ 数组在内存中的连续存储                  │
│ ┌─────┬─────┬─────┬─────┬─────┬─────┐ │
│ │ [0] │ [1] │ [2] │ [3] │ [4] │ [5] │ │
│ │ 10  │ 20  │ 30  │ 40  │ 50  │ 60  │ │
│ └─────┴─────┴─────┴─────┴─────┴─────┘ │
│   ↑                                    │
│ 基址                                   │
│                                        │
│ 访问公式：address = base + index * size │
└─────────────────────────────────────────┘

时间复杂度：
• 访问：O(1) - 随机访问
• 查找：O(n) - 线性查找
• 插入：O(n) - 需要移动元素
• 删除：O(n) - 需要移动元素

🎨 Java实现示例：

// 动态数组实现
public class DynamicArray<T> {
   
    private Object[] array;
    private int size;
    private int capacity;
    
    public DynamicArray() {
   
        this.capacity = 10;
        this.array = new Object[capacity];
        this.size = 0;
    }
    
    // 扩容操作
    private void resize() {
   
        capacity *= 2;
        Object[] newArray = new Object[capacity];
        System.arraycopy(array, 0, newArray, 0, size);
        array = newArray;
    }
    
    // 添加元素
    public void add(T element) {
   
        if (size >= capacity) {
   
            resize();
        }
        array[size++] = element;
    }
    
    // 插入元素
    public void insert(int index, T element) {
   
        if (index < 0 || index > size) {
   
            throw new IndexOutOfBoundsException();
        }
        if (size >= capacity) {
   
            resize();
        }
        // 移动元素
        for (int i = size; i > index; i--) {
   
            array[i] = array[i - 1];
        }
        array[index] = element;
        size++;
    }
    
    // 删除元素
    public T remove(int index) {
   
        if (index < 0 || index >= size) {
   
            throw new IndexOutOfBoundsException();
        }
        @SuppressWarnings("unchecked")
        T removed = (T) array[index];
        // 移动元素
        for (int i = index; i < size - 1; i++) {
   
            array[i] = array[i + 1];
        }
        size--;
        return removed;
    }
}

🔗 链表结构

🔗 链表类型对比：

单向链表：
┌─────┬─────┐   ┌─────┬─────┐   ┌─────┬──────┐
│Data │Next │──→│Data │Next │──→│Data │ null │
└─────┴─────┘   └─────┴─────┘   └─────┴──────┘
   Head                            Tail

双向链表：
     ┌─────┬─────┬─────┐   ┌─────┬─────┬─────┐
null←│Prev │Data │Next │←→│Prev │Data │Next │→null
     └─────┴─────┴─────┘   └─────┴─────┴─────┘
        Head                    Tail

循环链表：
┌─────┬─────┐   ┌─────┬─────┐   ┌─────┬─────┐
│Data │Next │──→│Data │Next │──→│Data │Next │
└─────┴─────┘   └─────┴─────┘   └─────┴─────┘
   ↑                               │
   └───────────────────────────────┘

🎨 链表实现：

// 单向链表实现
public class LinkedList<T> {
   
    private Node<T> head;
    private int size;
    
    private static class Node<T> {
   
        T data;
        Node<T> next;
        
        Node(T data) {
   
            this.data = data;
        }
    }
    
    // 头部插入
    public void addFirst(T data) {
   
        Node<T> newNode = new Node<>(data);
        newNode.next = head;
        head = newNode;
        size++;
    }
    
    // 尾部插入
    public void addLast(T data) {
   
        Node<T> newNode = new Node<>(data);
        if (head == null) {
   
            head = newNode;
        } else {
   
            Node<T> current = head;
            while (current.next != null) {
   
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }
    
    // 删除节点
    public boolean remove(T data) {
   
        if (head == null) return false;
        
        if (head.data.equals(data)) {
   
            head = head.next;
            size--;
            return true;
        }
        
        Node<T> current = head;
        while (current.next != null) {
   
            if (current.next.data.equals(data)) {
   
                current.next = current.next.next;
                size--;
                return true;
            }
            current = current.next;
        }
        return false;
    }
}

📚 栈与队列

📚 栈和队列对比：

栈 (Stack) - LIFO(后进先出)：
│   ┌─────┐ ←── top     │ push/pop操作
│   │  3  │             │
│   ├─────┤             │
│   │  2  │             │
│   ├─────┤             │
│   │  1  │             │
│   └─────┘             │

队列 (Queue) - FIFO(先进先出)：
    enqueue          dequeue
      ↓                ↑
┌─────┬─────┬─────┬─────┐
│  1  │  2  │  3  │  4  │
└─────┴─────┴─────┴─────┘
 rear              front

优先队列 (Priority Queue)：
┌─────────────────────────────────────────┐
│ 基于堆实现的优先队列                    │
│        1(优先级最高)                    │
│      /   \                              │
│     3     2                             │
│   /  \   /                              │
│  7    4 5                               │
│                                         │
│ 特点：每次出队都是优先级最高的元素       │
└─────────────────────────────────────────┘

🌳 第二章：树形数据结构篇

🌲 二叉树与二叉搜索树

// 二叉搜索树实现
public class BinarySearchTree<T extends Comparable<