线性表总结 顺序表、链表对比

前几篇我们已经学习了顺序表、单链表、双链表等再次回顾一下。1. 线性表概念线性表是具有相同数据类型的 n (n0) 个数据元素的有限序列。特点表中元素个数有限表中元素具有逻辑上的顺序性表中元素有其先后顺序表中元素都是数据元素每个元素都是单个元素表中元素的数据类型相同这意味着每个元素占有相同大小的存储空间表中元素具有抽象性即仅讨论元素间的逻辑关系而不考虑元素究竟表示什么内容。基本操作包括初始化、求表长、插入、删除等等。2. 线性表分类注意线性表是从逻辑结构上考虑的侧重的是元素之间的逻辑关系它有两种存储方式顺序存储的叫顺序表链式存储的有单链表、双链表、循环链表等顺序表和链表都是线性表。像树、图这种不是线性表。3. 顺序表、链表比较3.1. 读写方式顺序表可以顺序存取也可以随机存取链表只能从表头顺序存取元素。补充双链表里提到过可以维护一个尾指针实际上也可以从表尾开始找如果有指向前驱结点的指针的话可以倒着找前面的但无论从哪里开始无论是从前往后还是从后往前这里的“只能顺序存取”强调的是必须一个一个地找不能一下子就找到指定的地方。希望读到这里的初学者能真正理解所以有点啰嗦。3.2. 逻辑结构和物理结构的关系顺序表中逻辑上相邻的元素物理存储位置也相邻链表中逻辑上相邻的元素物理存储位置不一定相邻。3.3. 查找操作时间复杂度按值查找顺序表无序时时间复杂度为有序时可以用折半查找时间复杂度是到后面查找算法的地方会再详细学到可以先不用深究链表的时间复杂度为。按位查找顺序表可以随机访问因此时间复杂度是链表的平均时间复杂度是。3.4. 空间分配顺序表在静态存储分配的情况下一旦存储空间装满就不能扩充再加入新元素会出现内存溢出因此需要预先分配足够大的空间但过大可能会导致顺序表后部大量闲置。链表的结点空间只在需要时申请分配且不需要连续操作灵活高效。4. 如何选取存储结构顺序表和链表怎么选择4.1. 从存储方面考虑顺序表存储密度大但需要预先估计存储规模链表不需要预先考虑存储规模但因为要存储指针所以存储密度低。4.2. 从时间复杂度考虑顺序表按位查找时时间复杂度仅为链表是若常用操作是按位查找则应该选择顺序表。顺序表在进行插入、删除操作时平均需要挪动一半的元素而链表只需要修改指针链表进行插入、删除操作也需要先找到插入位置但只看插入、删除这个操作的话链表更方便。总之比较稳定的线性表可以顺序存储但如果频繁插入、删除的可以选择链表。