ArrayList数组列表和LinkedList双向链表的性能分析比较

简单的说一下传说中的ArrayList数组列表LinkedList双向链表的性能对比。既然ArrayList具有数组的特性,LinkedList具有双向链表的特性,可以分析得出下面的结论:

存储分配:

ArrayList:

本质上是使用数组存储的,所以是使用一段连续的存储单元依次存放所有的元素。

LinkedList:

是基于链表的,采用链式存储结构,用一组任意的存储单元存放所有元素。

时间性能:

ArrayList:

查找:O(1)

插入和删除:需要平均移动表长一半的元素,时间为O(n)。

LinkedList:

查找:O(n)

插入和删除:在指出需要插入或删除的结点的位置的情况下,时间为O(1)。

空间性能:

ArrayList:

需要预分配存储空间,当空间不足时,动态的增长。

LinkedList:

不需要分配存储空间,只需创建一个头结点header,随时根据需要把内存空间链接起来。

arthinking wechat
欢迎关注itzhai公众号