链表

链式储存结构称之为链表，又称线性链表，分为：单链表、双向链表、循环链表。可以用任意一组储存单元来储存链表的数据元素（储存单元可以是不连续的）。除了储存每一个元素外，还必须初春指示其直接后继元素的信息。这两部分称之为节点，多个节点组成了链表。

单链表

链表中每一个结点是用一个数据域和一个指针域来描述，数据域存储数据元素，指针域存储后继结点的地址。线性链表的最后一个结点无后继结点，它的指针域为空（记为 NULL 或∧）。另外，还要设置表头指针 head ，指向线性链表的第一个结点。

链表与顺序表不同，它通常采用动态分配内存的方法，链表中的每个结点占用的存储空间不是预先分配的，而是运行时系统根据需要临时生成的。链表的一个重要特征是插入、删除运算灵活方便，无需移动结点，只要改变结点中指针域的值即可

双向链表

链表中每一个结点是用一个数据域和两个指针域来描述，数据域存储数据元素，指针域一个存储前驱结点的地址，一个存储后继结点的地址。线性链表的第一个结点无前驱结点，它的前驱指针为空，最后一个结点无后继结点，它的后继指针为空。另外，还要设置表头指针 head ，指向线性链表的第一个结点。

循环链表

把单链表中最后一个结点的指针域的值改为第一个结点的地址，即构成循环链表。

顺序表和链表的区别：

• 顺序表只存放数据，不存放逻辑关系，所以顺序表存储密度大，节省空间，而链表除了要存储数据外，还要存储数据的逻辑关系，占用空间较大
• 顺序表按地址顺序存放数据，有一定规律，所以存取、查询等速度快。而链表不按顺序存储，数据存放地址无规律可循，查找数据需从表头开始，所以存取、查询等速度慢
• 顺序表插入和删除数据需移动数据位置，而链表无需移动，所以顺序表插入和删除操作麻烦，而链表插入和删除操作方便