数组和链表-Array and Linked list

xiaoxiao2025-10-21  7

数组和链表

数组

数组必须相连

若超出预留空间(添加元素):预留更多空间

缺点:

用不上,浪费内存

超出内存要转移

链表

链表中的元素可以存储在内存任何地方,链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起

缺点:

读取元素效率低:从第一个开始读取

 

数组

链表

读取

O(1)

O(n)

插入

O(n)

O(1)

删除

O(n)

O(1)

在中间插入

数组:将后面元素向后移,若没有足够空间需要转移地址

链表:修改其前面元素指向的地址(和其指向的元素?)

删除

数组:删除元素后,必须将后面的元素向前移

链表:只需修改前一个元素指向的地址

PS:仅当能够立即访问要删除的元素时,删除操作的运行时间才为O(1)(通常记录了链表的第一个元素和最后一个元素,因此删除这些元素时运行时间为O(1))

数组VS链表

数组支持随机访问和顺序访问

链表支持顺序访问

转载请注明原文地址: https://www.6miu.com/read-5038320.html

最新回复(0)