链表(Linked list)是算法中常用的一种基础数据结构，是一种链式存储结构的线性表。
简介
定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列节点(链表中每一个元素称为节点)组成，节点可以在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。
特点
链表是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。
优点
链表的优点就是插入和删除操作会非常快，时间复杂度为 O(1)。
缺点
链表的缺点就是要找一个元素，必须要从头开始找起，时间复杂度为 O(n)。
分类
链表有很多种不同的类型：单向链表、双向链表以及循环链表。
单向链表
单向链表指的是链表中的节点的指针域只能指向链表中的下一个节点或者指向 NULL，节点之间不能相互指向，单向链表是链表中结构最简单的。
单向链表只能从一个方向进行遍历。
结构
单向链表有一个头节点和一个尾节点，头节点没有值域，只有链域，专门存放第一个节点的地址；尾节点，有值域，也有链域，链域值始终为NULL。
对于单向链表，如果想在尾部添加一个节点，那么必须从头部一直遍历到尾部，找到尾节点，然后在尾节点后面插入一个节点。
效率分析
单向链表的效率分析如下：
- 链表插入和删除操作的时间复杂度均为
O(n)； - 链表读取操作的时间复杂度为
O(n)。
优缺点
单向链表的优缺点如下：
- 优点：插入和删除操作不需要移动数据元素。
- 缺点：只能从头到尾遍历，只能找到后继，无法找到前驱，不支持随机读取。
双向链表
双向链表其实是单向链表的改进，在双向链表中，节点除含有数据域外，还有两个链域，一个存储直接后继节点地址，一般称之为右链域；一个存储直接前驱节点地址，一般称之为左链域。
双向链表是可以从两个方向进行遍历的。
优缺点
双向链表的优缺点如下：
- 优点：查找元素时可以从两个方向进行遍历，一定程度上提升了查找数据元素的速度。
- 缺点：增加、删除节点复杂，需要多分配一个指针存储空间，增加了额外的内存开销。
循环链表
循环链表指的是在单向链表和双向链表的基础上，将两种链表的最后一个节点指向第一个节点从而实现循环。
循环链表与单向链表和循环链表有以下不同：
- 在建立一个循环链表时，必须使其最后一个节点的指针指向表头节点，而不是象单链表那样置为 NULL。此种情况还使用于在最后一个节点后插入一个新的节点。
- 在判断是否到表尾时，是判断该节点链域的值是否是表头节点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为 NULL。
循环链表是一个链表环。
优缺点
循环链表的优缺点如下：
- 优点：没有 NULL 指针，遍历的时候可以从任意节点开始，增加了遍历的灵活性。
- 缺点：没有解决单链表查找元素速度较慢的问题。
