文档章节

【Java集合类】ArrayList与LinkedList官方说明

YuanyuanL
 YuanyuanL
发布于 2016/07/12 13:16
字数 760
阅读 32
收藏 0

LinkedList and ArrayList are two different implementations of the List interface. LinkedListimplements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.

As with standard linked list and array operations, the various methods will have different algorithmic runtimes.

For LinkedList<E>

  • get(int index) is O(n/4) average
  • add(E element) is O(1)
  • add(int index, E element) is O(n/4) average
         but O(1) when index = 0 <--- main benefit of LinkedList<E>
  • remove(int index) is O(n/4) average
  • Iterator.remove() is O(1) <--- main benefit of LinkedList<E>
  • ListIterator.add(E element) is O(1) <--- main benefit of LinkedList<E>

Note: O(n/4) is average, O(1) best case (e.g. index = 0), O(n/2) worst case (middle of list)

For ArrayList<E>

  • get(int index) is O(1) <--- main benefit of ArrayList<E>
  • add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
  • add(int index, E element) is O(n/2) average
  • remove(int index) is O(n/2) average
  • Iterator.remove() is O(n/2) average
  • ListIterator.add(E element) is O(n/2) average

Note: O(n/2) is average, O(1) best case (end of list), O(n) worst case (start of list)

LinkedList<E> allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list. Javadoc says "operations that index into the list will traverse the list from the beginning or the end, whichever is closer", so those methods are O(n/4) on average, though O(1) for index = 0.

ArrayList<E>, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.

So depending on the operations you intend to do, you should choose the implementations accordingly. Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you're doing something really performance-sensitive, you shouldn't worry about this -- they're both constants.)

The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n), whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).

Another benefit of using a LinkedList arise when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList. Note that ArrayDeque may be a good alternative to LinkedList for adding and removing from the head, but it is not a List.

Also, if you have large lists, keep in mind that memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don't have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added.

The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 - 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements. To avoid the high cost of resizing when you know you're going to add a lot of elements, construct the ArrayList with a higher initial capacity.

It's worth noting that Vector also implements the List interface and is almost identical toArrayList. The difference is that Vector is synchronized, so it is thread-safe. Because of this, it is also slightly slower than ArrayList. So as far as I understand, most Java programmers avoid Vector in favor of ArrayList since they will probably synchronize explicitly anyway if they care about that.

© 著作权归作者所有

共有 人打赏支持
YuanyuanL

YuanyuanL

粉丝 153
博文 323
码字总数 189405
作品 0
济南
部门经理
私信 提问
Java Connection集合分析之List

Java Connection集合家庭分析 Java集合大致可以分为Set、List、Queue和Map四种体系,其中Set代表无序、不可重复的集合;List代表有序、重复的集合;而Map则代表具有映射关系的集合,Java 5 ...

我爱春天的毛毛雨
2018/11/14
0
0
从 Java 代码到 Java 堆

从 Java 代码到 Java 堆 分析是一种美德,PS原文地址:http://www.ibm.com/developerworks/cn/java/j-codetoheap/ 理解和优化您的应用程序的内存使用 本文将为您提供 Java™ 代码内存使用情况...

北极之北
2016/03/10
568
3
Java高级篇 -- List选择及优化

在java编程中,我们常常使用到java自带的集合类List 以下为几点简单的优化建议: 1.Vector还是ArrayList Vector有其特有有点,其每个方法都为同步方法【synchronized】,所以是线程安全的,在...

YOTOO
2014/05/05
0
0
关于java.util.Vector 或 java.util.Hashtable类过时的讨论

某些高级IDE在检测代码成熟问题时,会报告集合是否过时的问题。目前过时的集合类有两个java.util.Vector 和 java.util.Hashtable 。 Vector的api描述是:从jdk 1.2版本开始,该类被修正为实现...

Barudisshu
2013/09/10
0
2
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
2018/08/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql 查询当天、本周,本月,上一个月的数据

今天 select * from 表名 where to_days(时间字段名) = to_days(now()); 昨天 SELECT * FROM 表名 WHERE TO_DAYS( NOW( ) ) - TO_DAYS( 时间字段名) <= 1 近7天 SELECT * FROM 表名 wher......

BraveLN
25分钟前
2
0
Android Multimedia框架总结(六)C++中MediaPlayer的C/S架构

前面几节中,都是通过java层调用到jni中,jni向下到c++层并未介绍 看下Java层一个方法在c++层 MediaPlayer后续过程 frameworks/av/media/libmedia/MediaPlayer.cpp 找一个我们之前熟悉的setDa...

天王盖地虎626
43分钟前
2
0
【Linux】【MySQL】CentOS7安装最新版MySQL8.0.13(最新版MySQL从安装到运行)

1、前言   框框博客在线报时:2018-11-07 19:31:06   当前MySQL最新版本:8.0.13 (听说比5.7快2倍)   官方之前表示:MySQL 8.0 正式版 8.0.11 已发布,MySQL 8 要比 MySQL 5.7 快 2 ...

Code辉
43分钟前
1
0
oracle dg备库重建redolog:ora-00313,ora-00312

trace文件: Errors in file /crbank/dbs/app/product/diag/rdbms/rdbs/dbs/trace/dbs_mrp0_24445130.trc: ORA-00313: open failed for members of log group 8 of thread 1 ORA-00312: onl......

hnairdb
57分钟前
1
0
深入分析Java I/O的工作机制 (一)

1.Java的I/O类库的基本架构 先说一下什么是类库:可以说是类的集合,类库包括接口、抽象类、具体类等。 I/O是机器获取和交互信息的主要渠道。 java在I/O上也一直在做持续的优化,在1.4版开始...

java菜分享
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部