算法

1.1 顺序存储结构和链式存储结构

优缺点

1. 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

    优点：存储密度大（＝1），存储空间利用率高
   
    缺点：插入或删除元素时不方便
   

2. 链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

    优点：插入或删除元素时很方便，使用灵活
   
    缺点：存储密度小（<1），存储空间利用率低
   

场景

1. 顺序表适宜于做查找这样的静态操作
2. 链表宜于做插入、删除这样的动态操作
3. 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表
4. 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表

顺序表与链表的比较

• 基于空间的比较

  • 存储分配的方式
    • 顺序表的存储空间是静态分配的
    • 链表的存储空间是动态分配的
  • 存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量
    • 顺序表的存储密度 = 1
    • 链表的存储密度 < 1

• 基于时间的比较

  • 存取方式
    • 顺序表可以随机存取，也可以顺序存取
    • 链表是顺序存取的
  • 插入/删除时移动元素个数
    • 顺序表平均需要移动近一半元素
    • 链表不需要移动元素，只需要修改指针