链表

什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表概念

头指针

头指针存放的是链表第一个节点的地址。单链表有两种情况：一是包含头结点的，此时，头指针存放的是头结点的地址，而头结点是和其他节点一样，包含数据域和指针域，但头结点的数据域是无意义的，可以为空，也可以为任何数，头结点的指针域包含的是首节点的地址。

二是不包含头结点的，此时，头指针存放的就是首节点的地址。

头结点

头结点的引出是为了操作链表的删除，增、减等操作方便而引出的头结点。这样在首节点前增加元素和在其他普通结点中增加元素的操作是一样的，是为了方便。

首节点

是存放链表中第一个有效元素的结点。

链表分类

链表可以分为单链表、双链表以及循环链表。

单链表

单链表指的是链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向，也就是一种线性链表：

双向链表

双向链表是一个有序的结点序列，每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针，即 front 和 tail，front 指针指向左边结点，tail 指针指向右边结点：

循环链表

循环链表指的是在单向链表和双向链表的基础上，将两种链表的最后一个结点指向第一个结点从而实现循环，循环链表也可以细分为循环单链表和循环双链表，循环单链表如下图所示：

循环双链表如下图所示：

链表特点

高效的插入和删除

链表的插入和删除元素只需要修改链表节点的指针的指向即可，不需要移动任何的元素。

低效的随机访问

要访问链表的某个元素只能通过遍历的方式，没办法通过使用下标索引直接获取的方式。

图解链表

单链表的结构如下图所示：

我们看到，我们定义了一个单链表，该链表包含了一个头结点 head，其指向了链表的第一个结点，并且，链表的每一个结点都包含了两个域，一个数据域和一个指针域。

其中，数据域保存的是链表每个结点的数据，指针域保存的是当前结点的下一个结点的地址。

链表结构

链表的结构定义如下：

struct Node{
	int data;
	struct Node *pNext;
}

其中，data 保存的时候每个结点的数据，pNext 保存的是链表的当前结点的下一个结点。