链表（单/双）与哨兵
上篇动态数组最大的软肋是：在中间插入或删除一个元素，要搬移其后所有的元素，代价 O(n)。链表（linked list）号称能绕开这个软肋——它不靠"连续内存 + 下标"组织数据，而是让每个元素自己记住"下一个是谁"。 但"链表删除是 O(1)"这句话，九成初学者都记漏了前提。这篇就把单链表、双链表、以及那个能把一堆边界特判消灭干净的**哨兵节点（sentinel）**讲透，顺便留三道面试开胃题。 一、单链表：每个节点只认识"下一个"单链表由一串 节点（Node） 串成。每个节点干两件事：存自己的数据 val，再存一个指向下一个节点的引用 next。最后一个节点的 next 是 null，表示"到头了"。一个独立的 head 引用指向第一个节点，靠它才能摸到整条链。 1 val next 2 val next 3 val next null head 本质一句话：单链表用&...
数组与动态数组（ArrayList）及均摊分析
你每天写 ArrayList、vector、list.append()，从没操心过"容量"——它好像永远装得下。但每次"满了"，它其实偷偷把整片数据搬了一次家：分配更大的内存、把旧元素逐个复制过去、再扔掉旧的。这一篇把这件"看不见的搬家"讲透，并回答一个反直觉的问题：为什么扩容是 O(n)，尾部追加却是 O(1)？ 答案叫均摊分析（amortized analysis）。 一、静态数组：快，但僵数组是最原始的数据结构：N 个同类型元素连续摆在内存里，靠下标直接寻址。 优点：随机访问 a[i] 是 O(1)——CPU 算一下 基地址 + i × 元素大小 就能取到，不依赖数组长度。 死穴：容量在创建时就钉死了。想在第 0 位插一个？后面所有元素都得往后挪，O(n)。更糟的是，满了就彻底塞不下了。 数组这层"裸"结构，正是上一篇说的"只承诺怎么存、不约束怎么用"。动态数组要解决的，就是给它套一层自动扩容的抽象。 二、动态数组：在数组上套一层"自动扩容"动态数...
数据结构导论：从数组到抽象数据类型（ADT）
很多人学完数组、链表、栈、队列，仍有一个挥之不去的困惑：这些"数据结构"到底有没有区别？为什么教科书总说 Stack 是 ADT 而不是数据结构？ 如果你也含糊，这篇就是为你写的——我们不背定义，先把这层窗户纸捅破。 缘起很朴素：数组是最原始、最"诚实"的数据结构，它把 N 个同类型元素连续摆在内存里，你用下标直接取。但它太"裸"了——它既不阻止你越界访问，也不阻止你在第 0 位插一个元素（后面所有元素都得搬）。于是自然会想：能不能定义一种"只许从一端进出"的抽象，把数组这种杂乱用法管起来？ 这正是抽象数据类型（ADT）的动机：从"怎么存"里提炼出"能做什么"。 一、先别急着写代码：什么是抽象数据类型（ADT）ADT = 一组数据值 + 一组在这些值上可做的操作（契约），它只规定"你能对我做什么"，不规定内部怎么存。 最熟悉的例子其实天天在用：整数就是 ADT。你知道 +、-、* 怎么用，但从不在乎 CPU 里是用补码还是浮点表示...
