一、线性表的概念

二、线性表常见的两种存储结构

1、顺序存储结构

2、链式存储结构

三、顺序存储结构

1、概念

• 各个元素存储的地址空间连续，逻辑相邻的元素在物理内存中也相邻，如数组；

2、优点

• 因为各个元素是连续储存，而且当元素类型一致时占用空间大小一致，所以可以直接通过首元素地址计算某个元素的内存地址，从而访问特定元素效率很高。
  • 

3、缺点

• 由于顺序存储的特点，所以在删除或插入元素后需要移动其它元素使得整体的存储空间依然是连续的， 所以删除、插入元素效率低。
• 由于元素存储空间连续，所以当有大数据时，较难分配一块连续的大内存空间。

4、顺序结构存储形式

四、链式存储结构

1、概念

• 各个元素存储在任意的地址空间，逻辑相邻的元素在物理内存中没有联系，如链表。

2、优点

• 由于链式存储的特点，删除或插入节点很方便，不需要移动其它元素，改变元素“连接”关系即可。

3、缺点

• 因为存储的任意性，只能通过前一个元素访问下一个元素，每一次访问元素都从头节点开始遍历， 所以访问特定元素或查找元素效率低。

4、链式结构存储形式

• 单链表
• 循环链表
• 双向链表

五、链式存储注意项

1、查询数

• 根据链找到对应的位置读取数，所以会更快一些。

2、查询数的位置

• 先读取链中的第一个数，与本身进行比较，如果合适就返回第一个数的位置，不一致就接着往下找。此时效率会低一些。

3、插入

• 需要把要原本的块链接先断掉，然后指向插入的块，然后插入的块再指向后面的块，因为有链式结构的改变，所以效率会慢一些。

4、删除

• 需要先将原本块链接先断掉，然后把剩下的块再链接起来，所以效率也会受影响。