线性表之链式存储（一）

前言

上次我们说到顺序存储有着查找方便的便利，是因为它是随机存取的，但同样的，增删对于顺序表有着难以忍受的复杂度，因此我们引进了链表，它有着顺序表没有的优点。
如果我让你将两个数组内的所有元素按照从大到小的顺序排成一个大数组，你是否会选择创建一个大数组来承载这个任务。如果是，那你就该好好学习一下这一节的内容了。

一.链表的概念

1.链表：n个结点组成的长链。
2.
3.根据结点的不同又分为三种
（1）.单链表：结点只有一个指针域
（2）.双链表：结点有两个指针域，一个指向直接后继，一个指向直接前趋。
（3）.循环链表：首尾相连的链表为循环链表
4.头指针：指向第一个结点的指针
5.首元结点：是指存储链表中第一个元素a1的结点
6.如上所举例子，表长为n；n=0时为空表，此时，如果有头节点，头结点指针域为空，无头结点，头指针为空（即NULL）
6.头节点：首元结点之前的一个结点（它的数据域一般是不需要存储数据的，如果非要存储，可以存储上表长），头结点的好处我们会在下面提到。
它与顺序表的区别在于：
1.结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
2.访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描各点，所以寻找第一个结点和最后一个结点的所花费时间不等，即顺序存取法。

先写到这里，明天我们将利用今天我们所学的知识解决开篇提出的问题
，并介绍一系列对链表的操作，并在这些操作中，体现出头结点的优点。

前言

一.链表的概念

更多相关文章

随机推荐