Java中List集合的深入介紹(超級推薦!)
1，Java集合介紹
作為一個程序猿，Java集合類可以說是我們在工作中運用最多、最頻繁的類。相比于數(shù)組（Array）來說，集合類的長度可變，更加方便開發(fā)。
Java集合就像一個容器，可以存儲任何類型的數(shù)據(jù)，也可以結(jié)合泛型來存儲具體的類型對象。在程序運行時，Java集合可以動態(tài)的進(jìn)行擴(kuò)展，隨著元素的增加而擴(kuò)大。在Java中，集合類通常存在于java.util包中。
Java集合主要由2大體系構(gòu)成，分別是Collection體系和Map體系，其中Collection和Map分別是2大體系中的頂層接口。
Collection主要有三個子接口，分別為List(列表)、Set(集)、Queue(隊列)。其中，List、Queue中的元素有序可重復(fù)，而Set中的元素?zé)o序不可重復(fù)。
List中主要有ArrayList、LinkedList兩個實現(xiàn)類；Set中則是有HashSet實現(xiàn)類；而Queue是在JDK1.5后才出現(xiàn)的新集合，主要以數(shù)組和鏈表兩種形式存在。
Map同屬于java.util包中，是集合的一部分，但與Collection是相互獨立的，沒有任何關(guān)系。Map中都是以key-value的形式存在，其中key必須唯一，主要有HashMap、HashTable、treeMap三個實現(xiàn)類。
2，List介紹
在Collection中，List集合是有序的，可對其中每個元素的插入位置進(jìn)行精確地控制，可以通過索引來訪問元素，遍歷元素。
在List集合中，我們常用到ArrayList和LinkedList這兩個類。
2.1 ArrayList集合
1，ArrayList底層通過數(shù)組實現(xiàn)，隨著元素的增加而動態(tài)擴(kuò)容。
2，ArrayList是Java集合框架中使用最多的一個類，是一個數(shù)組隊列，線程不安全集合。
它繼承于AbstractList，實現(xiàn)了List, RandomAccess, Cloneable, Serializable接口。
1，ArrayList實現(xiàn)List，得到了List集合框架基礎(chǔ)功能；
2，ArrayList實現(xiàn)RandomAccess，獲得了快速隨機訪問存儲元素的功能，RandomAccess是一個標(biāo)記接口，沒有任何方法；
3，ArrayList實現(xiàn)Cloneable，得到了clone()方法，可以實現(xiàn)克隆功能；
4，ArrayList實現(xiàn)Serializable，表示可以被序列化，通過序列化去傳輸，典型的應(yīng)用就是hessian協(xié)議。
ArrayList集合的特點：
- 容量不固定，隨著容量的增加而動態(tài)擴(kuò)容（閾值基本不會達(dá)到）
- 有序集合（插入的順序==輸出的順序）
- 插入的元素可以為null
- 增刪改查效率更高（相對于LinkedList來說）
- 線程不安全
ArrayList的底層數(shù)據(jù)結(jié)構(gòu)：
2.2 LinkedList集合
1，LinkedList底層通過鏈表來實現(xiàn)，隨著元素的增加不斷向鏈表的后端增加節(jié)點。
2，LinkedList是一個雙向鏈表，每一個節(jié)點都擁有指向前后節(jié)點的引用。相比于ArrayList來說，LinkedList的隨機訪問效率更低。
它繼承AbstractSequentialList，實現(xiàn)了List, Deque, Cloneable, Serializable接口。
1，LinkedList實現(xiàn)List，得到了List集合框架基礎(chǔ)功能；
2，LinkedList實現(xiàn)Deque，Deque 是一個雙向隊列，也就是既可以先入先出，又可以先入后出，說簡單點就是既可以在頭部添加元素，也可以在尾部添加元素；
3，LinkedList實現(xiàn)Cloneable，得到了clone()方法，可以實現(xiàn)克隆功能；
4，LinkedList實現(xiàn)Serializable，表示可以被序列化，通過序列化去傳輸，典型的應(yīng)用就是hessian協(xié)議。
LinkedList集合的底層數(shù)據(jù)結(jié)構(gòu)：
3，List常用方法
A:添加功能 boolean add(E e):向集合中添加一個元素 void add(int index, E element):在指定位置添加元素 boolean addAll(Collection<? extends E> c)：向集合中添加一個集合的元素。 B:刪除功能 void clear()：刪除集合中的所有元素 E remove(int index)：根據(jù)指定索引刪除元素，并把刪除的元素返回 boolean remove(Object o)：從集合中刪除指定的元素 boolean removeAll(Collection<?> c):從集合中刪除一個指定的集合元素。 C:修改功能 E set(int index, E element):把指定索引位置的元素修改為指定的值，返回修改前的值。 D:獲取功能 E get(int index)：獲取指定位置的元素 Iterator iterator():就是用來獲取集合中每一個元素。 E:判斷功能 boolean isEmpty()：判斷集合是否為空。 boolean contains(Object o)：判斷集合中是否存在指定的元素。 boolean containsAll(Collection<?> c)：判斷集合中是否存在指定的一個集合中的元素。 F:長度功能 int size():獲取集合中的元素個數(shù) G:把集合轉(zhuǎn)換成數(shù)組 Object[] toArray():把集合變成數(shù)組。
3.1 ArrayList 基本操作
public class ArrayListTest {
public static void main(String[] agrs){
//創(chuàng)建ArrayList集合：
List<String> list = new ArrayList<String>();
System.out.println("ArrayList集合初始化容量："+list.size());
// ArrayList集合初始化容量：0
//添加功能：
list.add("Hello");
list.add("world");
list.add(2,"!");
System.out.println("ArrayList當(dāng)前容量："+list.size());
// ArrayList當(dāng)前容量：3
//修改功能：
list.set(0,"my");
list.set(1,"name");
System.out.println("ArrayList當(dāng)前內(nèi)容："+list.toString());
// ArrayList當(dāng)前內(nèi)容：[my, name, !]
//獲取功能：
String element = list.get(0);
System.out.println(element);
// my
//迭代器遍歷集合：(ArrayList實際的跌倒器是Itr對象)
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
String next = iterator.next();
System.out.println(next);
}
/**
my
name
!
*/
//for循環(huán)迭代集合：
for(String str:list){
System.out.println(str);
}
/**
my
name
!
*/
//判斷功能：
boolean isEmpty = list.isEmpty();
boolean isContain = list.contains("my");
//長度功能：
int size = list.size();
//把集合轉(zhuǎn)換成數(shù)組：
String[] strArray = list.toArray(new String[]{});
//刪除功能：
list.remove(0);
list.remove("world");
list.clear();
System.out.println("ArrayList當(dāng)前容量："+list.size());
// ArrayList當(dāng)前容量：0
}
}
3.2 LinkedList 基本操作
public class LinkedListTest {
public static void main(String[] agrs){
List<String> linkedList = new LinkedList<String>();
System.out.println("LinkedList初始容量："+linkedList.size());
// LinkedList初始容量：0
//添加功能：
linkedList.add("my");
linkedList.add("name");
linkedList.add("is");
linkedList.add("jiaboyan");
System.out.println("LinkedList當(dāng)前容量："+ linkedList.size());
// LinkedList當(dāng)前容量：4
//修改功能:
linkedList.set(0,"hello");
linkedList.set(1,"world");
System.out.println("LinkedList當(dāng)前內(nèi)容："+ linkedList.toString());
// LinkedList當(dāng)前內(nèi)容：[hello, world, is, jiaboyan]
//獲取功能：
String element = linkedList.get(0);
System.out.println(element);
// hello
//遍歷集合：(LinkedList實際的迭代器是ListItr對象)
Iterator<String> iterator = linkedList.iterator();
while(iterator.hasNext()){
String next = iterator.next();
System.out.println(next);
}
/**
hello
world
is
jiaboyan
*/
//for循環(huán)迭代集合：
for(String str:linkedList){
System.out.println(str);
}
/**
hello
world
is
jiaboyan
*/
//判斷功能：
boolean isEmpty = linkedList.isEmpty();
boolean isContains = linkedList.contains("jiaboyan");
//長度功能：
int size = linkedList.size();
//刪除功能：
linkedList.remove(0);
linkedList.remove("jiaboyan");
linkedList.clear();
System.out.println("LinkedList當(dāng)前容量：" + linkedList.size());
// LinkedList當(dāng)前容量：0
}
}
4，ArrayList和LinkedList比較
（1）元素新增性能比較
網(wǎng)上很多說的是，在做新增操作時，ArrayList的效率遠(yuǎn)不如LinkedList，因為Arraylist底層時數(shù)組實現(xiàn)的，在動態(tài)擴(kuò)容時，性能會有所損耗，而LinkedList不存在數(shù)組擴(kuò)容機制，所以LinkedList的新增性能較好。究竟時哪個好呢，我們用實踐得到結(jié)果。
public class ListTest{
// 迭代次數(shù)
public static int ITERATION_NUM = 100000;
public static void main(String[] args) {
try{
insertPerformanceCompare();
}catch (Exception e){}
}
//新增性能比較：
public static void insertPerformanceCompare() throws InterruptedException {
Thread.sleep(5000);
System.out.println("LinkedList新增測試開始");
long start = System.nanoTime();
List<Integer> linkedList = new LinkedList<Integer>();
for (int x = 0; x < ITERATION_NUM; x++) {
linkedList.add(x);
}
long end = System.nanoTime();
System.out.println(end - start);
System.out.println("ArrayList新增測試開始");
start = System.nanoTime();
List<Integer> arrayList = new ArrayList<Integer>();
for (int x = 0; x < ITERATION_NUM; x++) {
arrayList.add(x);
}
end = System.nanoTime();
System.out.println(end - start);
}
}
測試結(jié)果：
第一次：
LinkedList新增測試開始
10873720
ArrayList新增測試開始
5535277
第二次：
LinkedList新增測試開始
13097503
ArrayList新增測試開始
6046139
第三次：
LinkedList新增測試開始
12004669
ArrayList新增測試開始
6509783
結(jié)果與預(yù)想的有些不太一樣，ArrayList的新增性能并不低。
原因：
? 可能是經(jīng)過JDK近幾年的更新發(fā)展，對于數(shù)組復(fù)制的實現(xiàn)進(jìn)行了優(yōu)化，以至于ArrayList的性能也得到了提高。
（2）元素獲取比較
由于LinkedList是鏈表結(jié)構(gòu)，沒有角標(biāo)的概念，沒有實現(xiàn)RandomAccess接口，不具備隨機元素訪問功能，所以在get方面表現(xiàn)的差強人意，ArrayList再一次完勝。
public class ListTest {
//迭代次數(shù)，集合大?。?
public static int ITERATION_NUM = 100000;
public static void main(String[] agrs) {
try{
getPerformanceCompare();
}catch (Exception e){}
}
//獲取性能比較：
public static void getPerformanceCompare()throws InterruptedException {
Thread.sleep(5000);
//填充ArrayList集合：
List<Integer> arrayList = new ArrayList<Integer>();
for (int x = 0; x < ITERATION_NUM; x++) {
arrayList.add(x);
}
//填充LinkedList集合：
List<Integer> linkedList = new LinkedList<Integer>();
for (int x = 0; x < ITERATION_NUM; x++) {
linkedList.add(x);
}
//創(chuàng)建隨機數(shù)對象：
Random random = new Random();
System.out.println("LinkedList獲取測試開始");
long start = System.nanoTime();
for (int x = 0; x < ITERATION_NUM; x++) {
int j = random.nextInt(x + 1);
int k = linkedList.get(j);
}
long end = System.nanoTime();
System.out.println(end - start);
System.out.println("ArrayList獲取測試開始");
start = System.nanoTime();
for (int x = 0; x < ITERATION_NUM; x++) {
int j = random.nextInt(x + 1);
int k = arrayList.get(j);
}
end = System.nanoTime();
System.out.println(end - start);
}
}
測試結(jié)果：
第一次：
LinkedList獲取測試開始
8190063123
ArrayList獲取測試開始
8590205
第二次：
LinkedList獲取測試開始
8100623160
ArrayList獲取測試開始
11948919
第三次：
LinkedList獲取測試開始
8237722833
ArrayList獲取測試開始
6333427
從結(jié)果可以看出，ArrayList在隨機訪問方面表現(xiàn)的十分優(yōu)秀，比LinkedList強了很多。
原因：
? 這主要是LinkedList的代碼實現(xiàn)所致，每一次獲取都是從頭開始遍歷，一個個節(jié)點去查找，每查找一次就遍歷一次，所以性能自然得不到提升。
5，ArrayList源碼分析
接下來，我們對ArrayList集合進(jìn)行源碼分析，其中先來幾個問題：
（1）ArrayList的構(gòu)造
（2）增刪改查的實現(xiàn)
（3）迭代器——modCount
（4）為什么數(shù)組對象要使用transient修飾符
（5）System.arraycopy()參數(shù)含義 Arrays.copyOf()參數(shù)含義
我們通過上面幾個問題，對ArrayList的源碼進(jìn)行一步一步的解析。
ArrayList構(gòu)造器
1，在JDK1.7版本中，ArrayList的無參構(gòu)造方法并沒有生成容量為10的數(shù)組。
2，elementData對象是ArrayList集合底層保存元素的實現(xiàn)。
3，size屬性記錄了ArrayList集合中實際元素的個數(shù)。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//實現(xiàn)Serializable接口，生成的序列版本號：
private static final long serialVersionUID = 8683452581122892189L;
//ArrayList初始容量大?。涸跓o參構(gòu)造中不使用了
private static final int DEFAULT_CAPACITY = 10;
//空數(shù)組對象：初始化中默認(rèn)賦值給elementData
private static final Object[] EMPTY_ELEMENTDATA = {};
//ArrayList中實際存儲元素的數(shù)組：
private transient Object[] elementData;
//集合實際存儲元素長度：
private int size;
//ArrayList有參構(gòu)造：容量大小
public ArrayList(int initialCapacity) {
//即父類構(gòu)造：protected AbstractList() {}空方法
super();
//如果傳遞的初始容量小于0 ，拋出異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
//初始化數(shù)據(jù)：創(chuàng)建Object數(shù)組
this.elementData = new Object[initialCapacity];
}
//ArrayList無參構(gòu)造：
public ArrayList() {
//即父類構(gòu)造：protected AbstractList() {}空方法
super();
//初始化數(shù)組：空數(shù)組，容量為0
this.elementData = EMPTY_ELEMENTDATA;
}
//ArrayList有參構(gòu)造：Java集合
public ArrayList(Collection<? extends E> c) {
//將集合轉(zhuǎn)換為數(shù)組：
elementData = c.toArray();
//設(shè)置數(shù)組的長度：
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
}
add() 添加
1，在JDK1.7當(dāng)中，當(dāng)?shù)谝粋€元素添加時，ensureCapacityInternal()方法會計算ArrayList的擴(kuò)容大小，默認(rèn)為10。
2，其中g(shù)row()方法最為重要，如果需要擴(kuò)容，那么擴(kuò)容后的大小是原來的1.5倍，實際上最終調(diào)用了Arrays.copyOf()方法得以實現(xiàn)。
//添加元素e
public boolean add(E e) {
ensureCapacityInternal(size + 1);
//將對應(yīng)角標(biāo)下的元素賦值為e：
elementData[size++] = e;
return true;
}
//得到最小擴(kuò)容量
private void ensureCapacityInternal(int minCapacity) {
//如果此時ArrayList是空數(shù)組,則將最小擴(kuò)容大小設(shè)置為10：
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//判斷是否需要擴(kuò)容：
ensureExplicitCapacity(minCapacity);
}
//判斷是否需要擴(kuò)容
private void ensureExplicitCapacity(int minCapacity) {
//操作數(shù)+1
modCount++;
//判斷最小擴(kuò)容容量-數(shù)組大小是否大于0：
if (minCapacity - elementData.length > 0)
//擴(kuò)容：
grow(minCapacity);
}
//ArrayList動態(tài)擴(kuò)容的核心方法:
private void grow(int minCapacity) {
//獲取現(xiàn)有數(shù)組大?。?
int oldCapacity = elementData.length;
//位運算，得到新的數(shù)組容量大小，為原有的1.5倍：
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新擴(kuò)容的大小依舊小于傳入的容量值，那么將傳入的值設(shè)為新容器大小：
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容器大小，大于ArrayList最大長度：
if (newCapacity - MAX_ARRAY_SIZE > 0)
//計算出最大容量值：
newCapacity = hugeCapacity(minCapacity);
//數(shù)組復(fù)制：
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 計算ArrayList最大容量：
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
//如果新的容量大于MAX_ARRAY_SIZE。將會調(diào)用hugeCapacity將int的最大值賦給newCapacity:
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
remove() 刪除
1，remove(int index)是針對于角標(biāo)來進(jìn)行刪除，不需要去遍歷整個集合，效率更高。
2，而remove(Object o)是針對于對象來進(jìn)行刪除，需要遍歷整個集合進(jìn)行equals()方法比對，所以效率較低。
3，不過，無論是哪種形式的刪除，最終都會調(diào)用System.arraycopy()方法進(jìn)行數(shù)組復(fù)制操作，所以效率都會受到影響。
//在ArrayList的移除index位置的元素
public E remove(int index) {
//檢查角標(biāo)是否合法：不合法拋異常
rangeCheck(index);
//操作數(shù)+1：
modCount++;
//獲取當(dāng)前角標(biāo)的value:
E oldValue = elementData(index);
//獲取需要刪除元素 到最后一個元素的長度，也就是刪除元素后，后續(xù)元素移動的個數(shù)；
int numMoved = size - index - 1;
//如果移動元素個數(shù)大于0 ，也就是說刪除的不是最后一個元素：
if (numMoved > 0)
// 將elementData數(shù)組index+1位置開始拷貝到elementData從index開始的空間
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//size減1，并將最后一個元素置為null
elementData[--size] = null;
//返回被刪除的元素：
return oldValue;
}
//在ArrayList的移除對象為O的元素，不返回被刪除的元素：
public boolean remove(Object o) {
//如果o==null，則遍歷集合，判斷哪個元素為null：
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//快速刪除，和前面的remove（index）一樣的邏輯
fastRemove(index);
return true;
}
} else {
//同理：
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//快速刪除：
private void fastRemove(int index) {
//操作數(shù)+1
modCount++;
//獲取需要刪除元素 到最后一個元素的長度，也就是刪除元素后，后續(xù)元素移動的個數(shù)；
int numMoved = size - index - 1;
//如果移動元素個數(shù)大于0 ，也就是說刪除的不是最后一個元素：
if (numMoved > 0)
// 將elementData數(shù)組index+1位置開始拷貝到elementData從index開始的空間
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//size減1，并將最后一個元素置為null
elementData[--size] = null;
}
set() 修改
由于ArrayList實現(xiàn)了RandomAccess，所以具備了隨機訪問特性，調(diào)用elementData()可以獲取到對應(yīng)元素的值。
//設(shè)置index位置的元素值了element，返回該位置的之前的值
public E set(int index, E element) {
//檢查index是否合法：判斷index是否大于size
rangeCheck(index);
//獲取該index原來的元素：
E oldValue = elementData(index);
//替換成新的元素：
elementData[index] = element;
//返回舊的元素：
return oldValue;
}
get() 獲取元素
通過elementData()方法獲取對應(yīng)角標(biāo)元素，在返回時候進(jìn)行類型轉(zhuǎn)換。
//獲取index位置的元素
public E get(int index) {
//檢查index是否合法：
rangeCheck(index);
//獲取元素：
return elementData(index);
}
//獲取數(shù)組index位置的元素：返回時類型轉(zhuǎn)換
E elementData(int index) {
return (E) elementData[index];
}
modCount含義
1，在Itr迭代器初始化時,將ArrayList的modCount屬性的值賦值給了expectedModCount。
2，通過上面的例子中，我們可以知道當(dāng)進(jìn)行增刪改時，modCount會隨著每一次的操作而+1，modCount記錄了ArrayList內(nèi)發(fā)生改變的次數(shù)。
3，當(dāng)?shù)髟诘鷷r，會判斷expectedModCount的值是否還與modCount的值保持一致，如果不一致則拋出異常。
AbstractList類當(dāng)中定義的變量：
protected transient int modCount = 0;
ArrayList獲取迭代器對象：
//返回一個Iterator對象，Itr為ArrayList的一個內(nèi)部類，其實現(xiàn)了Iterator<E>接口
public Iterator<E> iterator() {
return new java.util.ArrayList.Itr();
}
迭代器實現(xiàn)：
//Itr實現(xiàn)了Iterator接口，是ArrayList集合的迭代器對象
private class Itr implements Iterator<E> {
//類似游標(biāo)，指向迭代器下一個值的位置
int cursor;
//迭代器最后一次取出的元素的位置。
int lastRet = -1;
//Itr初始化時候ArrayList的modCount的值。
int expectedModCount = modCount;
//利用游標(biāo)，與size之前的比較，判斷迭代器是否還有下一個元素
public boolean hasNext() {
return cursor != size;
}
//迭代器獲取下一個元素：
public E next() {
//檢查modCount是否改變：
checkForComodification();
int i = cursor;
//游標(biāo)不會大于等于集合的長度：
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = java.util.ArrayList.this.elementData;
//游標(biāo)不會大于集合中數(shù)組的長度：
if (i >= elementData.length)
throw new ConcurrentModificationException();
//游標(biāo)+1
cursor = i + 1;
//取出元素：
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
//檢查modCount是否改變：防止并發(fā)操作集合
checkForComodification();
try {
//刪除這個元素：
java.util.ArrayList.this.remove(lastRet);
//刪除后，重置游標(biāo)，和當(dāng)前指向元素的角標(biāo) lastRet
cursor = lastRet;
lastRet = -1;
//重置expectedModCount：
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//并發(fā)檢查：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
transient 修飾符
1，當(dāng)我們序列化對象時，如果對象中某個屬性不進(jìn)行序列化操作，那么在該屬性前添加transient修飾符即可實現(xiàn)。例如：
private transient Object[] elementData;
那么問題來了，為什么ArrayList不想對elementData屬性進(jìn)行序列化呢？elementData可是集合中保存元素的數(shù)組啊，如果不序列化elementData屬性，那么在反序列化時候，豈不是丟失了原先的元素？
原因是 ArrayList在添加元素時，可能會對elementData數(shù)組進(jìn)行擴(kuò)容操作，而擴(kuò)容后的數(shù)組可能并沒有全部保存元素。
例如：我們創(chuàng)建了new Object[10]數(shù)組對象，但是我們只向其中添加了1個元素，而剩余的9個位置并沒有添加元素。當(dāng)我們進(jìn)行序列化時，并不會只序列化其中一個元素，而是將整個數(shù)組進(jìn)行序列化操作，那些沒有被元素填充的位置也進(jìn)行了序列化操作，間接的浪費了磁盤的空間，以及程序的性能。
所以，ArrayList才會在elementData屬性前加上transient修飾符。
接下來，我們來看下ArrayList的writeObject()、readObject()
//序列化寫入：
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
int expectedModCount = modCount;
s.defaultWriteObject();
s.writeInt(size);
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
// 序列化讀?。?
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
s.defaultReadObject();
s.readInt();
if (size > 0) {
ensureCapacityInternal(size);
Object[] a = elementData;
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
1，ArrayList在序列化時會調(diào)用writeObject()，直接將elementData寫入ObjectOutputStream。
2，反序列化時則調(diào)用readObject()，從ObjectInputStream獲取elementData。
Arrays.copyOf() 數(shù)組擴(kuò)容
該方法在內(nèi)部創(chuàng)建了一個新數(shù)組，底層實現(xiàn)是調(diào)用System.arraycopy()。
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
original - 要復(fù)制的數(shù)組
newLength - 要返回的副本的長度
newType - 要返回的副本的類型
System.arraycopy()
該方法是用了native關(guān)鍵字，調(diào)用的為C++編寫的底層函數(shù)。
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
src - 源數(shù)組。
srcPos - 源數(shù)組中的起始位置。
dest - 目標(biāo)數(shù)組。
destPos - 目標(biāo)數(shù)據(jù)中的起始位置。
length - 要復(fù)制的數(shù)組元素的數(shù)量。
6，LinkedList源碼分析
看到網(wǎng)上都說LinkedList是一個環(huán)形鏈表結(jié)構(gòu)，頭尾相連。但，當(dāng)我開始看源碼的時候，發(fā)現(xiàn)并不是環(huán)形鏈表，是一個直線型鏈表結(jié)構(gòu)，我一度以為是我理解有誤。后來發(fā)現(xiàn)，JDK1.7之前的版本是環(huán)形鏈表，而到了JDK1.7以后進(jìn)行了優(yōu)化，變成了直線型鏈表結(jié)構(gòu)。
集合基礎(chǔ)結(jié)構(gòu)
1，在LinkedList中，內(nèi)部類Node對象最為重要，它組成了LinkedList集合的整個鏈表，分別指向上一個點、下一個結(jié)點，存儲著集合中的元素。
2，成員變量中，first表明是頭結(jié)點，last表明是尾結(jié)點。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
//LinkedList的元素個數(shù)：
transient int size = 0;
//LinkedList的頭結(jié)點：Node內(nèi)部類
transient java.util.LinkedList.Node<E> first;
//LinkedList尾結(jié)點：Node內(nèi)部類
transient java.util.LinkedList.Node<E> last;
//空實現(xiàn)：頭尾結(jié)點均為null，鏈表不存在
public LinkedList() {
}
//調(diào)用添加方法：
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
//節(jié)點的數(shù)據(jù)結(jié)構(gòu)，包含前后節(jié)點的引用和當(dāng)前節(jié)點
private static class Node<E> {
//結(jié)點元素：
E item;
//結(jié)點后指針
java.util.LinkedList.Node<E> next;
//結(jié)點前指針
java.util.LinkedList.Node<E> prev;
Node(java.util.LinkedList.Node<E> prev, E element, java.util.LinkedList.Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
add() 添加
LinkedList的添加方法，主要分為2種，一是直接添加一個元素，二是在指定角標(biāo)下添加一個元素。
（1）add(E e)底層調(diào)用linkLast(E e)方法，就是在鏈表的最后面插入一個元素。
（2）add(int index, E element)，插入的角標(biāo)如果==size，則插入到鏈表最后；否則，按照角標(biāo)大小插入到對應(yīng)位置。
//添加元素：添加到最后一個結(jié)點；
public boolean add(E e) {
linkLast(e);
return true;
}
//last節(jié)點插入新元素：
void linkLast(E e) {
//將尾結(jié)點賦值個體L:
final java.util.LinkedList.Node<E> l = last;
//創(chuàng)建新的結(jié)點，將新節(jié)點的前指針指向l:
final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(l, e, null);
//新節(jié)點置為尾結(jié)點：
last = newNode;
//如果尾結(jié)點l為null：則是空集合新插入
if (l == null)
//頭結(jié)點也置為 新節(jié)點：
first = newNode;
else
//l節(jié)點的后指針指向新節(jié)點：
l.next = newNode;
//長度+1
size++;
//操作數(shù)+1
modCount++;
}
//向?qū)?yīng)角標(biāo)添加元素：
public void add(int index, E element) {
//檢查傳入的角標(biāo) 是否正確：
checkPositionIndex(index);
//如果插入角標(biāo)==集合長度，則插入到集合的最后面：
if (index == size)
linkLast(element);
else
//插入到對應(yīng)角標(biāo)的位置：獲取此角標(biāo)下的元素先
linkBefore(element, node(index));
}
//在succ前插入 新元素e：
void linkBefore(E e, java.util.LinkedList.Node<E> succ) {
//獲取被插入元素succ的前指針元素：
final java.util.LinkedList.Node<E> pred = succ.prev;
//創(chuàng)建新增元素節(jié)點，前指針 和 后指針分別指向?qū)?yīng)元素：
final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, succ);
succ.prev = newNode;
//succ的前指針元素可能為null，為null的話說明succ是頭結(jié)點，則把新建立的結(jié)點置為頭結(jié)點：
if (pred == null)
first = newNode;
else
//succ前指針不為null，則將前指針的結(jié)點的后指針指向新節(jié)點：
pred.next = newNode;
//長度+1
size++;
//操作數(shù)+1
modCount++;
}
對于LinkedList集合增加元素來說，可以簡單的概括為以下幾點：
1，將添加的元素轉(zhuǎn)換為LinkedList的Node對象節(jié)點。
2，增加該Node節(jié)點的前后引用，即該Node節(jié)點的prev、next屬性，讓其分別指向哪一個節(jié)點）。
3，修改該Node節(jié)點的前后Node節(jié)點中pre/next屬性，使其指向該節(jié)點。
remove() 刪除元素
LinkedList的刪除也提供了2種形式，其一是通過角標(biāo)刪除元素，其二就是通過對象刪除元素；不過，無論哪種刪除，最終調(diào)用的都是unlink來實現(xiàn)的。
//刪除對應(yīng)角標(biāo)的元素：
public E remove(int index) {
checkElementIndex(index);
//node()方法通過角標(biāo)獲取對應(yīng)的元素，在后面介紹
return unlink(node(index));
}
//刪除LinkedList中的元素，可以刪除為null的元素，逐個遍歷LinkedList的元素，重復(fù)元素只刪除第一個：
public boolean remove(Object o) {
//如果刪除元素為null：
if (o == null) {
for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
//如果刪除元素不為null：
for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//移除LinkedList結(jié)點：remove()方法中調(diào)用
E unlink(java.util.LinkedList.Node<E> x) {
//獲取被刪除結(jié)點的元素E：
final E element = x.item;
//獲取被刪除元素的后指針結(jié)點：
final java.util.LinkedList.Node<E> next = x.next;
//獲取被刪除元素的前指針結(jié)點：
final java.util.LinkedList.Node<E> prev = x.prev;
//被刪除結(jié)點的 前結(jié)點為null的話：
if (prev == null) {
//將后指針指向的結(jié)點置為頭結(jié)點
first = next;
} else {
//前置結(jié)點的 尾結(jié)點指向被刪除的next結(jié)點；
prev.next = next;
//被刪除結(jié)點前指針置為null:
x.prev = null;
}
//對尾結(jié)點同樣處理：
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
set() 修改元素
1，LinkedList的set(int index, E element)方法與add(int index,E element)的設(shè)計思路基本一致，都是創(chuàng)建新Node節(jié)點，插入到對應(yīng)的角標(biāo)下，修改前后節(jié)點的prev、next屬性。
2，其中，node(int index)方法至關(guān)重要，通過對應(yīng)角標(biāo)獲取到對應(yīng)的集合元素。
3，可以看到，node（）中是根據(jù)角標(biāo)的大小是選擇從前遍歷還是從后遍歷整個集合。也可以間接的說明，LinkedList在隨機獲取元素時性能很低，每次的獲取都得從頭或者從尾遍歷半個集合。
//設(shè)置對應(yīng)角標(biāo)的元素：
public E set(int index, E element) {
checkElementIndex(index);
//通過node()方法，獲取到對應(yīng)角標(biāo)的元素：
java.util.LinkedList.Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
//獲取對應(yīng)角標(biāo)所屬于的結(jié)點：
java.util.LinkedList.Node<E> node(int index) {
//位運算：如果位置索引小于列表長度的一半，則從頭開始遍歷；否則，從后開始遍歷；
if (index < (size >> 1)) {
java.util.LinkedList.Node<E> x = first;
//從頭結(jié)點開始遍歷：遍歷的長度就是index的長度，獲取對應(yīng)的index的元素
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//從集合尾結(jié)點遍歷：
java.util.LinkedList.Node<E> x = last;
//同樣道理：
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
get() 獲取元素
get(int index)
在通過node(int index)獲取到對應(yīng)節(jié)點后，返回節(jié)點中的item屬性，該屬性就是我們所保存的元素。
//獲取相應(yīng)角標(biāo)的元素：
public E get(int index) {
//檢查角標(biāo)是否正確：
checkElementIndex(index);
//獲取角標(biāo)所屬結(jié)點的 元素值：
return node(index).item;
}
迭代器
在LinkedList中，并沒有自己實現(xiàn)iterator()方法，而是使用其父類AbstractSequentialList的iterator()方法。
List<String> linkedList = new LinkedList<String>(); Iterator<String> iterator = linkedList.iterator();
父類AbstractSequentialList中的 iterator():
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
public Iterator<E> iterator() {
return listIterator();
}
}
父類AbstractList中的 listIterator()：
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
public ListIterator<E> listIterator() {
return listIterator(0);
}
}
LinkedList中的 listIterator()：
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {}
7，小結(jié)
到此這篇關(guān)于Java中List集合的文章就介紹到這了,更多相關(guān)Java List集合介紹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
源碼閱讀之storm操作zookeeper-cluster.clj
這篇文章主要介紹了源碼閱讀之storm操作zookeeper-cluster.clj的相關(guān)內(nèi)容，對其源碼進(jìn)行了簡要分析，具有參考意義，需要的朋友可以了解下。2017-10-10
這篇文章主要介紹Java選擇排序和垃圾回收機制，創(chuàng)建對象就會占據(jù)內(nèi)存，如果程序在執(zhí)行過程中不能再使用某個對象，這個對象是徒耗內(nèi)存的垃圾，下面來看看文章具體內(nèi)容吧2021-10-10
SpringBoot使用jasypt加解密密碼的實現(xiàn)方法(二)
這篇文章主要介紹了SpringBoot使用jasypt加解密密碼的實現(xiàn)方法(二),本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-10-10
本篇文章主要介紹了淺談Java中的高精度整數(shù)和高精度小數(shù)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
Java如何將Excel數(shù)據(jù)導(dǎo)入到數(shù)據(jù)庫
這篇文章主要為大家詳細(xì)介紹了Java將Excel數(shù)據(jù)導(dǎo)入到數(shù)據(jù)庫的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
這篇文章主要為大家介紹了Flowable 設(shè)置流程變量的四種方式詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
詳細(xì)分析java并發(fā)之volatile關(guān)鍵字
這篇文章主要介紹了java并發(fā)之volatile關(guān)鍵字的的相關(guān)資料，文中代碼非常詳細(xì)，幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-06-06
Jdk11使用HttpClient提交Http2請求的實現(xiàn)方法
這篇文章主要介紹了Jdk11使用HttpClient提交Http2請求的實現(xiàn)方法，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2022-08-08
這篇文章主要介紹了java判讀數(shù)組中是否有重復(fù)值的示例,需要的朋友可以參考下2014-04-04
Spring的依賴注入的最大亮點是所有的Bean對Spring容器的存在是沒有意識的，我們可以將Spring容器換成其他的容器，Spring容器中的Bean的耦合度因此也是極低的,本文重點給大家介紹spring中的Aware接口，感興趣的朋友一起看看吧2022-02-02