数据结构作业-顺序表和链表的对比

顺序表和链表的对比

    顺序表和链表都属于线性表，这两种存储结构各有优缺点。

    顺序储存结构的特点是逻辑上关系相邻的两个元素在物理位置上也相邻，可以按元素序号随机存取表中的任一元素，时间复杂度为O(1)，它的存储位置可以用直观的公式表示。但在顺序表中做插入或删除操作时，需要移动大量元素，时间复杂度为O(n)，降低了执行效率。

    而链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，没有顺序存储的缺点，故在链表中做插入或删除操作时，不需要移动数据，只修改指针，不会影响前面和后面的节点，时间复杂度为O(1)，因此对n较大的链表效率高。但也失去了可随机存取的优点，时间复杂度O(n)。

    在存储空间分配上，顺序表的存储空间必须预先分配，元素个数扩充受限，易造成存储空间浪费或空间溢出现象；而链表无需预先分配空间，内存空间允许时，元素个数不受限制。在存储密度上，不考虑顺序表中的空闲区，顺序表存储密度为1；而链表存储密度小于1，单链表存储密度为0.5。

    综上，从空间性能上，当线性表长度变化不大，能事先确定存储大小，用顺序表；当线性表长度变化大，难以预估存储规模，用链表。在时间效率上，频繁查找，很少插入或删除，用顺序表；很少查找，频繁插入或删除，用链表。