单向链表

单向链表(singly linked list)或单链表指逻辑结构为线性表、存储结构为链式存储结构（即属于链表），且结点间只存在指向下个结点的链接（尾结点除外）。

在编程语言中，通常不直接提供链表结构。在内存中，链表分配和访问内存的方式不符合访问局部性原理，对缓存不友好，执行效率会按照缓存与内存的访问时间比例成数量级地放大，因此通常会使用动态数组代替。但是动态数组中间插入时间复杂度较高，必须要插入中间段时，会使用块状链表作为代替。

在外存中，文件间通过文件名的链表连接则是比较常见的做法。

尽管单向链表不适合直接用于内存分配，但是经常以逻辑上的形式存在。一个例子是管理内存常用的自由链表，固定内存段被划分为结点，结点间互相连接成链表，以数组的内存限制为代价保证访问的局部性，并同时用链式结构难以随机访问为代价换取插入删除的灵活性。

结构

单向链表中的每个结点可以抽象成如图所示结构。

其中含有数据域和指向下个结点的链接。链接成一个链表时如下图所示。

这个结构只需要获取第一个结点，就可以顺藤摸瓜地找到整个结构。如果只保存一个能取得第一个结点的数据，保存这个数据的变量通常称为 head ，也称为头指针(head pointer, head reference)。

修改操作中，总是需要从上一个结点操作想要插入或删除的结点，使用一个虚拟结点可以统一对头结点的操作。所以有时也保存一个虚拟结点，称为头结点(head node)。头结点中的链接就相当于上一个方法中的头指针。

在链表两端的插入通常称为头插法和尾插法。