数据结构——线性表的链式表示和实现(链表总览)

简介: 数据结构——线性表的链式表示和实现(链表总览)

链式存储结构


结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻

线性表的链式表示又称为非顺序映像或链式映像。


如何实现?



相关术语



  • 各结点由两个域组成:


数据域:存储元素数值数据


指针域:存储直接后继结点的存储位置


  • 结点:数据元素的存储映像。由数据域和指针域两部分组成


  • 链表:n个结点由指针链组成一个链表。它是线性表的链式存储映像,称为线性表的链式存储结构。


  • 单链表、双链表、循环链表:


结点只有一个指针域的链表,称为单链表或线性链表


有两个指针域的链表,称为双链表


首尾相接的链表称为循环链表


循环链表示意图:


  • 头指针、头结点和首元结点



头指针是指向链表中第一个结点的指针


首元结点是指链表中存储第一个数据元素a1的结点


头结点是在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息


上例链表的逻辑结构示意图有以下两种形式:



问题讨论


如何表示空表?


有头结点时,当头结点的指针域为空时表示空表



在链表中设置头结点有什么好处?


  1. 便于首元结点的处理


首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致,无须进行特殊处理;


  1. 便于空表和非空表的统一处理


无论链表是否为空,头指针都是指向头结点的非空指针,因此空表和非空表的处理也就统一了。


头结点的数据域内装的是什么?


头结点的数据域可以为空,也可存放线性表长度等附加信息,但此结点不能计入链表长度值。



链表(链式存储结构)的特点


(1)结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻


(2)访问时只能通过头指针进入链表,并通过每个结点的指针域向后扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间不等


链表的优缺点


优点


  • 数据元素的个数可以自由扩充


  • 插入、删除等操作不必移动数据,只需修改链接指针,修改效率较高


缺点


  • 存储密度小


  • 存取效率不高,必须采用顺序存取,即存取数据元素时,只能按链表的顺序进行访问(顺藤摸瓜)


相关文章
|
7天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
32 4
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
28天前
|
算法 Java
数据结构与算法学习五:双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现,并通过实例演示了双向链表的优势和应用。
15 0
数据结构与算法学习五:双链表的增、删、改、查
|
7天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
24 0
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
21天前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
17 0
|
27天前
|
存储
探索数据结构:便捷的双向链表
探索数据结构:便捷的双向链表
|
27天前
|
存储
探索数据结构:单链表的实践和应用
探索数据结构:单链表的实践和应用
|
28天前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
16 0