线性表(知识笔记)

什么是线性表

线性表描述的是数据的逻辑结构。其描述的逻辑为：
数据是线性的，一对一的，头结点无前驱，可以有且只能有一个后继，尾结点有且只有一个前驱，无后继，其余结点有且只有一个前驱和后继。就类似于一条队伍。
存储结构：顺序存储和链式存储(这篇说的都是单链表)。
顺序存储类似于自习室占座位，预先开辟一块内存，是与逻辑结构一一对应的存储数据；
链式存储，数据位置不固定，每个结点存储值和下一个结点的指针。

线性表的适用性

适用于数据逻辑为一一对应关系的数据，比如浏览器的历史记录，可以实现前进后退，就是线性表的实现。

线性表的优缺点

这里按照存储结构分别表述。
顺序存储：由于存储的是一块连续的内存，相当于内存地址都是已知的（可以简单的计算得出），查询的复杂度为O(1)，但是不利于增删（每增删一，其后的数据内存地址都要更改），增删的复杂度为O(n)。
而且需要预先分配空间，数据量经常改变很不方便。
链式存储：由于存储的内存地址不确定，只能由头结点一个个去遍历，所以查询的时间复杂度为O(n)。增删如果只增删一个，和顺序存储无区别，但是如果要增删的数量变为十二十一百。链式存储的优势便体现出来。而且不需要分配存储空间，更灵活。