链表

修改元素无需移动

头结点和头指针的区别

头指针指向的是头结点. 内容是头结点的地址. 而头结点是链表的第一个结点. 一般不存放信息. 删除结点后队列为空时，必须特殊处理。

1. 静态链表：一个结构体数组，一个data，一个next。静态链表的指针不是内存地址的指针型变量，而是存储数组下标的整型变量。
2. 双向链表：不提高查找速度。

class node {
    private:
    int _value;
    node * next;
    node * prior; //双链表
}

操作

1. 查找中间结点: 使用快慢指针法.

删除节点 P 后，是否需要把 P.next 设为 None 呢？

从做题的角度看，不断开没有关系，只要保证程序的逻辑是正确的就行。从标准库的角度看，断开更加安全、逻辑更加清晰。如果不断开，假设被删除节点未被正常回收，那么它会影响后继节点的内存回收。

列表list

「列表 list」是一个抽象的数据结构概念，它表示元素的有序集合，支持元素访问、修改、添加、删除和遍历等操作，无须使用者考虑容量限制的问题。列表可以基于链表或数组实现。

链表天然可以看作一个列表，其支持元素增删查改操作，并且可以灵活动态扩容。 数组也支持元素增删查改，但由于其长度不可变，因此只能看作一个具有长度限制的列表。 当使用数组实现列表时，长度不可变的性质会导致列表的实用性降低。这是因为我们通常无法事先确定需要存储多少数据，从而难以选择合适的列表长度。若长度过小，则很可能无法满足使用需求；若长度过大，则会造成内存空间浪费。

为解决此问题，我们可以使用「动态数组 dynamic array」来实现列表。它继承了数组的各项优点，并且可以在程序运行过程中进行动态扩容。

实际上，许多编程语言中的标准库提供的列表是基于动态数组实现的，例如 Python 中的 list 、Java 中的 ArrayList 、C++ 中的 vector 和 C# 中的 List 等。在接下来的讨论中，我们将把“列表”和“动态数组”视为等同的概念。

许多编程语言内置了列表，例如 Java、C++、Python 等。它们的实现比较复杂，各个参数的设定也非常考究，例如初始容量、扩容倍数等。感兴趣的读者可以查阅源码进行学习。

为了加深对列表工作原理的理解，我们尝试实现一个简易版列表，包括以下三个重点设计。

初始容量：选取一个合理的数组初始容量。在本示例中，我们选择 10 作为初始容量。 数量记录：声明一个变量 size ，用于记录列表当前元素数量，并随着元素插入和删除实时更新。根据此变量，我们可以定位列表尾部，以及判断是否需要扩容。 扩容机制：若插入元素时列表容量已满，则需要进行扩容。先根据扩容倍数创建一个更大的数组，再将当前数组的所有元素依次移动至新数组。在本示例中，我们规定每次将数组扩容至之前的 2 倍。

“列表的出现极大地提高了数组的实用性，但可能导致部分内存空间浪费”，这里的空间浪费是指额外增加的变量如容量、长度、扩容倍数所占的内存吗？

这里的空间浪费主要有两方面含义：一方面，列表都会设定一个初始长度，我们不一定需要用这么多；另一方面，为了防止频繁扩容，扩容一般会乘以一个系数，比如 。这样一来，也会出现很多空位，我们通常不能完全填满它们。

C++ STL 里面的 std::list 已经实现了双向链表，但好像一些算法书上不怎么直接使用它，是不是因为有什么局限性呢？

一方面，我们往往更青睐使用数组实现算法，而只在必要时才使用链表，主要有两个原因。

空间开销：由于每个元素需要两个额外的指针（一个用于前一个元素，一个用于后一个元素），所以 std::list 通常比 std::vector 更占用空间。 缓存不友好：由于数据不是连续存放的，因此 std::list 对缓存的利用率较低。一般情况下，std::vector 的性能会更好。 另一方面，必要使用链表的情况主要是二叉树和图。栈和队列往往会使用编程语言提供的 stack 和 queue ，而非链表。