前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

线性表的链式存储结构

顺序存储结构不足的解决办法

前面讲的线性表的顺序存储结构。它是有缺点的，最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。能不能想办法解决呢?

为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系，他们在内存中也是挨着的，中级没有空袭，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。

干脆所有元素都不要考虑相邻位置了，哪里有空位就到哪里，而只是让每个元素知道它下一个元素的位置，这样就可以在第一个元素时，就知道第二个元素的位置（内存地址），在第二个元素时，再找到第三个的位置（内存地址）

线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置

以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中,除了要存数据元素信息外，还要存储它的后继元素的存储地址。

数据域和指针域

因此，为了表示每个数据元素ai 与其直接后继数据元素ai+1 之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。

书上说的太好了，看书真的比看视频更有收获！！！

同学们，快去看书吧！

n个结点(a的存储映像)链结成一个链表,即为线性表(a1, a2, an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起

头指针

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里?最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”(通常用NULL或“^”符号表示)。

有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。 头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针

头指针与头结点的异同

异同点如下：

线性表链式存储结构代码描述

/*线性表的单链表存储结构*/
 typedef struct Node
 {
 ElemType data;
 struct Node *next;
 } Node;
 typedef struct Node *LinkList; /*定义 LinkList*/

从这个结构定义中,我们也就知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next 的值是一个指针。p->next指向谁呢?当然是指向第i+1个元素，即指向ai+1 的指针也就是说，如果p->data=ai,那么p->next->data=ai+1

上面这段话需要反复咀嚼！！！甚至自己可以拿笔画一下，多画几次就记住了~

p指针一个结点，相当于干了两件事

分别是指向了结点的数据域与和指针域

指向数据域是p->data

指向指针域是指针域里本来有个指针，p呢，它又指向这个指针，这个指针呢有指向下一个结点的data所以就有了上面这个图

以此类推