线性表的链式存储结构（十）

        我们之前学习了顺序存储结构线性表，虽然它很强大。但是存在一个不算是缺点的缺点：那便是在插入和删除时。需要移动大量的元素。那么该如何解决这个问题呢？我们直接会想到的是在数据元素之间空出位置，那么在后面的插入时便会很方便。那么此时便会出现一个问题：究竟留出多少空间合适呢？有一个极端是我们需要插入的是 n 个元素。换而言之，这个空间需要预留无穷大，那么这个肯定是不现实的。

        此时便出现了我们本节要讲的内容：链式存储。我们来看看链式存储的定义：为了表示每个数据元素与直接后继元素之间的逻辑关系；数据元素除了存储本身的信息外，还需要存储直接后继的信息。如下

        我们来看看链式存储逻辑结构，它是基于链式存储结构的线性表，每个结点都包含数据域和指针域。数据域是指粗出数据元素本身；而指针域是指存储相邻结点的地址。关系如下所示

        顺序表指的是基于顺序存储结构的线性表，链表指的是基于链式存储机构的线性表。链表分为三种：a> 单链表，即没和结点只包含直接后继的地址信息；b> 循环链表，即单链表中的最后一个结点的直接后继为第一个结点；c> 双向链表，即单链表中的结点包含治脚气前驱和后继的地址信息。

        下来我们来看看链表中的基本概念：A、头结点。链表中的辅助结点，包含指向第一个数据元素的指针；B、数据结点。链表中代表数据元素的结点，表现形式为：（数据元素，地址）；C、尾结点。链表中的最后一个数据结点，包含的地址信息为空。那么单链表中的结点是怎样进行定义的呢？如下

        我们来看看单链表中的内部结构，如下

        头结点在单链表中的意义是：辅助数据元素的定位，方便插入和删除操作；因此，头结点不存在存储实际的实际数据元素。那么在目标位置处是如何插入数据元素呢？1、从头结点开始，通过 current 指针定位到目标位置；2、从堆空间申请新的 Node 结点；3、执行操作：node->value = e; node->next = current->next; current->next = node; 同理，在目标位置处删除数据元素：1、从头结点开始，通过 current 指针定位到目标位置；2、使用 toDel 指针指向需要删除的结点；3、执行操作：toDel = current->next; current->next = toDel->next; delete toDel;

        通过今天对线性表的链式存储结构的学习，总结如下：1、链表中的数据元素在物理内存中午相邻关系；2、链表中的结点都包含数据域和指针域；3、头结点用于辅助数据元素的定位，方便插入和删除操作；4、插入和删除操作需要保证链表的完整性。

        今天七夕情人节，祝大家七夕快乐！