前几天看到一篇文章,里面特意提到了,读取频繁使用ArrayList,增删频繁使用Linkedlist;并且在一个范例中,特意将ArrayList转化为LinkedList以提高末尾插入的效率。而事实上,问题并非如此简单。
ArrayList与LinkedList的异同是我面试较常问的问题。大部分人可能都知道前者基于数组而后者基于链表(能答出双向链表自然更好),并且前者适合读取、后者适合插入删除;偶有候选人能曰“It depends”并给出具体情况之分析时,往往能获得不错的第一印象。
抛开具体语言的实现不说,先从数据结构上看一下,两者时间、空间负责度上的区别:
查找自不必说,插入删除与具体的位置有关,如果在首部、中部执行增删,考虑到ArrayList需要复制指定位置之后的所有元素,因此具有O(N)的时间复杂度;而LinkedList则只需O(1)。
如果是尾部增加、删除的情况,ArrayList不需要移动任何元素,因此两者的理论时间复杂度都为
O(1)。考虑得更细一点,如果是尾部增加的情况,LinkedList需要重新向JVM申请内存空间,而ArrayList不需要,因其一开始就会申请较多的空间,并且可以通过初始化capacity来避免动态膨胀的开销;如果是尾部减少的情况,LinkedList或许会带来GC释放内存的开销,而ArrayList仅需简单的将length减一;并且考虑到今后的扩展性,无论是哪种情况,使用ArrayList要划算得多。
另外,特别提一下删除操作,我前面特意强调“抛开具体语言不说”,是因为虽然理论上LinkedList的随机增删的时间复杂度是O(1),但那是对于传入的是其内部某节点指针或者entry而言的,而事实上,在JAVA中由于不存在指针一说,并且对其数据结构的完美隐藏,大部分情况我们不会直接传入某个entry,而是基于以下两种情况的元素删除:
- 删除特定index的元素,对应LinkedList.remove(int)方法
- 删除特定值的元素,LinkedList.remove(Object)
事实上,对于上述情况,在删除前势必需要一个定位查找的工作,而众所周知,LinkedList在元素遍历上相当低效的,因此删除元素的时间复杂度应该是O(1) + O(N),也就是O(N)。当然java进行了优化,譬如说采用折半查找索引的方式
Entry<E> e = header;
if (index < (size >> 1)) {
//looking forward
for (int i = 0; i <= index; i++)
e = e.next;
} else {
//looking backward
for (int i = size; i > index; i–)
e = e.previous;
}
尽管如此,还是不敌ArrayList的O(1)。特别的,对于LinkedList.remove(int)方法来说,LinkedList定位慢而删除快,ArrayList定位快而删除慢,因此具体谁领风骚还真不好说,不仅与具体操作的位置有关,还与集合中元素的数量有关。
麻雀虽小五脏俱全,一个小小的LinkedList居然衍生出这么多的花样。以后对于LinkedList增删优于ArrayList一说,切不可一言以蔽之
- 大小: 31.7 KB
分享到:
相关推荐
List-LinkedList 单链表就地反转 的代码的一种实现。
ArrayList、LinkedList、Vector区别简介。
Java 中Linkedlist类的源代码Java 中Linkedlist类的源代码Java 中Linkedlist类的源代码Java 中Linkedlist类的源代码
LinkedLIst.cpp
java LinkedList的添加删除操作 java LinkedList的添加删除操作
使用LinkedList模拟堆栈操作,包括进栈、出栈,入队、出队
非常简单的Java LinkedList 应用实例
和数组一样,LinkedList 也是一种线性数据结构,但它不像数组一样在连续的位置上存储元素,而是通过引用相互链接。 LinkedList 中的每一个元素都可以称之为节点(Node),每一个节点都包含三个项目:其一是元素本身...
LinkedList的使用.pdf
1.List是接口类,ArrayList和LinkedList是List的实现类 2.ArrayList是动态数组(顺序表)的数据结构 3.LinkedList
LinkedList实践代码,用于学习LinkedList功能,包括二叉树的构建和遍历等。
LinkedList<String> list = new LinkedList(); list.add("aaa"); list.add("bbb"); list.add("ccc"); /* * public void addFirst(E e)方法 * 将指定元素插入此列表的开头 */ list.addFirst("000...
使用LinkedList类编写程序,用某种集合接口的实现类作存储,实现具有自定义排序功能的包含姓名、年龄、身高、职称等内容的人事信息输入和打印。
LinkedList实现栈。对LinkedList添加同步,可以多线程操作。
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。 LinkedList 实现 List 接口,能对它进行队列操作。 LinkedList 实现 Deque 接口,即能将...
数据结构,LinkedList在c++的实现,一共有三个头文件:Link.h 、List.h 、LinkedList。
Arduino-LinkedList.zip,与通用微控制器和Arduino ProjectsLinkedList一起工作的完全实现的LinkedList,Arduino是一家开源软硬件公司和制造商社区。Arduino始于21世纪初,深受电子制造商的欢迎,Arduino通过开源系统...
深入解析hashMap底层原理,非常深入的讲解了HashMap和相关的数据的等信息
比较ArrayList,LinkedList,Vector三者随机读取,插入,删除性能。
测试ArrayList和LinkedList的add方法