数据结构重学日记（七）线性表的链式存储

概念

线性表的链式存储是指通过一组任意的存储单元来存储线性表中的元素，为了建立起数据元素之间的线性关系，对每个链表结点，除了存放数据元素自身的信息之外，还需要存放一个指向其后继的信息。这两部分信息组成数据元素 的存储映像，成为结点。

结点中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链。

链式存储
n 个结点（ 线性链表示例

头指针和头结点

有时候为了操作方便和统一，会给链表增加一个不存放数据的头结点，就像给项链加了一个扣，可以更方便的佩戴和摘取。

头指针始终指向链表的第一个结点。

头结点是带有头结点的链表中的第一个结点。数据域可以不存储任何信息，指针域存放链表中第一个元素的结点存放位置。

头结点的作用：

• 当链表为空时，头结点的头指针指向头结点，没有头结点的链表头指针会是 null。

• 无论链表是否为空，头指针始终指向头结点，因此空表和非空表的操作可以统一，方便了链表的操作，也减少了程序的复杂性和出现 bug 的机会。

• 方便链表的特殊操作，比如插入在表头或删除第一个结点。

在顺序表中，想找到第 i 个元素，可以通过 L->data[i] 找到，称为 随机存取方式。而在单链表中，想找到第 i 个元素就必须从头开始，按照顺序一直数到第 i 个元素，称为顺序存取方式。

链式存储的实现：

typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode * next;
}LNode, * LinkList;