开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介: 数据结构——线性表的链式表示和实现(链表总览)
+关注继续查看

链式存储结构


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

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


如何实现?


image


相关术语


image


  • 各结点由两个域组成:


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


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


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


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


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


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


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


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


循环链表示意图:


image

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


image


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


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


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


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


image


问题讨论


如何表示空表?


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


image


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


  1. 便于首元结点的处理


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


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


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


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


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


image


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


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


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


链表的优缺点


优点


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


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


缺点


  • 存储密度小


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


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构——线性表的顺序表示与实现(顺序表)
数据结构——线性表的顺序表示与实现(顺序表)
17 0
【数据结构】链表(C++)
【数据结构】链表(C++)
18 0
数据结构之链表(1)
数据结构之链表(1)
21 0
数据结构——线性表的链式存储结构2(静态链表)
数据结构——线性表的链式存储结构2(静态链表)
25 0
数据结构之链表
一、概念 (1)数组的线性序是由数组的下标决定的,链表中的顺序是由各对象中的指针所决定的 (2)链表结点结构 node *prev; node *next; int key; (3)链表结点 node *head; node *nil;//哨兵 (4)对链表的操作 LIST-SEARCH(L, k) LIST-INSERT(L, x) LIST-DELETE(
931 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载