位置:首页  >   程序积累  > 数据结构之数组和链表

数据结构之数组和链表

====数组=====
1.在内存中,数组是一块连续的区域
2.数组需要预留空间,在使用前需要提前申请所占内存的大小
3.在数组起始位置处,插入数据和删除数据效率低
-插入数据时,待插入位置的元素和它后面的所有元素都需要向后搬移
-删除数据时,待删除位置后面的所有元素都要向前搬移
4.随机访问速度效率很高,时间复杂度可以到达O(1)
因为数组的内存是连续的,想要访问那个元素,直接从数组的首地址向后偏移就可以访问到了
5.数组开辟的空间,在不够使用的时候需要扩容,扩容的话,就会涉及需要把旧数组的所有数据向新数组中搬移
6.数组的空间是从栈分配的
====数组的优点====
随机访问性强,查找速度快,时间复杂度O(1)
====数组的缺点====
1.头插和头删的效率低,时间复杂度O(N)
2.空间利用率不高
3.内存空间要求高,必须有足够的连续的内存空间
4.数组空间的大小固定,不能动态扩展


=====链表=====
1.在内存中,元素的空间可以在任意地方,空间是分散的,不需要连续 
2.链表中的元素都会两个属性,一个是元素的值,另一个是指针,此指针标记了下一个元素的地址
每一个数据都会保存下一个数据的内存的地址,通过此地址可以找到下一个数据
3.查找数据时效率低,时间复杂度为O(N)
因为链表的空间是分散的,所以不具有随机访问性,如要需要访问某个位置的数据,需要从第一个数据开始找起,依次往后遍历,直到找到待查询的位置,故可能在查找某个元素时,时间复杂度达到O(N)
4.空间不需要提前指定大小,是动态申请的,根据需求动态的申请和删除内存空间,扩展方便,故空间的利用率较高 
5.任意位置插入元素和删除元素效率较高,时间复杂度为O(1) 
6.链表的空间是从堆中分配的
====链表的优点====
1.任意位置插入元素和删除元素的速度快,时间复杂度为O(1) 
2.内存利用率高,不会浪费内存 
3.链表的空间大小不固定,可以动态拓展

====链表的缺点====
随机访问效率低,时间复杂度为0(N)


文章属性
精彩评论