顺序表和单链表的优缺点

顺序表和单链表的优缺点

#顺序表的优点：其存储结构为随机存取结构，逻辑关系可直接用数组元素下标表示。

#顺序表的缺点：①线性表的长度不确定，难以事先确定数组长度。②存储空间必须是连续的，易造成存储空间的“碎片”现象。③插入和删除操作需要移动大量元素。

#单链表的优点：①元素的存储单元是任意的，可连续也可不连续。②不需要限定长度。

#单链表的缺点：①其查找时间复杂度为O(n)。②存放元素时需要另外开辟一个指针域的空间。

分析下列情况下，采用何种存储结构更好些。

（1）若线性表的总长度基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素。

采用顺序存储结构，其插入和删除操作需要移动大量元素，但可按数组下标直接查找元素。

（2）如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。

采用链接存储结构，链表的长度不需要限制，可动态发生变化。

（3）描述一个城市的设计与规划。

采用链接存储结构，因为城市的设计与规划过程中的变化大，需要不断的插入和删除操作。