当前位置：首页 > 正文

数组和顺序链表的区别

作者：晨曦发布时间：2022-05-21浏览：474

数组和顺序链表的区别

1、数组的内存需要提前确定，一旦确定不能更改其大小；而链表会动态分配内存；

2、数组的内存空间在内存中是连续的；而链表的内存空间则不是连续的；

　　3、数组的元素在栈区分配空间（即数组存储的元素都是为基本数据类型）；而链表在堆区分配空间（即链表中存储的元素为对象）

4、数组查询元素利用下标定位，时间复杂度为O（1）；而链表定位元素的时间复杂度则为O（ｎ）；

　　5、数组插入或删除元素的时间复杂度为O（ｎ）；而链表插入和删除的时间复杂度为O（1）；

　　数组

　　数组的存储方式是将元素在内存中连续存放，由于每个元素占用内存相同，所以可以通过下标迅速访问数组中的任何元素。但是如果要在数组中增加一个元素则需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想要删除一个元素，同样需要移动大量元素去填充掉被删除的元素。所以说数组查询元素速度较快，而增删元素速度较慢。

　　链表

　　链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起的。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果需要访问链表中的一个元素，则需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表结构就非常简单了，只要修改元素中的指针就可以了。所以说链表查询元素速度较慢，而增删元素速度较快。

声明：部分资源转载自互联网，转载目的在于传递更多知识，并不代表本网赞同其观点和对其真实性负责。如有侵权或者知识有谬误之处，麻烦通知删除，谢谢！联系方式: zzsla2022#163.com

数组和顺序链表的区别

相关推荐

Copyright zzsla.top Rights Reserved.

京公网安备11011502037736