1 List 接口

java.util 中的集合類包含 Java 中某些最常用的類。最常用的集合類是 List 和 Map。
List是一種常用的集合類型，它可以存儲任意類型的對象，也可以結合泛型來存儲具體的類型對象，本質上就是一個容器。

1.1 List 類型介紹

1. 有序性: List中的元素是按照添加順序進行存放的。因為有序，所以有下標，下標從0開始
2. 可重復性： List中可以存儲重復的元素
   List中主要有ArrayList、LinkedList兩個實現類。
   

2 List 接口

2.1 List 初始化

// 創建集合
List list = new ArrayList<>();// 添加元素
list.add("hello");
list.add("world");
list.add("java");// public boolean remove(Object o)：刪除指定的元素，返回刪除是否成功
list.remove("world");//true
// public E remove(int index)：刪除指定索引處的元素，返回被刪除的元素
list.remove(1);//world
// public E set(int index,E element)：修改指定索引處的元素，返回被修改的元素
list.set(1,"javaee");//world// IndexOutOfBoundsException
list.remove(3);

2.2 List 常用API

ArrayList和LinkedList通用方法。

方法名								說明
public boolean add(要添加的元素)		將指定的元素追加到此集合的末尾
public boolean remove(要刪除的元素)	刪除指定元素,返回值表示是否刪除成功
public E remove(int index)			刪除指定索引處的元素，返回被刪除的元素
public E set(int index,E element)	修改指定索引處的元素，返回被修改的元素
public E get(int index)				返回指定索引處的元素
public int size()					返回集合中的元素的個數
boolean contains(Object o)			如果此列表包含指定的元素，則返回 true
boolean addAll(int index, Collection<? extends E> c)									將指定集合中的所有元素插入到此列表中，從指定的位置開始
void clear()						列表中刪除所有元素

2.3 List 遍歷方式

List<String> list = new ArrayList<String>();
list.add("aaa");
list.add("bbb");
list.add("ccc");//方法一：超級for循環遍歷
for(String attribute : list) {System.out.println(attribute);
}
//方法二：對于ArrayList來說速度比較快, 用for循環, 以size為條件遍歷:
for(int i = 0 ; i < list.size() ; i++) {system.out.println(list.get(i));
}
//方法三：集合類的通用遍歷方式, 從很早的版本就有, 用迭代器迭代
Iterator it = list.iterator();
while(it.hasNext()) {System.ou.println(it.next);
}

3 ArrayList

ArrayList是Java中的實現List接口的類，底層使用數組來存儲元素。但與數組相比，它具有更靈活的大小和動態的增加和刪除元素。

注意: 由于 ArrayList 底層使用的是數組，因此一旦創建了 ArrayList，它的大小就是固定的。而當元素添加到 ArrayList 中時，如果底層數組已滿，則需要創建一個更大的數組，并將原有元素復制到新數組中，這會帶來一定的性能損耗。
因此，在實際開發中，建議在創建 ArrayList 時設置一個合適的初始化容量，避免在運行時頻繁進行擴容操作，同時也可避免浪費過多空間資源。
例如：new ArrayList(50);將ArrayList初始容量改為50

3.1 ArrayList 數據結構

ArrayList的數據結構本質上就是數組。區別在于，數組是一種靜態的數據結構，需要在創建數組時就指定它的長度，并且創建后長度無法改變。而ArrayList是一種動態的數據結構，它可以自動進行擴容。

3.2 ArrayList 類定義

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList是一個繼承于AbstractList的線性數據結構。

AbstractList提供了List接口的默認實現（個別方法為抽象方法）

• ArrayList 實現 List 接口，能對它進行隊列操作。
• ArrayList 實現了Cloneable接口，即覆蓋了函數clone()，能克隆。
• ArrayList 實現java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。
• ArrayList 實現RandomAccess接口,提供了隨機訪問功能。RandmoAccess是java中用來被List實現，為List提供快速訪問功能的。在ArrayList中，我們即可以通過元素的序號快速獲取元素對象；這就是快速隨機訪問。
  

3.3 ArrayList 特點

除了具備List有序性、可重復性特點外，ArrayList還具備以下的特點：

• 自動擴容 ：當向ArrayList中加入的元素超過了其默認的長度時（由于ArrayList是數組的封裝類，在創建ArrayList時不用給定長度，其默認長度為10），它會自動擴容以增加存儲容量
• 隨機訪問：隨機訪問是指可以直接訪問元素，而不需要從頭部或者尾部遍歷整個列表。由于ArrayList底層是用數組實現的，因此可以通過索引來快速訪問元素。
• 慢速插入/刪除：：相比于鏈表（如LinkedList），ArrayList在中間插入或刪除元素較慢，因為需要移動元素。
• 高效的遍歷：由于ArrayList底層采用了數組來存儲元素，所以對于ArrayList的遍歷操作比較高效。

3.4 ArrayList 特定API

方法名							說明
ArrayList() 					ArrayList構造函數。默認容量是10
ArrayList(int initialCapacity)  ArrayList帶容量大小的構造函數
ArrayList(Collection<? extends E> c)創建一個包含collection的ArrayList
trimToSize()					將內部存儲的數組大小調整為列表中元素的實際數量。
ensureCapacity(int minCapacity)	設置內部存儲的數組大小，以容納指定數量的元素。
toArray(T[] a)					將列表中的元素轉換為指定類型的數組

4 LinkedList

LinkedList也是Java中實現List接口的常用集合類，底層使用的是雙向鏈表數據結構。

與ArrayList不同，LinkedList在內部存儲元素時，不是使用連續的內存空間，而是使用一個鏈表來存儲元素。

4.1 LinkedList 數據結構

LinkedList底層采用的是雙向鏈表（doubly linked list） 數據結構。鏈表中的每個節點（結點）都由兩個部分組成，一部分是存儲數據元素的值域，另一部分是指向前一個節點和后一個節點的指針（引用）。對于雙向鏈表來說，除了一個指向前一個節點的指針外，還有一個指向后一個節點的指針

4.2 LinkedList 類定義

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。

為什么要繼承自AbstractSequentialList ?
AbstractSequentialList 實現了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)這些骨干函數。降低了List接口的復雜度。LinkedList雙向鏈表通過繼承于AbstractSequentialList，就相當于已經實現了“get(int index)這些接口”。
此外，若需要通過AbstractSequentialList自己實現一個自定義列表，只需要擴展此類，并提供 listIterator() 和 size() 方法的實現即可。若要實現不可修改的列表，則需要實現列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

• LinkedList 實現 List 接口，能對它進行隊列操作。
• LinkedList 實現 Deque 接口，即能將LinkedList當作雙端隊列使用。
• LinkedList 實現了Cloneable接口，即覆蓋了函數clone()，能克隆。
• LinkedList 實現java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。
  LinkedList 是非同步的。
  

4.3 LinkedList 特點

• 隨機訪問性能較差：LinkedList的隨機訪問性能較差，因為在鏈表中要從頭開始遍歷鏈表，直到找到目標元素。所以如果在代碼中需要頻繁進行隨機訪問元素的操作，LinkedList可能不是一個最佳的選擇。
• 添加/刪除操作快：由于LinkedList底層使用雙向鏈表，因此它的添加和刪除操作非常快，因為只需要更改指針的指向即可，不需要像ArrayList一樣重新分配數組空間，而且LinkedList還支持在指定位置插入和刪除元素。
• 需要額外空間：鏈表中每個節點都需要額外存儲到前一個和后一個節點的指針，因此比數組等其他數據結構需要更多的內存空間。
• 適用于隊列和雙端隊列：LinkedList還可以支持隊列和雙端隊列的功能，如在鏈表頭部或尾部添加或刪除元素，實現隊列和雙端隊列的常見操作。

4.4 LinkList 特定API

方法名				說明
LinkedList()		構造方法
LinkedList(Collection<? extends E> c) 創建一個包含collection的LinkedList
addFirst(E element)	將元素添加到列表的開頭
getFirst()  		返回列表的第一個元素。
getLast()			返回列表的最后一個元素。
removeFirst()		刪除并返回列表的第一個元素。
removeLast()		刪除并返回列表的最后一個元素。

5 ArrayList與LinkedList的比較

• 由于ArrayList的數據結構為數組，所以查詢修改快，新增刪除慢；而LinkedList的數據結構為鏈表結構，所以查詢修改慢，新增刪除快
• ArrayList是基于數組實現的動態數組，在內存中有連續的空間，可以通過下標訪問元素，由于數組需要提前分配一定大小的空間，因此當元素數量增多之后，可能會導致數組空間不足需要重新分配數組，這種情況下可能會出現內存空間浪費；相比之下，LinkedList是基于鏈表實現的，每個元素都有一個引用指向下一個元素，不需要提前分配空間，因此能夠更加靈活地插入和刪除元素。然而，鏈表在內存中是不連續的，每個元素的引用占用額外的內存空間。由于鏈表中每個元素都需要有一個指向下一個元素的引用，因此在存儲同樣數量的元素時，LinkedList通常會占用比ArrayList更大的內存空間。

轉載鏈接

https://www.cnblogs.com/lzq198754/p/5780165.html
https://blog.csdn.net/TestXzing/article/details/131197073
https://blog.csdn.net/jianyuerensheng/article/details/51204598