ArrayList、LinkedList，及其它们的区别（在效率、底层、空间等方面）_linkedlist arraylist

Java知识点总结：想看的可以从这里进入

8.2.2、List

列表（list）是元素的有序集合，它提供了基于元素位置的操作（下标），有助于快速访问、添加和删除列表中特定索引位置的元素。List 接口实现了 Collection 和 Iterable 作为父接口，元素允许重复，按照插入顺序依次排列，需要时通过索引下标来访问集合中的元素。List集合有两种常用的实现类：ArrayList类和LinkedList类。（List的一些特性主要是用来弥补数组的不足）

List除了Collection提供方法外，还根据自身的索引性质增加了一些方法：

1、boolean add(int index, Object o)：将o插入指定位置index，后面对象的索引位置相对后移１位
   boolean addAll(int index, Collection c):从index位置开始将c中的所有元素添加进来
2、remove(int index)：移除指定位置元素
3、set(int index, Object element)：用指定元素替换集合中指定位置的元素
4、get(int index)：通过索引获取相应元素
5、int indexOf(Object o)：返回指定元素位置的索引。存在多个时，返回第一个的索引位置，不存在返回-１
6、int lastIndexOf(Object o)：返回指定元素位置的索引。存在多个时，返回最后一个的索引位置，不存在返回-１
7、ListIterator<> listIterator()：返回此集合元素的列表迭代器
8、ListIterator<> listIterator(int index)：，从列表的指定位置开始，返回此集合元素的列表迭代器
9、List <> subList(int start, int end)：返回一个指定区域的List子集合对象，[start,end)
1
2
3
4
5
6
7
8
9
10

1、ArrayList

ArrayList 继承了 AbstractList （抽象类，实现了List接口）。它相当于一个可变的数组，可保存所有的元素，包括null。它和数组一样，通过下标索引快速访问集合中的元素，但是添加元素和删除元素却非常麻烦，需要依次改变元素的下标值。

• 创建，构造方法

  1、ArrayList()：构造一个初始容量为10的集合
  2、ArrayList(Collection<? extends E> c)	构造一个包含Collection的元素的集合，这些元素按照Collection迭代器返回他们的顺序排列的
  3、ArrayList(int initialCapacity)：构造一个具有指定初始容量的集合
  1
  2
  3

  • DK1.7：像饿汉式，直接创建一个初始容量为10的数组
  • JDK1.8：像懒汉式，一开始创建一个长度为0的数组，当添加第一个元素时再创建一个始容量为10的数组
  

• 特点

  • 底层是动态数组，一个连续的内存，排列有序，元素可重复

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uCD8B9kH-1676439793859)(C:/Users/%E7%BE%BD/AppData/Roaming/Typora/typora-user-images/image-20230211160326236.png)]

  • 有下标，通过下标修改、查询元素速度快

  • 线程不安全，但是效率高

  • 尾插数据时速度是o(1)，非尾插数据，会涉及元素的移动，在添加元素时会涉及到扩容的问题。超出初始长度时，会创建新的数组，将原数组数据赋值到新数组中。扩容：原来数组的大小＋原来数组的一半（1.5倍）

    

• 方法

  1、add()：将元素插入到指定位置的 arraylist 中
     add(int index, Object o)：在指定的索引位置添加元素。索引位置必须介于0和列表中元素个数之间
     addAll()：添加集合中的所有元素到 arraylist 中
  2、forEach()：遍历 arraylist 中每一个元素并执行特定操作
  3、clear()：删除 arraylist 中的所有元素
  4、clone()：复制一份 arraylist
  5、contains()：判断元素是否在 arraylist
     containsAll()：查看 arraylist 是否包含指定集合中的所有元素
  6、get()：通过索引值获取 arraylist 中的元素
  7、indexOf()：返回 arraylist 中元素的索引值
  8、removeAll()：删除存在于指定集合中的 arraylist 里的所有元素
     remove()：删除 arraylist 里的单个元素
     removeIf()：删除所有满足特定条件的 arraylist 元素
     removeRange()：删除 arraylist 中指定索引之间存在的元素
  9、replaceAll()：将给定的操作内容替换掉数组中每一个元素
  10、size()：返回 arraylist 里元素数量
  11、isEmpty()：判断 arraylist 是否为空
  12、subList()：截取部分 arraylist 的元素
  13、set()：替换 arraylist 中指定索引的元素
  14、sort()：对 arraylist 元素进行排序
  15、toArray()：将 arraylist 转换为数组
  16、toString()：将 arraylist 转换为字符串
  17、ensureCapacity()：设置指定容量大小的 arraylist
  18、lastIndexOf()：返回指定元素在 arraylist 中最后一次出现的位置
  19、retainAll()：保留 arraylist 中在指定集合中也存在的那些元素
  20、trimToSize()	：将 arraylist 中的容量调整为数组中的元素个数
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26

• 数组可以包含基本数据类型和引用类型，ArrayList只能包含引用类型。
• 数组的大小在定义后不可以调整大小。ArrayList是基于动态数组实现的，可以通过内部扩容自动调整容量。
• ArrayList还是List接口的实现类，相比数组支持更多的方法和特性。

2、LinkedList

LinkedList采用链表的结构保存数据，它是一种线性表，在每一个节点里都存着下一个节点的地址，所以是分散存放在内存中的，不连续，对内存要求低。数据元素的逻辑顺序是通过链表中的指针链接次序实现的，由一系列结点组成，结点可以在运行时动态生成，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点、上一节点地址的指针域。

由于LinkedList实现了List接口和Deque接口，所以它可以看成是一个顺序容器，也可以看成一个队列，甚至还可以当做一个栈使用（但一般队列或栈会使用ArrayDeque）。

链表适合插入、删除数据。但是查找、修改内部某一元素时效率低(越靠近中间越低)，需要迭代遍历

链表可分为单向链表和双向链表（底层链表细分可分为8种结构）。

• 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接。

  

• 一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接。

  

1、add(E e)		将指定元素追加到此列表的末尾，成功为 true，失败为 false。
   add(int index, E element)	将指定元素插入到此列表中的指定位置。
   addAll(Collection c)	 将一个集合的所有元素按迭代器返回的顺序添加到末尾，返回是否成功，成功为 true，失败为 false。
   addAll(int index, Collection c)	将集合的所有元素添加到链表的指定位置后面，成功为 true，失败为 false。
   addFirst(E e)	将指定元素插入到列表的开头
   addLast(E e)		将指定元素追加到此列表的末尾。
   push(E e)   将一个元素压入由此列表表示的堆栈(将元素插入到列表的前面),这个方法等价于addFirst。
2、offer(E e)	将指定元素添加为列表的尾部，返回是否成功，成功为 true，失败为 false。
   offerFirst(E e)	头部插入元素，返回是否成功，成功为 true，失败为 false。
   offerLast(E e)	尾部插入元素，返回是否成功，成功为 true，失败为 false。
3、clear()	清空链表。
4、removeFirst()	 从列表中删除并返回第一个元素
   removeLast()	  从列表中删除并返回最后一个元素。
   remove(Object o)	 如果指定元素存在，则从此列表中删除该元素的第一次出现。如果该列表不包含该元素，则该列表不变。
   remove(int index)  删除此列表中指定位置的元素。将所有后续元素向左移动，返回从列表中移除的元素。
   remove()	 返回列表头元素，并删除。
   removeIf(Predicate<? super E> filter) ：删除此集合中满足给定谓词的所有元素。方法内使用迭代
   pop()   从此列表表示的堆栈中弹出一个元素(删除并返回该列表的第一个元素),该方法等价于removeFirst()
5、contains(Object o)	判断是否含有某一元素。
6、get(int index)	返回列表中指定位置的元素
   getFirst()	返回此列表中的第一个元素。
   getLast()	返回此列表中的最后一个元素。
7、indexOf(Object o)	查找指定元素从前往后第一次出现的索引。
8、lastIndexOf(Object o)	查找指定元素最后一次出现的索引。
9、E peek()	返回第一个元素，不删除。
   element()	返回第一个元素，不删除
   peekFirst()	返回头部元素,不删除。
   peekLast()	返回尾部元素，不删除。
   poll()	 返回列表头元素，并删除。
   pollFirst()  检索并删除此列表的第一个元素,如果此列表为空则返回null
   pollLast()   检索并删除此列表的最后一个元素，如果此列表为空则返回null。
10、set(int index, E element)	将列表中指定位置的元素替换为指定的元素。
11、clone()	克隆该列表。
12、descendingIterator()	返回倒序迭代器。
13、size()	返回链表元素个数。
14、listIterator(int index)	返回从指定位置开始到末尾的迭代器。
15、toArray()	返回一个由链表元素组成的数组。
	toArray(T[] a)	返回一个由链表元素转换类型而成的数组。
16、isElementIndex(int index)   告诉参数是否是现有元素的索引。
	isPositionIndex(int index)  告诉参数是否是迭代器或添加操作的有效位置的下标。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

3、两者区别

ArrayList 和 LinkedList 是 Java 集合框架中用来存储对象引用列表的两个类，都实现 List 接口，存储的数据有序，且可重复，而且两者在多线程环境中都是不安全的。但因为底层分别是动态数组和链表的缘故，就导致它们很多特性都有所不同：

1. 数据结构

   ArrayList底层是动态数组，在空间中是一段连续的内存

   LinkedList底层是链表，内存不连续，对内存要求低。

2. 空间利用：

   ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间

   LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

3. 尾插数据：对ArrayList和LinkedList而言，在列表末尾增加一个元素时间复杂度都是 o(1)。

   对ArrayList来说，尾插速度非常快，但是会涉及到一个扩容的问题，会进行大量的复制操作。

   而对LinkedList而言，使用了链表结构，不需要维护大小，但是他每次添加需要新建entry对象，进行赋值操作。

   总得来说如果不涉及到扩容的问题，ArrayList的尾插会更快一些。

   public static void main(String[] args) {
       List<String> arraylist = new ArrayList<>();
       int listSize = 1000000;
       for(int i=0; i<listSize; i++){
           arraylist.add("初始数据");
       }
       System.out.println("ArrayList尾插数据用时：" + insert(arraylist));
   
       List<String> linkedList = new LinkedList<>();
       for(int i=0; i<listSize; i++){
           linkedList.add("初始数据");
       }
       System.out.println("LinkedList尾插数据用时：" + insert(linkedList));
   }
   
   
   //插入数据，分别在头部、中间、尾部（四种插入位置：10、list.size()/2、list.size()-10、尾插）
   public static Long insert(List<Integer> list){
       long startTime = System.currentTimeMillis();
       int insertNum = 500000;
       for (int i=0; i<insertNum; i++){
           list.add("数据"+i);
           //list.add(10,"数据"+i);
           //list.add(list.size()/2,"数据"+i);
       }
       long endTime = System.currentTimeMillis();
       return endTime-startTime;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28

   

4. 非尾插数据：

   在ArrayList的中间插入或删除一个元素会导致列表中剩余的元素都会被移动，因此效率较低，插入位置越靠前，需要复制调整的元素也越多，效率也就越慢。

   LinkedList的非尾插，首先要通过循环找到需要插入的位置。如果此位置处于前半段，则从前往后找；若其位置处于后半段，则从后往前找。所以在靠前和靠后的位置插入非常高效，但是在拥有大量元素的情况下，在链表的中间插入元素效率很低。（首尾复杂度为o(1)，其余为o(n)，整体来说还是o(n)）

   

5. 删除元素：(元素的删除和插入效果类似)

   在ArrayList的每一次有效的元素删除操作后，都要进行数组的重组。并且删除的位置越靠前，数组重组时的开销越大。

   LinkedList的删除，首先要通过循环找到要删除的元素。如果要删除的位置处于前半段，则从前往后找；若其位置处于后半段，则从后往前找。所以要删除较为靠前或者靠后的元素都是非常高效的；但要移除中间的元素却几乎要遍历完半个List，在List拥有大量元素的情况下，效率很低。

6. 容量参数：ArrayList等底层基于数组的数据结构的参数，它表示初始化的数组大小，当素数量超过其已有大小时，会进行扩容，数组的扩容会导致整个数组进行一次内存复制，所以设定一个合理的初始大小有助于减少数组扩容的次数，从而提高系统性能。

   此参数是LinkedList所没有的

7. 遍历列表：总体来说ArrayList效率要高于LinkedList

   对于ArrayList来说，因为其索引的缘故，大致的速度为：for循环<迭代器<forEach。通过索引获取数据时间复杂度为 O ( 1 ) 。

   对于LinkedList来说，大致的速度为：迭代器<forEach<for循环（LinkedList不支持高效的随机元素访问），获取头部元素和尾部元素时间复杂度为O(1)

   public static void main(String[] args) {
       List<String> arraylist = new ArrayList<>();
       int listSize = 100000;
       for(int i=0; i<listSize; i++){
           arraylist.add("初始数据"+i);
       }
       System.out.println("ArrayList使用for遍历：" + forList(arraylist));
       System.out.println("ArrayList使用forEach遍历：" + forEachList(arraylist));
       System.out.println("ArrayList使用迭代器遍历：" + iteratorList(arraylist));
   
   
       List<String> linkedList = new LinkedList<>();
       for(int i=0; i<listSize; i++){
           linkedList.add("初始数据"+i);
       }
       System.out.println("LinkedList使用for遍历：" + forList(linkedList));
       System.out.println("LinkedList使用forEach遍历：" + forList(linkedList));
       System.out.println("LinkedList使用迭代器遍历：" + iteratorList(linkedList));
   }
   public static Long forList(List<String> list){
       long startTime = System.currentTimeMillis();
       StringBuilder builder = new StringBuilder(100000);
       int size = list.size();
       for(int i=0; i<size; i++){
           builder.append(list.get(i));
       }
       long endTime = System.currentTimeMillis();
       return endTime-startTime;
   }
   
   public static Long forEachList(List<String> list){
       long startTime = System.currentTimeMillis();
       StringBuilder builder = new StringBuilder(100000);
       for (String s : list) {
           builder.append(s);
       }
       long endTime = System.currentTimeMillis();
       return endTime-startTime;
   }
   
   public static Long iteratorList(List<String> list){
       long startTime = System.currentTimeMillis();
       StringBuilder builder = new StringBuilder(100000);
       Iterator<String> iterator = list.iterator();
       while (iterator.hasNext()){
           builder.append(iterator.next());
       }
       long endTime = System.currentTimeMillis();
       return endTime-startTime;
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21
   22
   23
   24
   25
   26
   27
   28
   29
   30
   31
   32
   33
   34
   35
   36
   37
   38
   39
   40
   41
   42
   43
   44
   45
   46
   47
   48
   49
   50

   

当操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会有更好的性能。当操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了。

4、Vector

Vector 是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。（现在使用较少）