存取方式
顺序表：可以实现顺序存取和随机存取
单链表：只能实现顺序存取
逻辑结构和物理结构
顺序表：逻辑相邻物理上也相邻，通过数组表示逻辑关系
单链表：逻辑相邻物理上不一定相邻，通过指针表示逻辑关系
基本操作
插入和删除
顺序表：需要移动大量数据项，效率低
单链表：通过修改指针来操作，结点指针已知时，时间复杂度为O(1)
按值查找
顺序表：需要遍历直到找到，时间复杂度为O(n)
单链表：需要遍历直到找到，时间复杂度为O(n)
按序查找
顺序表：可直接访问，效率高，O(1)
单链表：仍需遍历直到找到，O(n)
内存空间
顺序表：顺序存储。静态分配和动态分配都需要预先分配合适的内存空间。静态分配时预先分配空间太大会造成浪费，太小又会造成数据溢出。动态分配时虽然不会溢出但是扩充需要大量移动数据项，操作效率低
单链表：链式存储。在需要插入结点时分配空间即可，高效方便
本文链接：https://shengto.top/data_structure/152.html
转载时须注明出处及本声明