03-a-1：从静态到动态2:50

03-A-1：从静态到动态2:50

03-A-2：从向量到列表2:36

03-A-3：从秩到位置3:44

欢迎回来 第三章的主题是列表 与向量一样 列表也是典型的最基本的一类 所谓的线性结构 但是正如我们马上要看到的 列表结构与向量结构 在几乎所有的方面都是对称的、互补的 因此它的特点也十分的鲜明 不同数据结构所提供的操作接口 形形**不尽相同 但是总体而言 无非分为静态和动态的两种 前者是所谓的读取式 也就是说 只是获取数据项的内容 而不对它进行修改 比如说 典型的像向量的get和search操作 而后一种呢 是所谓的写入式的操作 也就是说 确实会对数据结构的局部 乃至整体进行修改 比较典型的是 向量的insert和remove操作 相应地 那数据元素在数据结构中的 存储与组织方式呢 也可以分为静态的和动态的两种 前者是以向量为代表的 具体来说 在这个数据结构的生命期内 数据区是在创建之初统一确定的 因此其中元素在逻辑上的次序 可以与它们在物理上存储的次序 直接联系起来 存在一一对应的关系 根据秩 能直接访问到这个元素 因此在静态操作方面 这类数据结构体现出效率上的很大的优势 比如说 get只需要O(1)的时间 如果按有序排列的话 search只需要logn的时间 但是反过来 这类结构在动态操作方面 却显得力不从心 回顾一下 无论是insert还是remove 都需要将当前这个元素的后继 向后移动一格 腾出一个空位 或者反过来 有的时候需要向前递补 填补一个空位 而最坏情况乃至平均情况下 我们都需要O(n)的时间 为了改变在动态操作方面的不足 我们应该相应地改用动态的存储方式 也就是说 各个元素所占的物理空间 是在生命期内动态地、逐步地分配 这里的代表就是我们这一章的主题：列表