线性表

数据结构的一种排列、组织方式，它是线性的

分类

大纲我们有一个图，可以回顾一下。

根据元素存储结构来划分的，顺序存储结构和链式存储结构。

1. 顺序表

2. 链表

存储空间虽然是离散的，一块一块的，但是通过逻辑上的一个指针的联系，在逻辑上实现一个整体。

3 链表的类别（主要来看链表）

单链表

单链表最后一个节点 为null

循环链表

最后一个为指针

双链表

最后一个有两个指针，可以形成两条链，叫做双链表。

双链表 灵活性，会大于其他。

4 链表的操作

单链表的删除

我要删除 a2

方法：
把 a1 的 next（指针）域 直接指向 a3，跳过 a2，那就可以了，等于a2已经被删除了。
再去，释放 节点a2，free a2，就完成了。

简单说就是，把前驱节点 a1 指向 后驱节点 a3。

单链表的节点插入

把 新的节点，从要插入的位置。
把 前驱节点 要插入的 next域 指向 新加入节点，再把 新加入节点的 next域 指向 下一个节点就可以了。

但是实际上的操作，我们不能直接替换，
a2本来指针可表示为 p->next，如果我们让 p->next 直接指向 如图的 s，则他会发生变化，发生变化后，就无法把后面一截连起来了。

那么如何操作呢？

1. 我们定义一个 s节点
2. 把s 指向 p节点的 下一个节点， p->next
3. 把 s->next 赋值为 p->next

双链表的节点删除

双链表的节点插入

此图，从左往右看，1 2 3 4步骤。 先完成，1 2，再完成 3 4

1. 新节点的 前驱 指向 a1 后驱 指向 a2
2. 接下来，再完成第二步赋值即可。

5. 顺序表与链表的比较

1. 何为存储密度？
   固定的（比如说内存）区域，存储的元素越多，密度越高。2K空间，一个存了200个数据，一个存了2000个数据。则2000个数据的，密度高。

2. 为什么 顺序存储好？
   因为就一个空间，而链式存储还需要1.5个空间，因为还要存指针。

3. 容量分配

链式存储可以随时增减空间。 顺序存储必须 事先确定

4. 时间性能

5. 插入删除运算

对于链表来说：
我们只是一个节点的操作指向， 操作起来就是一个常量，所以他们时间复杂度为 O(1)
对于顺序存储来说：
你删除或者添加一个，都需要把后面的，位置也移动一遍。 虽然看起来非常容易，但是时间消耗在移动操作上。
所以明显 插入删除运算 链式存储 优于 顺序存储

6. 查找运算
   相同，因为他们都是 从第一个 往第二，三个查找。

特殊情况，顺序存储，123456 从小到大，我们可以使用 二分法查找，就会顺序结构比链式存储快。

7. 读运算

顺序存储， 依次存储，他的偏移量 是可以 直接计算出来的。比如第一个为 000，第八个是多少？直接加上偏移量7即可，那就是007/ （从 0开始计算。） 这种存储方式称为随机存储，想存储哪一个元素 就是存储哪一个元素。

而链表就无法这样做。

必须一个一个 next，一直查找查找。

6. 栈 -先进后出

栈，不是一个实实在在存在的东西，是逻辑上概念，一种思想，一种概念。
并不像 顺序存储，链式存储那样，一种一种很有规律的。

栈是在其之上的一种逻辑单元。

我们只要给 栈 定义一个规则 先进后出就可以了

比如： 你往箱子里 塞 如 笔记本， 毛巾， 散热器， 鼠标垫。

那么你拿出来，就得是 鼠标垫，散热器，毛巾，笔记本。

这就是 先进后出。

那我们栈，能不能 1 2 3 4 进去，然后 1 2 3 4出来呢？

可以，如果你的栈是不是如上图，那就行。

7. 队列（先进先出）

排队挂号，能理解吧。。。

顺序结构队列

特殊队列（循环队列）

队列指针，转转转，转一圈，又回到了，原点。（爱的魔力转圈圈。。。。）

如图，如果队列没有记录任何元素的时候，头指针，尾指针都指向同一个 元素 . 且元素当中的值是空的。
记录一个元素之后，比如我在 0 存入一个 X， 则 队头指针不变，队尾指针会 后移一位，再存入，又后移一位。以此类推。

判断循环队列 是满还是空状态？

问题，当我在最后一个地方，存入一个 Z 的时候，我的 tail 指针就又回来了（因为是循环队列）。

以前 如果 head = tail 我们就是 空情况， 而现在 又回来了，是 队列满的情况，也相等。

也就是说我们发现了，我们不知道 如何判断 循环 队列 是空还是满队列。

解决办法： 牺牲一个空间，这个空间 我们不用来存放数据/

就是 当 tail 指针，为指向这个空间时候。就满了。

如何判断，就是 tail + 1 = head 则循环队列满了。

感谢关注

上海PHP自学中心-免费编程视频教学|Python教学|Web开发教学|全栈开发教学|加密与解密|Linux教学|Golang教学|

]

@author wangchunbo