1、线性表的概念

  • 线性表Linear List是由n(n≥0)个类型相同的数据元素组成的有序序列
  • 线性表的特点
    • 同一性：同一类型
    • 有穷性
    • 有序性

2、线性表的顺序储存

  • 顺序表：采用顺序储存结构的线性表通常称为顺序表
  • 用一组地址连续的存储单元依次在储存线性表的各个元素，使得线性表中的在逻辑结构上相邻的数据元素储存在相邻的物理储存单元中
  • 优缺点
    • 优点
      • 操作方法简单，容易实现
      • 无须为表示结点间的逻辑关系而增加额外的储存开销
      • 存储密度高
      • 顺序表可按元素位序随机存取结点
    • 缺点
      • 插入、删除运算不方便，需要移动大量结点，效率低
      • 存储分配只能预先静态分配，当表长变化较大时，难以确定合适的储存规模

3、线性表的链式储存

  • 采用链式储存结构的线性表称为链表
  • 按照实现角度分类
    • 静态链表
    • 动态链表
  • 链接方式
    • 单链表
    • 双向链表
    • 循环链表