干货:一文弄懂链表结构,以后再也别问我什么是链表数据结构啦!
链表 [Linked List]:链表是由一组不必相连【不必相连:可以连续也可以不连续】的内存结构 【节点】,按特定的顺序链接在一起的抽象数据类型。链表常用的有 3 类: 单链表、双向链表、循环链表。链表的核心操作集有 3 种:插入、删除、查找【遍历】。
1、 单链表:由各个内存结构通过一个Next 指针链接组成,每一个内存结构都存在后继内存结构【链尾除外】,内存结构由数据域和Next指针域组成。
文字解析:
Date数据+Next指针,组成一个单链表内存结构;
第一个内存结构成为:链头,最后一个内存结构称为链尾;
链尾的Next指针设置为NULL[指向空];
单链表的遍历只能从头到尾一直遍历;
2、 双向链表:[Double Linked List]:由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成,每一个内存结构都存在前驱内存结构和后继内存结构【链头没有前驱,链尾没有后继】,内存结构由数据域、Prev 指针域和 Next 指针域组成。
文字解析:
Data 数据 + Next 指针 + Prev 指针,组成一个双向链表的内存结构;
第一个内存结构称为 链头,最后一个内存结构称为 链尾;
链头的 Prev 指针设置为 NULL, 链尾的 Next 指针设置为 NULL;
Prev 指向的内存结构称为 前驱, Next 指向的内存结构称为 后继;
双向链表的遍历是双向的,即如果把从链头的 Next 一直到链尾的[NULL] 遍历方向定义为正向,那么从链尾的 Prev 一直到链头 [NULL ]遍历方向就是反向
3、 单向循环链表 [Circular Linked List] : 由各个内存结构通过一个指针 Next 链接在一起组成,每一个内存结构都存在后继内存结构,内存结构由数据域和 Next 指针域组成。
双向循环链表 [Double Circular Linked List] : 由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成,每一个内存结构都存在前驱内存结构和后继内存结构,内存结构由数据域、Prev 指针域和 Next 指针域组成。
文字解析:
循环链表分为单向、双向两种;
单向的实现就是在单链表的基础上,把链尾的 Next 指针直接指向链头,形成一个闭环;
双向的实现就是在双向链表的基础上,把链尾的 Next 指针指向链头,再把链头的 Prev 指针指向链尾,形成一个闭环;
循环链表没有链头和链尾的说法,因为是闭环的,所以每一个内存结构都可以充当链头和链尾;
4、 静态链表: 让数组的元素都是由两个数据组成,data 和 cur . 即数组的每个下标都对应一个data和 cur . 数据域data 用来存放数据元素 ,游标cur 相当于单链表中的指针, 存放该元素的后继在数组中的下标. 这种用数组描述的链表叫静态链表. 其在插入和删除操作时,只需要修改游标,不需要移动元素. 但是没有解决连续储存分配带来的表长难以确定的问题,且失去了顺序存储结构随机存储的特性。
本文内容大部分参照 作者: 半纸渊 https://www.jianshu.com/p/73d56c3d228c
(想要更详细解释请点击此链接查阅)