顺序表和链表的比较

  1. 存取方式
    顺序表：可以顺序存取，也可以随机存取
    链表：只能从表头顺序存取元素
  2. 逻辑结构和物理结构
    采用顺序存储：逻辑上相邻的元素，其对应的物理存储位置也相邻。
    采用链式存储：逻辑上相邻的元素，其物理存储位置则不一定相邻；其对应的逻辑关系是通过指针链接来表示的。
  3. 查找、插入和删除操作
    对于按值查找：当顺序表在无序的情况下，两者的时间复杂度都
    是O(n)；当顺序表在有序的情况下，采用折半查找，其时间复杂度为O(lon2n)。
    对于按序号查找：顺序表支持随机访问，时间复杂度为O(1)；而链表的时间复杂度为O(n)。
    对于插入、删除：顺序表的插入、删除操作，平均需要移动半个表长的元素；链表的插入、删除操作，只需要修改相关结点的指针域即可。由于链表的每个结点有指针域，，因而在存储空间上比顺序存储要付出较大的代价，存储密度不够大。
  4. 空间分配
    静态顺序存储：一旦存储空间装满就不能扩充，如果再加入新元素，将出现内存溢出，需要预先分配足够大的存储空间。预先分配过大，还会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
    动态顺序存储：虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间将导致分配失败。
    链式存储结构：空间只在需要的时候申请分配，只要内存有空间有可以分配，操作灵活，高效。
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容