ArrayList 和 LinkedList 的区别?

ArrayList:底层是基于数组实现的,查找快,增删较慢;

LinkedList:底层是基于链表实现的。确切的说是循环双向链表(JDK1.6 之前是双向循环链表、JDK1.7 之后取消了循环),查找慢、增删快。LinkedList 链表由一系列表项连接而成,一个表项包含 3 个部分:元素内容、前驱表和后驱表。链表内部有一个 header 表项,既是链表的开始也是链表的结尾。header 的后继表项是链表中的第一个元素,header 的前驱表项是链表中的最后一个元素。

ArrayList 的增删未必就是比 LinkedList 要慢:

  1. 如果增删都是在末尾来操作【每次调用的都是 remove() 和 add()】,此时 ArrayList 就不需要移动和复制数组来进行操作了。如果数据量有百万级的时,速度是会比 LinkedList 要快的。

  2. 如果删除操作的位置是在中间。由于 LinkedList 的消耗主要是在遍历上,ArrayList 的消耗主要是在移动和复制上(底层调用的是 arrayCopy() 方法,是 native 方法)。LinkedList 的遍历速度是要慢于 ArrayList 的复制移动速度的如果数据量有百万级的时,还是 ArrayList 要快。

发表评论