03 链表的线性表（链表和线性链表）

总结：初级双向循环链表结构最为复杂，通常用于多带存储数据。 实际使用的链表数据结构是一个包含所有标题的双向循环链表。

饿了就吃吧~打嗝———路飞

1.本章重点介绍链表（单链表+双向链表）的表示和实现。猜测。 OJ 有关链接列表的常见问题。 序列表和链表的区别。 2、为什么需要链表

简介：关于序列表的问题和思路

（一）动态序列表

特点：

数据不够要插入的空间。 ，应该扩大。 数据必须按顺序存储。

缺点：

如果空间不够，请增加容量。 扩展容量会牺牲一些性能，并且需要申请新空间、复制数据和释放旧空间。 消费也会增加。 如果增加容量，则扩展的容量可能会被浪费。 （容量增加是正常容量增加的两倍。）在开头或中间向左或向右插入数据时，必须按顺序移动，导致插入效率较差。 (O(N))

(2) 解决方案：

根据需要保留空间（每个保留一个）。 不需要物理空间连续性、前导和中间插入或数据移动。

这就引出了一种新的物理存储结构————>链表

3.链表概念和结构

概念：链表是一种物理的、不连续的、非顺序的存储。 存储结构 结构是数据元素的逻辑排序，通过链表中指针的链接排序来实现。

逻辑结构如图（假想）：（以单链表为例）

如图所示的物理结构（内存中的结构）：（以单链表为例）

你要做什么实际上需要实现的链表的结构可以有很大的不同。 结合以下情况，链表结构有八种。

单向、双向、循环无前导、非循环

链表结构数量巨大，但最实用的就是它们常用的结构有两种。

1. 无头单向非循环链表：

结构简单且典型，不使用多个条带来存储数据。 在实践中，它们经常用作其他数据结构的子结构，例如哈希桶或图邻接列表。 此外，这种结构经常出现在书面采访中。

2. 有头双向循环链表：

该结构最复杂，通常用于存储多带数据。 实际使用的链表数据结构是一个包含所有标题的双向循环链表。 另外，虽然这个结构很复杂，但是当你用代码实现它时，你会发现这个结构提供了很多好处，而且很容易实现。 稍后你在实现代码时就会发现。

4、实现单向链表

注意：

plist/phead——>头指针（通常不变）

cur——>当前位置（当前缩写）

查找tail的注意事项：

比较

//错误码//原来的tail查找（然后tail） SLTNode* tail = phead; while (tail != NULL){tail = tail->next;} //正确代码 //找到原来的tail（然后插入tail ） SLTNode* tail = phead;while (tail->next != NULL) {tail = tail->next;}

说明：

代码的第一部分是错误的。

<