数组与链表的区别

[问答题]

数组与链表的区别

肉嘟嘟的小丸子

（1）逻辑结构。数组必须实现定义固定的长度，不能适应数据动态的增减的情况，即在数组使用前，就必须确定数组的大小。当数据增加时，可能超出原定义的元素的个数，当数据减少时，造成内存浪费。数组中插入删除数据项时，需要移动其他数据项。而链表采用动态分配内存的形式实现，可以适应数据动态增减情况，需要时可以用new/malloc分配内存空间，不需要时用delete/free将已分配的空间释放，不会造成内存空间的浪费，且可以方便的插入，删除数据项。

（2）内存结构。（静态）数组从栈中分配内存空间，对于程序员方便快速，但是自由度小。链表从堆中分配空间，自由度大，但申请管理比较麻烦。

（3）数据中数组的内存是顺序存储的，而链表是随机存取的。数组随机访问效率很高，可以直接定位，但插入删除操作的效率比较低。链表在插入删除操作上相对数组有很高的效率，而如果访问链表中的某个元素，那就要从表头逐个遍历，直到找到所需要的元素为止，所以链表的随机访问效率比数组低。

（4）链表不存在越界问题，数组有越界问题。数组便于查询，链表便于插入删除。数组节省空间但是长度固定。链表虽然变长，但是占了更多的存储空间。

发表于 2017-04-07 17:06:57 回复(0)

cyanlong

顺序存储结构的特点是逻辑上相邻的数据元素，在物理内存的位置也相邻，并且，顺序表的存储空间需要预先分配。

其优点有:

1.不用为表示节点间的逻辑关系而增加额外的开销。

2.顺序表可按元素序号随机访问。

其缺点为: 在对顺序表做结构性修改，如删除(插入)时需要对删除点(插入点)之后的所有元素平移以保证顺序表内存上的连续性。

在链式存储结构中，使用指针(引用)实现元素之间的逻辑关系。并且，链式的存储空间是动态分配的。

其优点为：在对链式存储结构做结构性修改，如插入(删除)时，只需要改变对应位置的引用关系即可，无需对无关的元素做移位之类的操作。

其缺点为：链表不能随机存取元素。

编辑于 2017-01-10 10:50:05 回复(0)

WSW需要一个清醒的头脑

存储结构不同，数组对插入删除操作开销大，链表则对查找指定位置元素开销大

发表于 2017-01-10 08:36:27 回复(0)

提交观点

问题信息

数组链表

上传者：牛100

难度：

3条回答 11收藏 3829浏览

数组与链表的区别

问题信息

热门推荐

相关试题