数据结构中链表及常见操作.docx
版权申诉
15 浏览量
2023-04-01
19:23:07
上传
评论
收藏 95KB DOCX 举报
链表
1 定义
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺
序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度，比另一种线性表顺
序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应
的时间复杂度分别是 O(logn)和 O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用
计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链
表由于增加了结点的指针域，空间开销比较大。
在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链
表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向
明上一个或下一个节点的位置的链接（"links"）。
链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆
体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据
类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任
意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以
及循环链表。
2 结构
2.1 单向链表
链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接
指向列表中的下一个节点，而最后一个节点则指向一个空值。
一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二
个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存
一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同
时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问
下一个节点，一直访问到需要的位置。
2.2 双向链表
每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指
向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指
向空值或者空列表）
双向链表可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个
链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。
2.3 循环链表
在一个循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可
实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始
的节点。指向整个列表的指针可以被称作访问指针。
剩余10页未读，继续阅读
资源评论
