链表与栈

超越数组 - 动态数据

当您预先知道数据的大小时，数组就非常有用。但是，当数据不可预测地到达时会发生什么——传感器读数流、人工智能要处理的任务队列，或者随着每条消息而增长的对话历史记录？您需要能够优雅地增长和收缩的结构。

输入链表、堆栈和队列 - 动态三重奏。

链表 - 节点和指针

链表将项目存储为节点链。每个节点保存两件事：数据本身和指向链中下一个节点的指针（引用）。

[data: "A" | next: →] → [data: "B" | next: →] → [data: "C" | next: null]

与数组不同，链表节点不会并排位于内存中。它们可以分散在任何地方 - 指针只是告诉您在哪里可以找到下一个。

链表与数组

|运营|数组|链接列表 | |------------|---------|-------------| |通过索引访问 | O(1) ⚡ | O(n) 🐢 | |在开头插入 | O(n) 🐢 | O(1) ⚡ | |插入中间 | O(n) 🐢 | O(1)* ⚡ | |从中间删除 | O(n) 🐢 | O(1)* ⚡ | |内存使用情况 |紧凑|额外（指针）|

*一旦找到位置 - 找到它仍然是 O(n)。

当链表获胜时

• 频繁插入和删除：如果您不断地在集合中间添加和删除项目，链表可以避免数组所需的昂贵的移动。
• 未知大小：当您不知道要存储多少项时，链表一次会增长一个节点，而无需调整大小。
• 构建其他结构：堆栈、队列和更复杂的结构通常构建在链表之上。

堆栈 - 后进先出 (LIFO)

堆栈的工作方式与一堆盘子完全相同：添加到顶部并从顶部删除。最后放入堆栈的项目是第一个取出的项目。

Push "A" → [A]
Push "B" → [A, B]
Push "C" → [A, B, C]
Pop      → [A, B]  (removed "C")
Pop      → [A]     (removed "B")

两个操作定义一个堆栈：

• 推送：将项目添加到顶部。
• 弹出：从顶部删除项目。

两者都是 O(1) - 即时的，无论堆栈大小如何。

现实世界中的堆栈

• 撤消/重做：每个文本编辑器都维护一堆操作。按 Ctrl+Z，最近的操作将弹出并反转。
• 浏览器后退按钮：您的浏览历史记录是一个堆栈。每个新页面都会被推送；单击“返回”会弹出当前页面。
• 调用堆栈：当您的代码调用函数时，该函数将被推送到调用堆栈上。完成后，它就会弹出。这就是程序跟踪它们所在位置的方式。

AI 中的堆栈