在计算机程序里，数据存储的方式无外乎两种：顺序存储和链式存储。顺序存储的结构可以称为顺序表，也可以用数组描述，链式存储的结构可以称为链表。
我们每一个学过数据结构的都知道，它们两者各自有一些鲜明的特性，比如：

• 我们可以通过数组下标去访问数组里的元素，查询、更新的效率高，时间复杂度是O(1)，但是在中间某个位置插入或删除一个元素就要挪动后面所有的元素，时间复杂度是O(n)。
• 链表里元素之间存在指针指向关联的另一个元素，我们只能通过指针挨个去遍历访问链表里的元素，查询、更新的效率低，时间复杂度是O(n)，在中间某个位置插入或删除一个元素比较方便，只需要修改相邻指针的引用就可以了，时间复杂度是O(1)。

数组

数组的好处显而易见，它的存储结构比较紧凑，相对节省空间。每个元素都有唯一的索引，支持随机访问。但是数组所需要的空间需要一次分配够，当数组容量满时，新加入元素就要对数组进行扩容。扩容时，往往不能在原地直接扩，因为后面的内存可能已经分配给其他数据结构了，所以要重新申请一块新的更大的内存空间，将原有的数组里的元素全部复制到新的数组里，再释放原有数组的空间，这个过程时间复杂度是O(n)，可以参考Java的ArrayList。如果不加以合理的维护，内存中将产生大量碎片。

链表

链表有效地解决里数组需要扩容的问题，因为链表里的每个元素节点都不需要连续，链表的节点通过指针进行索引，每个节点只能找到它指针指向的下一个节点。正常的单向链表是从头节点开始，每个节点依次有一个指针指向它后面的节点，尾部节点指向NULL。有时候为了方便拿到前驱节点，我们会采用双向链表，也就是每个节点既包含一个指针指向后面的，也包含一个指针指向前面的。还有一种链表是循环链表，也就是说尾节点指向了头节点。

Dummy Node

翻译为哑节点或者假人头节点。

Dummy node 是一个虚拟节点，也可以认为是标杆节点。Dummy node 就是在链表表头 head 前加一个节点指向 head，即dummy -> head。Dummy node 的使用多针对单链表没有前向指针的问题，保证链表的 head 不会在删除操作中丢失。还有一种用法比较少见，就是使用 dummy node 来进行head的删除操作。所以，当链表的 head 有可能变化（被修改或者被删除）时，使用 dummy node 可以很好的简化代码，最终返回dummy.next即新的链表。

快慢指针

快慢指针指的是2个指针沿着链表向前移动的步数不一样，比如一个每次移2步，另一个每次移1步。可以通过它找到链表中间的节点以及判断链表是否循环。