顺序表的结构和实现

    结构
    表头信息：容量，元素个数
    数据区：元素集合

    两种实现方式
    一体式结构：表头和数据连续
    分离式结构：表对象存放表头信息+数据区的地址信息，数据存放在另一块空间

    两种扩容方式
    线性增长：每次申请固定数据空间
    指数增长：每次翻倍，以空间换时间

    增加元素
    表尾增加：O(1) append
    非保序插入：不常见，不关注
    保序插入: O(n) insert

    删除元素
    删除表尾: O(1) pop()
    非保序删除：不常见，不关注
    保序删除: O(n) pop(i)

    Python中的顺序表
    list和tuple
    list是一个元素个数可变的线性表（动态顺序表），采用分离式结构
    image.png

    image.png

    链表
    image.png
    image.png
    头结点（首节点）：p

    链表的实现

    image.png