<数据结构> 链表 - 链表的概念及结构

简介: <数据结构> 链表 - 链表的概念及结构

1、 链表的概念


概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的


1、链表由一系列结点(链表中每一个元素称为结点)组成。


2、结点可以在运行时动态(malloc)生成。


3、每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域(详见1.2 节点部分)。


4、相比于线性表顺序结构,链表操作复杂。但是由于不需按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比顺序表快得多;但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表只需O(1)


2、 结点


链表由一个个结点构成,每个结点采用结构体的形式。结构体内前面的变量按照需要给予,最后一个变量是这个结构体类型的指针,用来存放下一节点的首地址‘


链表结点分为两个域

数据域 :存放各种实际的数据

指针域 :存放下一结点的地址

(图为带哨兵位头结点的链表)


3、 链表的使用场景


线性表在 需要经常插入或删除数据元素 的情况下适合采用链式存储结构


因为对于链表来说,插入或删除数据只需要创建一个结点、输入数据、修改指针把该结点连接到链表中的某一位置即可; 而对于顺序表,插入一个数据可能需要搬移其他数据,复杂度高。


4、 链表分类 和 常用的结构


各种链表的结构:

虽然组合起来一共有8种链表可以选择,但是实际中最常用的主要还是 无头单向非循环 链表和 带头双向循环 链表。


1、无头单向非循环链表:俗称 “单链表”。结构简单,一般不会单独用来存储数据。实际上更多是作为其他数据结构的子结构(如哈希桶、图的邻接表、栈的链式结构等)


2、带头双向循环链表:结构最复杂,一般用来单独存储数据。实际使用的链表,大多都是带头双向循环链表。虽然结构最复杂,但是这种结构会带来很多优势。


5、 与顺序表的比较


链表: 链表是通过结点把离散的数据链接成一个表,通过对结点的插入、删除操作从而实现对数据的存取。


顺序表: 顺序表是通过开辟一段连续的内存(直接使用 数组 或者 malloc后realloc扩容)来存储数据。


但是由于 realloc 扩容分为原地扩容和异地扩容,前者代价较低,而后者扩容时不仅需要拷贝数据,还要释放旧空间。再者,扩容时一般会扩到原来容量的2倍,扩容次数多了就容易造成空间的浪费


顺序表的每个成员对应链表的结点;成员和结点的数据类型可以是标准的c类型或者是用户自定义的结构体类型。


比较对象

顺序表

链表

存储空间

连续

不连续

插入或删除数据

可能要搬移数据,复杂度O(n)

只需修改指针

push

动态顺序表:空间不够了需要扩容

没有“容量”的概念,push时直接malloc新的结点

应用

需要频繁访问

需要频繁插入、删除数据

相关文章
|
6天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
28 5
|
26天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
63 16
|
29天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
55 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
29天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
42 0
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
24 0
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
6月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
58 2