说说“链表”这种数据结构

我们对数组这种数据结构很熟悉，知道数组需要一块连续的内存空间来存储。但是，对链表却很陌生，其实， 链表是不需要一块连续的内存空间，它通过指针将一组零散的内存块串联起来使用。

那些内存块称为链表的“结点”，为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址，所以，记录下个结点地址的指针叫作后继指针 next。

链表有三种最常见的结构，它们分别是：单链表、双向链表和循环链表。

单向链表

有2个特殊结点，头结点和尾结点，头结点：第一个结点，头结点用来记录链表的基地址，有了它，就可以遍历得到整条链表。尾结点：最后一个结点，指针不是指向下一个结点，而是指向一个空地址 NULL，表示这是链表上最后一个结点。

循环链表

是一种特殊的单链表

可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。

双向链表

双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。