基础数据结构之一链表介绍
2011-06-06
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。
在计算机科学中,链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向明上一个/或下一个节点的位置的链接("links")。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。
链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C/C++和Java依靠易变工具来生成链表。
单向链表
链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。
一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接
一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
链表最基本的结构是在每个节点保存数据和到下一个节点的地址,在最后一个节点保存一个特殊的结束标记,另外在一个固定的位置保存指向第一个节点的指针,有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来,然后直接访问。当然如果只是访问数据就没必要了,不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个(需要储存反向的指针,见下面的双向链表)节点。
相对于下面的双线链表,这种普通的,每个节点只有一个指针的链表也叫单向链表,或者单链表,通常用在每次都只会按顺序遍历这个链表的时候(例如图的邻接表,通常都是按固定顺序访问的)。
双向链表
一种更复杂的链表是"双向链表"或"双面链表"。每个节点有两个连接:一个指向前一个节点,(当此"连接"为第一个"连接"时,指向空值或者空列表);而另一个指向下一个节点,(当此"连接"为最后一个"连接"时,指向空值或者空列表)
一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接
在一些低级语言中, XOR-linking 提供一种在双向链表中通过用一个词来表示两个链接(前后),我们通常不提倡这种做法。
双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针,还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点,当然也可以访问后一个节点,以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。
由于另外储存了指向链表内容的指针,并且可能会修改相邻的节点,有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点,形成一个下面说的循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表,对于把链表单独的存在数组里的情况,也可以直接用这个数组表示链表并用第0个或者第-1个(如果编译器支持)节点固定的表示这个虚拟节点。
循环链表
在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表,你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法,循环链表可以被视为"无头无尾"。这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。
指向整个列表的的指针可以被称作存取指针。
用单向链表构建的循环链表
循环链表中第一个节点之前就是最后一个节点,反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理,区别不大(详见下面实例代码)。当然,如果只会在最后插入数据(或者只会在之前),处理也是很容易的。
另外有一种模拟的循环链表,就是在访问到最后一个节点之后的时候,手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能,在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。
其它
链表中的节点不需要以特定的方式存储,但是集中存储也是可以的,主要分下面这几种具体的存储方法:
共用存储空间:链表的节点和其它的数据共用存储空间,优点是可以存储无限多的内容(不过要处理器支持这个大小,并且存储空间足够的情况下),不需要提前分配内存;缺点是由于内容分散,有时候可能不方便调试。
独立存储空间:一个链表或者多个链表使用独立的存储空间,一般用数组或者类似结构实现,优点是可以自动获得一个附加数据:唯一的编号,并且方便调试;缺点是不能动态的分配内存。当然,另外的在上面加一层块状链表用来分配内存也是可以的,这样就解决了这个问题。这种方法有时候被叫做数组模拟链表,但是事实上只是用表示在数组中的位置的下标索引代替了指向内存地址的指针,这种下标索引其实也是逻辑上的指针,整个结构还是链表,并不算是被模拟的(但是可以说成是用数组实现的链表)。
链表用来构建许多其它数据结构,如堆栈,行列和他们的衍生。
节点的数据域也可以成为另一个链表。通过这种手段,我们可以用列表来构建许多链性数据结构;这个实例产生于Lisp编程语言,在Lisp中链表是初级数据结构,并且现在成为了常见的基础编程模式。 有时候,链表用来生成联合数组,在这种情况下我们称之为联合数列。这种情况下用链表会优于其它数据结构,如自平对分查找树(self-balancing binary search trees)甚至是一些小的数据集合。不管怎样,一些时候一个链表在这样一个树中建立一个节点子集,并且以此来更有效率地转换这个集合。
相关推荐
数据结构上机实验之一,比较基础的实验,先构建单链表,再将单链表转化为循环链表。
数据结构系列前言: 数据结构作为程序员的基本知识,需要...进入正题,关于链表的数据结构知识,这里简单介绍下: 链表是一种物理存储单元上非线性、非连续性的数据结构(它在数据逻辑上是线性的),它的每个节点由两
链表是一种常见的数据结构,也属于线性表,但不会按线性的顺序来储存数据。而是在每一个节点中,储存了下一个节点的指针。可以看图理解。(有C语言基础的可能比较好理解)。 使用链表结构可以克服数组需要预先知道数据...
本资源是一份关于数据结构与算法中基础数据结构的备赛资料,主要包括数组、链表、栈、队列、树、图等常见数据结构的基本概念、操作和应用。通过本资料的学习,可以帮助读者深入理解数据结构的基础知识,掌握常见数据...
(1)数据结构与算法概念解析 (2)数据结构之数组 (3)数据结构之栈 (4)数据结构之队列 (5)数据结构之链表 (6)数据结构之二叉树 (7)数据结构之霍夫曼树 (8)数据结构之红黑树(一)——基础分析 ...
10-3 旋转图像-原理讲解 10-4 旋转图像-代码实操第11章 数据结构之“二叉树”二叉树是数据结构中难度最大的没有之一,如何实现一个二叉树结构并对它遍历难于上青天,学完这个章节会让你牢牢掌握二叉树的基础知识。...
软件设计师考试大纲对数据结构部分的要求是熟练掌握常用数据结构和常用算法,因此,本专题从数据结构的概述出发,对基本的概念引出常用的数据结构类型的介绍和讲解,同时在讲解各种数据结构中间采用算法与数据结构相...
算法:C语言实现 (第1-4部分)基础知识、数据结构、排序及搜索(原书第3版) 本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。...
他是我国计算机普及和高校计算机基础教育开拓者之一,现任全国高等院校计算机基础教育研究会会长、教育部全国计算机应用技术证书考试委员会主任委员。 谭浩强教授创造了3个世界纪录:(1)20年来他(及和他人合作)...
关于这本小册.md 1、回顾大学四年,后悔没有这样做.md 2、计算机基础到底是哪些基础.md 3、编程语言是个什么玩意儿.md ...23、数据结构中的绝代双骄(2)链表.md 24、数据结构中的栈和队列这回懂了.md ……
文章目录3 链表3.1 单向链表单链表的操作单链表是否为空、长度、遍历操作头部添加元素 add()尾部添加元素append()指定位置添加元素...链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是不像顺序表一样
3. 单链表——线性表的链式存储结构之一 10 4. 循环链表 15 5. 双向循环链表 15 6. 顺序表与单链表的比较 16 二、 习题 16 第3章 栈和队列 17 一、 基础知识和算法 17 1. 栈 17 2. 链栈 17 3. 顺序栈 18 4. 队列 19 ...
全国计算机二级JAVA笔试分类模拟题算法和数据结构、程序设计基础全文共21页,当前为第1页。全国计算机二级JAVA笔试分类模拟题算法和数据结构、程序设计基础全文共21页,当前为第1页。二级JAVA笔试分类模拟题算法和...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
本书是关于计算机科学与工程领域的基础性研究科目之一——数据结构与算法的专著。 本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之...
(55) 在设计程序时,应采纳的原则之一是(A) 注:和设计风格有关 A. 程序结构应有助于读者理解 B. 不限制goto语句的使用 C. 减少或取消注解行 D. 程序越短越好 (56) 下列不属于软件调试技术的是(B) 注:P98 A. 强行...
他是我国计算机普及和高校计算机基础教育开拓者之一,现任全国高等院校计算机基础教育研究会会长、教育部全国计算机应用技术证书考试委员会主任委员。 谭浩强教授创造了3个世界纪录:(1)20年来他(及和他人合作)...
31 习题9 排序------------------------------------------------------------------------------------34 第1部分 C++基本知识 各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学...