线性表的顺序存储结构与链式存储结构_线性表的存储结构顺序表和链表

1、线性表的概况

线性表的定义：零个或多个数据元素的有限序列

2、顺序存储结构:

三个重要属性：

      存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置

      线性表的最大存储容量：数组data的长度MAXSIZE（这里是20）

      线性表的当前长度：length

顺序存储结构的插入删除时间复杂度：

       最好情况：插入/删除最后一个元素，O(1)。

       最差情况：插入/删除第一个元素，O(n)

       平均时间复杂度：(n-1)/2---->最终复杂度O(n)

       最终结论：

          线性表的顺序存储结构中，在存读数据时，不管哪个位置，时间复杂度都是O(1)；插入删除，时间复杂度都是O(n)

3、线性表的链式存储结构:

 

单链表的时间复杂度

       单链表的读取：时间复杂度，当i=1，O(1)；当in，O(n)。

       单链表的插入删除：先找到i的位置O(n)，然后赋值移动指针O(1)。时间复杂度都是O(n)。

    大批量多次删除插入的时候，顺序存储结构，每次删除插入都是O(n)。链式存储结构第一次O(1)，剩下的为O(1)。这个时候就体现出，链式存储结构的优点。(插入删除操作越频繁，单链表的效率优势越大)。

4、单链表结构与顺序存储结构优缺点：

一些经验总结：

（1）频繁查找，很少插入删除用单链表。若需要频繁插入删除时，宜采用单链表结构。（比如游戏开发中的，用户信息顺序存储，武器装备信息链式存储）

（2）当线性表中元素个数较大，或者未知时，用单链表。

5、拓展链表

静态链表：用数组描述的链表叫做 静态链表(数组＋游标实现法)。---->没有指针/对象引用机制，basic等早期编程语言。

循环链表：将单链表中终端节点的指针端由空指针改为指向头结点，使整个单链行程一个环。

双向链表：是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。