CCNAIVE

20240122

2024/1/22

# 1 链表（Linked List）数据结构分析

  1. What（是什么） 链表是一种线性数据结构，它由一系列节点（Node）组成，每个节点包含两部分：数据域和指针域（或称为引用域）。数据域用于存储元素的值，而指针域则指向下一个节点的位置。链表中的元素在内存中并不一定连续存放，它们通过指针链接在一起，形成了逻辑上的线性序列。
  2. Why（为什么存在）
    • 动态特性：与数组不同，链表可以动态地增加或删除元素，不需要预先知道数据的大小或为所有可能的元素分配固定的空间，因此更适用于频繁插入和删除操作的场景。
    • 内存效率：对于大型数据集，如果内存空间不连续，则链表能更好地利用零散的内存空间，尤其是当需要分配较大对象时，避免了因内存碎片导致的大块连续空间不足的问题。
    • 灵活性：链表提供了更高的灵活性，可以根据需要实现多种变体，例如单向链表、双向链表、循环链表等。
  3. How（如何使用）
    • 基本操作：
      • 插入：在链表的任意位置插入新节点，只需更新相应位置前一个节点的指针指向新节点即可。
      • 删除：找到要删除节点的前一个节点，将其指针指向待删除节点的下一个节点，然后释放待删除节点的内存。
      • 查找：从头节点开始沿着链表遍历，直到找到指定元素或达到链表末尾。
      • 更新：定位到目标节点并修改其数据域的值。
    • 链表类型：
      • 单向链表（Singly Linked List）：每个节点只有一个指针指向下一个节点。
      • 双向链表（Doubly Linked List）：每个节点有两个指针，一个指向前一个节点，另一个指向后一个节点，使得可以在两个方向上遍历链表。
      • 循环链表（Circular Linked List）：最后一个节点的指针不是指向null，而是指向头节点，形成一个闭环。
    • 代码示例（以Java为例，创建单向链表节点类）：
1class Node {
2    int data;
3    Node next;
4
5    // 构造方法
6    public Node(int data) {
7        this.data = data;
8        this.next = null;
9    }
10}
11
12// 示例：插入节点
13public void insertAtEnd(Node head, int value) {
14    Node newNode = new Node(value);
15    if (head == null) {
16        head = newNode; // 如果链表为空，直接将新节点作为头节点
17    } else {
18        Node current = head;
19        while (current.next != null) {
20            current = current.next;
21        }
22        current.next = newNode; // 在链表末尾插入新节点
23    }
24}

链表在实际应用中广泛用于各种算法和数据结构的实现，如LRU缓存淘汰策略、哈希表的扩容机制、队列和栈的实现等

# 栈（Stack）数据结构分析

  1. What（是什么） 栈是一种线性数据结构，它遵循“后进先出”（Last In First Out, LIFO）的原则。栈中的元素只能通过一个端点进行插入或删除操作，这个端点被称为栈顶（top）。形象地说，栈就像一个垂直堆放的盘子，你每次只能从顶部取放。

  2. Why（为什么存在）

    • 简单高效：栈提供了基础且高效的内存分配和释放机制，比如在程序调用函数时，系统会使用栈来管理局部变量和函数参数。
    • 用于回溯和撤销操作：栈常用于需要恢复先前状态的操作，例如浏览器的历史记录、编辑器的撤销功能等。
    • 编译原理和算法实现：栈在编译器设计中用于解析表达式、处理括号匹配等问题；在算法实现中，如深度优先搜索（DFS）、括号匹配检验等场景也大量应用到栈。

  3. How（如何使用）

    • 基本操作：

      • push: 将元素压入栈顶，相当于向堆叠的盘子里添加新的盘子。
      • pop: 删除并返回栈顶元素，类似于从堆叠的盘子中取出最上面的一个盘子。
      • peek 或 top: 查看但不移除栈顶元素。
      • isEmpty: 检查栈是否为空。

    • 代码示例（以Java为例）：

class Stack {
    private Node top; // 定义栈顶节点引用

    class Node {
        int data;
        Node next;

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

    // 压栈操作
    public void push(int item) {
        Node newNode = new Node(item);
        if (top == null) {
            top = newNode;
        } else {
            newNode.next = top;
            top = newNode;
        }
    }

    // 出栈操作
    public int pop() {
        if (top == null) {
            throw new RuntimeException("Stack is empty");
        }
        int data = top.data;
        top = top.next;
        return data;
    }

    // 查看栈顶元素
    public int peek() {
        if (top == null) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }

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

总之，栈作为一种重要的数据结构，在计算机科学和软件工程中有广泛的应用，尤其在解决具有递归性质的问题时尤为关键。

# 队列

# 二叉树

# 排序算法

# 贪心算法

# 动态规划

20240123