顺序表和链表的区别 不同点顺序表链表(带头双向循环)存储空间物理上一定连续逻辑上连续物理上不一定连续随机访问(用下标随机访问)支持:O(1)不支持:O(N)任意位置插入或者删除元素可能需要搬移元素,效率低O(N)只需修改指针指向插入动态顺序表,空间不够时需要扩容(扩容本身有消耗,空间浪费(通常每次扩大为原来的2倍))没有容量的概念(按需申请释放)应用场景元素高效存储+频繁访问任意位置插入或删除频繁缓存利用率高低(可能造成缓存污染) 从表中对比可以看出,二者是互补的 链表纵有万般好,但是也有明显的不足:不支持用下标随机访问 小的数据加载到寄存器,大的数据加载的和缓存