定义

链表就是线性表的链式存储方式。链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。链表通过一个指向下一个元素地址的引用将链表中的元素串起来。

分类

链表分为单向链表(Singly linked lis)、双向链表(Doubly linked list)、循环链。

单向链表

由各个内存结构通过一个 Next 指针链接在一起组成，每一个内存结构都存在后继内存结构【链尾除外】，内存结构由数据域和 Next 指针域组成。

说明

• Data 数据 + Next 指针，组成一个单链表的内存结构 ；
• 第一个内存结构称为 链头，最后一个内存结构称为 链尾；
• 链尾的 Next 指针设置为 NULL [指向空]；
• 单链表的遍历方向单一【只能从链头一直遍历到链尾】

单链表操作

双向链表

由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构【链头没有前驱，链尾没有后继】，内存结构由数据域、Prev 指针域和 Next 指针域组成。

说明

• Data 数据 + Next 指针 + Prev 指针，组成一个双向链表的内存结构；
• 第一个内存结构称为 链头，最后一个内存结构称为 链尾；
• 链头的 Prev 指针设置为 NULL， 链尾的 Next 指针设置为 NULL；
• Prev 指向的内存结构称为 前驱， Next 指向的内存结构称为 后继；
• 双向链表的遍历是双向的，即如果把从链头的 Next 一直到链尾的[NULL] 遍历方向定义为正向，那么从链尾的 Prev 一直到链头 [NULL ]遍历方向就是反向；

双向链表操作

循环链表

由各个内存结构通过一个指针 Next 链接在一起组成，每一个内存结构都存在后继内存结构，内存结构由数据域和 Next 指针域组成。
双向循环链表 [Double Circular Linked List] : 由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构，内存结构由数据域、Prev 指针域和 Next 指针域组成。

说明

• 循环链表分为单向、双向两种；
• 单向的实现就是在单链表的基础上，把链尾的 Next 指针直接指向链头，形成一个闭环；
• 双向的实现就是在双向链表的基础上，把链尾的 Next 指针指向链头，再把链头的 Prev 指针指向链尾，形成一个闭环；
• 循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头和链尾；

循环链表操作