链表

链表
术语名称	链表
英语名称	linked list

链表(linked list)指逻辑结构为线性表、存储结构为链式存储结构的数据结构。当不说明链表的具体种类时，默认指代的是单向链表。

链表主要包括单向链表、双向链表、单向循环链表、双向循环链表四种，根据其中的链接与循环性进行区分。通常链表类数据结构的内部存在三种主要区别。

1. 单向/双向：指链表结点中的链接。若每个结点只有指向下一结点（线性表中的后继）的链接，称为单向；若结点中除指向下一结点的链接外，还含有指向上一结点（线性表中的前趋）的链接，称为双向。
2. 哨兵结点：通过在头部和尾部增加头结点和尾结点，可以简化部分实现，称为头结点和尾结点。循环链表只需要一个哨兵结点，称为头结点。头结点可以统一首结点（第一个数据结点）与非首结点的操作。
3. 循环/不循环：指链表的最后一个结点的链接是否指向第一个结点（均包括哨兵结点），也就是使用指向另一端的链接代替空链接。