链表是一种数据结构, 其使用不受程序设计语言的限制, 多种程序设计语言, 如:C、C++、JAVA等, 均可实现链表 (以下涉及的程序以C语言为例) 。链表由离散的结点通过指针连接而成, 构成链表的结点实际上就是一个包含指针项并由数据域和指针域两大部分构成的结构体变量。链表的基本操作包括:链表的建立、结点的插入、结点的删除、查询具有某一数值的结点等。其中, 链表的建立是动态的, 初始建立时往往是空的, 除头结点外, 不包含其它任何结点。因此, 链表的动态建立过程其实就是在程序执行过程中从无到有地建立一个链表的过程。这个过程是灵活的, 至于链表建立后的使用则完全基于用户的应用需求。
链表在计算机科学中的使用非常广泛, 数据结构中的堆栈、队列、串、树等结构及其算法以及操作系统中进程的排列等均可由链表来实现, 并且根据算法的需要, 还可选用单链表、双链表或循环链表等不同的链表结构。因此, 熟练掌握链表的使用有助于更好地学习和掌握计算机科学。
1 数据结构中链表的建立、插入和删除
线性表是n个类型相同的数据元素的有限序列, 数据元素之间是一对一的关系。为了能利用计算机对线性表进行处理, 就必须把线性表有效地存储到计算机的内存中。用链接方式存储的线性表是线性链表, 线性单链表是线性链表的一种。只有掌握好线性单链表的概念它后面的操作才会变得容易。要了解线性单链表的概念, 首先要知道线性表的链式存储结构、结点的概念, 进而得出什么是线性单链表知道了定义后要理解它的逻辑表示和存储表示。
线性单链表是拥有有序结点序列的数据结构, 其中, 每个结点包含一个数据元素以及一个指向序列中下一个结点的指针。即数据域和指针域。数据域用来存储结点的值;指针域用来存储数据元素的直接后继的地址 (或位置) 。链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。由于链表的每个结点只有一个指针域, 所以这种链表就称为单链表。
1.1 设计原理
如果链表的结点结构中只有一个指针域, 这样存储的链表就是单链表 (Single Linked List) , 一般在第一个结点之前附设一个结点, 称为头结点。头结点数据域可以不存储任何信息, 其他结点的数据域存储结点a1a2……an这样的数据元素。单链表的结点结构如下:
用尾插法建立单链表L的原理为:用头指针head指向头结点, 并设置一个尾指针r和head有相同的指向, 最终尾指针r指向终端结点。
1.2 单链表中的插入操作
单链表中的插入操作分为前插和后插, 后插操作相对简单, 前插要转化成后插才能完成。
(1) 后插运算实现单链表的插入。
在第3个位置的结点之后插入数据元素
在单链表中增加一个指向其前趋的指针域prior, 这就形成了双链表的结点结构。双链表一般是由头指针head唯一确定的, 因为增加头指针能使双链表上的某些运算变得方便, 不需要特殊处理。
2 链表在计算机科学中的应用实例
下面是一个链表的简单应用的实例, 在这个程序的运行过程中, 用户输入命令“E”或“e”, 即可录入新的学生记录;而输入命令“L”或“l”, 则输出所有学生记录。所有记录由一条链表来保存, 链表中的每个结点保存一条学生记录, 这里就涉及到链表的建立、结点的插入及查询等操作。当然, 要建立一个较为完整的学籍管理系统, 还需要加入记录的删除、记录的查询及修改等功能。
当然, 以上程序也可以选用其它存储结构来实现, 比如:数组。链表和数组一样, 都是一种存储结构, 但通过上例可以看出, 与数组相比, 链表的优点在于以下几点。
(1) 可以进行离散的空间分配, 不必占用大量连续的存储空间数组中所有的元素占用的是一片连续的存储空间, 当数组元素个数很多而每个元素所占空间又很大的时候, 内存中不一定能找到那么大的一片连续的存储空间供用户使用。例如:数组中有100个元素, 每个元素占200个字节, 此时, 如果使用数组, 则需要一片连续的近20K的存储空间, 这是困难的。但链表离散的空间分配则可以解决这个问题, 使用链表时, 只要能找到总和为20K的存储空间, 这个空间可以是连续的, 也可以是离散的, 只要每部分超过200字节即可, 这相对而言是容易的。 (2) 可以进行动态空间分配, 不必预估存储空间的大小, 数组在使用之前必须事先声明其元素个数, 而在大多数情况下, 我们事先并不知道需要多少个元素, 而且根据情况的不同, 元素个数也不是固定不变的。链表的动态空间分配可以弥补数组的这个不足, 它不需要实现声明结点个数, 而是可以根据实际情况, 随时增加或删除结点, 既不会造成空间的浪费, 也不会因存储空间不足而导致重新分配空间的麻烦。 (3) 可以用于复杂的数据结构, 如堆栈、队列及操作系统中进程的排列等基于上述两个优点, 链表可以更好的实现堆栈、队列、串等数据结构的描述。 (4) 可以避免大量的数据移动:当数据需要频繁的进行插入、删除操作时, 数组需要进行大量的数据移动操作以空出/填补插入/删除操作所需的空间。
摘要：本文基于笔者多年从事计算机科学与应用的相关研究经验, 以计算机科学中的一个重要方向数据结构为研究对象, 探讨了数据结构中链表的应用思路, 分析了链表的建立、插入和删除防范, 给出了具体的应用实例, 全文是笔者长期工作和学习实践基础上的理论升华, 相信对从事相关工作的同行有着重要的参考价值和借鉴意义。
关键词：计算机科学,数据结构,链表,实例