溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹“ArrayList和LinkedList源碼是什么”，在日常操作中，相信很多人在ArrayList和LinkedList源碼是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”ArrayList和LinkedList源碼是什么”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！
在java中，集合這一數(shù)據(jù)結(jié)構(gòu)應(yīng)用廣泛，應(yīng)用最多的莫過于List接口下面的ArrayList和LinkedList;
我們先說List,
1 public interface List<E> extends Collection<E> {
2 //返回list集合中元素的數(shù)量，若數(shù)量大于Integer.MAX_VALUE,則返回Integer.MAX_VALUE
3 int size();
4
5 //判讀集合內(nèi)是否沒有元素，若沒有元素返回true
6 boolean isEmpty();
7
8 //判斷集合內(nèi)是否包含指定的元素o
9 boolean contains(Object o);
10
11 //以適當(dāng)?shù)男蛄?，返回該集合元素中的一個迭代器12 Iterator<E> iterator();
13
14 //返回一個數(shù)組，該數(shù)組包含該集合中所有的元素（以從first到last的順序）15 Object[] toArray();
16
17 //把集合中的元素放到數(shù)組a中，并返回18 <T> T[] toArray(T[] a);
19
20
21 //向集合末尾中添加一個元素22 boolean add(E e);
23
24 //從集合中刪除第一個出現(xiàn)的元素o25 boolean remove(Object o);
26
27
28 //判斷集合中是否包含 指定集合c中的所有元素29 boolean containsAll(Collection<?> c);
30
31 //將指定集合c中的所有元素都追加到 集合的末尾32 boolean addAll(Collection<? extends E> c);
33
34 //將指定集合c中的所有元素都插入到 集合中，插入的開始位置為index35 boolean addAll(int index, Collection<? extends E> c);
36
37 //將指定集合c中的所有元素從本集合中刪除38 boolean removeAll(Collection<?> c);
39
40 //本集合和 集合c的交集41 boolean retainAll(Collection<?> c);
42
43 //清除集合中的元素44 void clear();
45
46 //比較指定對象o和本集合是否相等，只有指定對象為list,size大小和本集合size一樣，且每個元素equal一樣的情況下，才返回true47 boolean equals(Object o);
48
49
50 int hashCode();
51
52 //返回指定位置index的元素53 E get(int index);
54
55 //將元素element設(shè)置到集合的index位置(替換)56 E set(int index, E element);
57
58 //將元素element插入到集合的index位置59 void add(int index, E element);
60
61 //移除指定位置index的元素62 E remove(int index);
63
64 //返回指定對象o在本集合中的第一個索引位置65 int indexOf(Object o);
66
67 //返回指定對象o在本集合中的最后一個索引位置68 int lastIndexOf(Object o);
69
70 //返回一個ListIterator的迭代器71 ListIterator<E> listIterator();
72
73 //從指定位置index開始返回一個ListInterator迭代器74 ListIterator<E> listIterator(int index);
75
76 //返回從位置fromIndex開始到位置toIndex結(jié)束的子集合77 List<E> subList(int fromIndex, int toIndex);
78 }下面我們看一看ArrayList，ArrayList是基于數(shù)組的方式來實(shí)現(xiàn)數(shù)據(jù)的增加、刪除、修改、搜索的。
ArrayList內(nèi)部維護(hù)者兩個變量：
//該數(shù)組緩存者集合中的元素，集合的容量就是該數(shù)組的長度，elementData用transient修飾，說明在序列化時，數(shù)組elementData不在序列化范圍內(nèi)。private transient Object[] elementData;//集合的大小 （集合中元素的數(shù)量）private int size;
我們再看一看ArrayList的構(gòu)造器：
ArrayList( initialCapacity) { ();
if (initialCapacity < 0) IllegalArgumentException("Illegal Capacity: "+
initialCapacity); .elementData = new Object[initialCapacity];
} ArrayList() { (10);
}
ArrayList(Collection<? E> c) {
elementData = c.toArray();
size = elementData.length;
(elementData.getClass() != Object[].)
elementData = Arrays.copyOf(elementData, size, Object[].);
}從上面的源碼中我們看到，先將c.toArray()方法的返回值賦值給elementData,將elementData.length賦值給size, 然后進(jìn)行了一個判斷 if(elementData.getClass() != Object[].class),若為真，則調(diào)用Arrays.copyOf（）方法創(chuàng)建一個新Object[]數(shù)組，將原來elementData中的元素copy到新建的Object[]數(shù)組中，最后將新建的數(shù)組賦值給elementData。
我們看一下Arrays.copyOf()方法的源碼：
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;
}如果newType類型為Object[].class的話，則直接創(chuàng)建一個長度為newLength的Object數(shù)組，否則使用Array.newInstance(Class<?> componentType, int length)方法創(chuàng)建一個元素類型為newType.getComponentType() （該方法返回數(shù)組中元素的類型）類型的，長度為newLength的數(shù)組，這是一個native方法，然后使用System.arraycopy() 這個native方法將original數(shù)組中的元素copy到新創(chuàng)建的數(shù)組中，并返回該數(shù)組。
我們注意 c.toArray might (incorrectly) not return Object[]，按理說一個c.toArray()返回的是一個Object[]類型，其getClass()返回的也一定是Object[].class,那為什么還要進(jìn)行逐個判斷呢？ 可真實(shí)情況真的是這樣嗎？我們看下面的示例：
//定義一個父類Animalpublic class Aniaml {
}//定義Animal的子類Personpublic class Person extends Aniaml{ private int id; private String name; private Date birthday; public Person(int id, String name, Date birthday) { this.id = id; this.name = name; this.birthday = birthday;
} public static void main(String[] args) {
test1();
test2();
test3();
} public static void test1(){
Person[] persons = {new Person(100,"lewis",new Date()),new Person(100,"lewis",new Date())}; //class [Lcom.lewis.guava.Person; Person的數(shù)組類型
System.out.println(persons.getClass());
Aniaml[] aniamls = persons; //class [Lcom.lewis.guava.Person; Person的數(shù)組類型
System.out.println(aniamls.getClass()); //class com.lewis.guava.Person Person類型
System.out.println(aniamls[0].getClass()); //java.lang.ArrayStoreException animals[]數(shù)組中實(shí)際存儲的是Peron類型，當(dāng)運(yùn)行時放入非Person類型時會報錯ArrayStoreException
aniamls[0] = new Aniaml();
} public static void test2(){
List<String> list = Arrays.asList("abc"); //class java.util.Arrays$ArrayList 由此可見該類型不是ArrayList類型
System.out.println(list.getClass());
Object[] objects = list.toArray(); //class [Ljava.lang.String; 返回的是String數(shù)組類型
System.out.println(objects.getClass()); //java.lang.ArrayStoreException: java.lang.Object 當(dāng)我們將一個Object放入String數(shù)組時報錯ArrayStoreException
objects[0] = new Object();
} public static void test3(){
List<String> dataList = new ArrayList<String>();
dataList.add("");
dataList.add("hehe");
//class java.util.ArrayList
System.out.println(dataList.getClass());
Object[] objects1 = dataList.toArray();
//class [Ljava.lang.Object;
System.out.println(objects1.getClass());
objects1[0]="adf";
objects1[0]=123;
objects1[0]=new Object();
}
}我們由上面test2()方法可知，一個List,調(diào)用list.toArray()返回的Object數(shù)組的真實(shí)類型不一定是Object數(shù)組（[Ljava.lang.Object;），當(dāng)我們調(diào)用 Object[] objArray = collection.toArray(), objArray并不一定能夠存放Object對象，所以上面的源碼中對這種情況進(jìn)行了判斷。
我們接著看ArrayList中的方法：
add(E),當(dāng)我們添加數(shù)據(jù)的時候，會遇到的一個問題就是：當(dāng)里面的數(shù)組滿了，沒有可用的容量的怎么辦？
add(E e) {
ensureCapacity(size + 1); // Increments modCount!!
elementData[size++] = e; true;
}
ensureCapacity( minCapacity) {
modCount++; oldCapacity = elementData.length; (minCapacity > oldCapacity) {
Object oldData[] = elementData; newCapacity = (oldCapacity * 3)/2 + 1; (newCapacity < minCapacity)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}
} add( index, E element) { (index > size || index < 0) IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
} E set( index, E element) {
RangeCheck(index);
E oldValue = (E) elementData[index];
elementData[index] = element; oldValue;
} RangeCheck( index) { (index >= size) IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
} addAll(Collection<? E> c) {
Object[] a = c.toArray(); numNew = a.length;
ensureCapacity(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
numNew != 0;
}我們再看刪除的方法
remove(Object o) { (o == null) {
for ( index = 0; index < size; index++) (elementData[index] == null) {
fastRemove(index); true;
}
} { ( index = 0; index < size; index++) (o.equals(elementData[index])) {
fastRemove(index); true;
}
} false;
} fastRemove( index) {
modCount++; numMoved = size - index - 1; (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
} E remove( index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index]; numMoved = size - index - 1; (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}元素的搜索：
/**
*獲取指定下標(biāo)index處的元素，先進(jìn)行邊界檢查，然后直接返回elementData數(shù)組中對應(yīng)位置index處的元素。
*/public E get(int index) {
RangeCheck(index); return (E) elementData[index];
} contains(Object o) { indexOf(o) >= 0;
}
indexOf(Object o) { (o == null) { ( i = 0; i < size; i++) (elementData[i]==null)
return i;
} { ( i = 0; i < size; i++) (o.equals(elementData[i]))
return i;
} -1;
}與indexOf(Object o)方法類似的是 lastIndexOf(Object o)方法，不同的是 后者返回的是最后一次出現(xiàn)指定元素o的位置下標(biāo)。
public int lastIndexOf(Object o) { if (o == null) { for (int i = size-1; i >= 0; i--) if (elementData[i]==null)
return i;
} else { for (int i = size-1; i >= 0; i--) if (o.equals(elementData[i]))
return i;
} return -1;
}我們再看一下ArrayList的迭代器方法如何實(shí)現(xiàn)的：
/**
*該方法是有ArrayList的父類AbstractList持有的，返回的是一個Itr對象
*/public Iterator<E> iterator() { return new Itr();
}我們看看Itr是個什么鬼：
Itr implements Iterator<E> {
cursor = 0; lastRet = -1; expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();
}
on,若modcount ！= expectedModCount，則拋出ConcurrentModificationException
E next() {
checkForComodification(); {
E next = get(cursor);
lastRet = cursor++;
return next;
} (IndexOutOfBoundsException e) {
checkForComodification(); NoSuchElementException();
}
} remove() { (lastRet == -1) IllegalStateException();
checkForComodification(); {
AbstractList.this.remove(lastRet); (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} (IndexOutOfBoundsException e) { ConcurrentModificationException();
}
}
checkForComodification() { (modCount != expectedModCount) ConcurrentModificationException();
}
}我們在看一個方法trimToSize
/**
*將elementData數(shù)組的容量 縮小為該集合實(shí)際包含的元素數(shù)量
*/public void trimToSize() {
modCount++; int oldCapacity = elementData.length; if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}使用ArrayList的注意事項(xiàng)：
1.ArrayList是基于數(shù)組的方式實(shí)現(xiàn)的,可以通過下標(biāo)索引直接查找到指定位置的元素，因此查找效率高，但每次插入或刪除元素，就要大量地移動元素，插入刪除元素的效率低。
2.ArrayList在插入元素時，可能會進(jìn)行數(shù)組的擴(kuò)容，但是在刪除元素時卻不會減小數(shù)組的容量，如果希望減小數(shù)組的容量，可使用trimToSize方法，在查找元素要遍歷數(shù)組時，對非 null元素使用equals方法，對null元素使用==。
3.擴(kuò)充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1個，也可能是一組）時，都要調(diào)用該方法來確保足夠的容量。當(dāng) 容量不足以容納當(dāng)前的元素個數(shù)時，就設(shè)置 新的容量為舊的容量的1.5倍加1，如果設(shè)置后的新容量還不夠，則直接新容量設(shè)置為傳入的參數(shù)（也就是所需的容 量），而后用Arrays.copyof()方法將元素拷貝到新的數(shù)組。從中 可以看出，當(dāng)容量不夠時，每次增加元素，都要將原來的元 素拷貝到一個新的數(shù)組中，非常之耗時，也因此建議在事先能確定元素數(shù)量的情況下，才使用ArrayList，否則建議使用 LinkedList
4.ArrayList不是線程安全的。
接著我們看下LinkedList，LinkedList是基于雙向鏈表的方式來實(shí)現(xiàn)的，雙向鏈表就是集合中的每個元素都知道其前面的一個元素的位置和它后的一個元素位置。
在LinkedList中，使用一個內(nèi)部類Entry來表示集合中的節(jié)點(diǎn)，元素的值賦值給element屬性，節(jié)點(diǎn)的next屬性指向下一個節(jié)點(diǎn)，節(jié)點(diǎn)的previous屬性指向前一個節(jié)點(diǎn)。
Entry<E> {
E element;
Entry<E> next;
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) { .element = element; .next = next; .previous = previous;
}
}/**
*維護(hù)了一個header節(jié)點(diǎn)，header節(jié)點(diǎn)的element屬性為null,previouse屬性為null，next屬性為null，并且header節(jié)點(diǎn)是不存儲數(shù)據(jù)的
*/private transient Entry<E> header = new Entry<E>(null, null, null);//size表示集合包含的元素個數(shù)private transient int size = 0;/**
* 構(gòu)造一個空的集合,將header節(jié)點(diǎn)的next屬性、previous屬性都指向header節(jié)點(diǎn)，這樣形成了一個雙向鏈表的閉環(huán)
*/public LinkedList() {
header.next = header.previous = header;
}新增操作
/**
*追加指定的元素e到集合尾部，其效果和方法 addLast(E e)是一致的，都是調(diào)用addBefore(e,header)方法。
*/public boolean add(E e) {
addBefore(e, header); return true;
}/**
*將數(shù)據(jù)e 插入到元素entry前面（private級別，LinkedList內(nèi)部調(diào)用，意味著不能直接在自己的應(yīng)用程序中調(diào)用此方法，但是可以利用反射API來間接的調(diào)用（好想沒必要這樣做））
*/private Entry<E> addBefore(E e, Entry<E> entry) { //創(chuàng)建一個新節(jié)點(diǎn)newEntry,newEntry.element屬性設(shè)置為e,newEntry.next屬性設(shè)置為entry，newEntry.previous屬性設(shè)置為entry.previous
Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); ///將newEntry.previous節(jié)點(diǎn)的next屬性指向newEntry本身
newEntry.previous.next = newEntry; //將newEntry.next節(jié)點(diǎn)的previous屬性指向newEntry本身
newEntry.next.previous = newEntry; //將集合大小size + 1
size++; //集合大小影響次數(shù)modCount + 1
modCount++;
//返回新創(chuàng)建的節(jié)點(diǎn)
return newEntry;
}下面我們看一下新增一個節(jié)點(diǎn)，在集合中的直接視圖情況：
假設(shè)我們一開始創(chuàng)建一個LinkedList時，只有一個header節(jié)點(diǎn)（不存儲數(shù)據(jù)的），如下圖所示：
有一個元素A1插入到了header的前面。
現(xiàn)在要插入一個元素A2,在執(zhí)行完下面代碼后，
Entry<E> newEntry = new Entry<E>(A2, header, header.previous); //將newEntry的next屬性指向header節(jié)點(diǎn)，newEntry.previous屬性指向header.previous指向的節(jié)點(diǎn)（A1）；
newEntry.previous.next = newEntry; //將newEntry.previous節(jié)點(diǎn)（A1）的next屬性指向newEntry,即將A1.previous屬性指向A2。
newEntry.next.previous = newEntry;//將newEntry.next節(jié)點(diǎn)（header）的previous屬性指向newEntry,即將header.previous屬性指向A2.
圖形變成了下面的樣子：
我們看一下LinkedList的一個帶參的構(gòu)造函數(shù)：
/**
*以指定集合c的迭代器返回的節(jié)點(diǎn)順序，構(gòu)造一個包含指定集合c中所有元素的集合
*/public LinkedList(Collection<? extends E> c) { //這里this()調(diào)用了LinkedList的無參構(gòu)造器，使header.next=header.previous=header，即此時僅有一個header節(jié)點(diǎn)
this(); //調(diào)用addAll(c)方法
addAll(c);
}/**
*將指定集合c中所有的元素，按照其迭代器返回的順序全部追加到集合的結(jié)尾。
*/public boolean addAll(Collection<? extends E> c) { return addAll(size, c);
}/**
*將指定集合c中所有的元素，按照其迭代器返回的順序，從指定的位置index開始全部插入到集合中。
*/public boolean addAll(int index, Collection<? extends E> c) { //對參數(shù)index做邊界檢查，無效拋出IndexOutOfBoundsException
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size); //將集合c 轉(zhuǎn)換為數(shù)組
Object[] a = c.toArray(); //獲取數(shù)組的長度
int numNew = a.length; //若數(shù)組的長度為0，說明數(shù)組是空的，沒有可以插入的元素，則直接返回false
if (numNew==0)
return false; //程序走到這，說明有可以插入的數(shù)據(jù)了，集合大小肯定會改變，因此modCount+1
modCount++; //如果入?yún)ndex==size,則將header節(jié)點(diǎn)設(shè)置為后繼節(jié)點(diǎn)successor,否則調(diào)用entry(int)方法求出位置index的節(jié)點(diǎn)，并將該節(jié)點(diǎn)設(shè)置為后繼節(jié)點(diǎn)successor.
Entry<E> successor = (index==size ? header : entry(index)); //獲取后繼節(jié)點(diǎn)successor的前驅(qū)節(jié)點(diǎn)predecessor
Entry<E> predecessor = successor.previous; //循環(huán)數(shù)組中的元素，進(jìn)入數(shù)據(jù)的插入
for (int i=0; i<numNew; i++) { //創(chuàng)建一個新節(jié)點(diǎn)e,將數(shù)組a的第i個元素a[i]作為新節(jié)點(diǎn)e的element屬性，successor作為e的next節(jié)點(diǎn)，predescessor作為e的previous節(jié)點(diǎn)
Entry<E> e = new Entry<E>((E)a[i], successor, predecessor); //將predecessor的next屬性指向新節(jié)點(diǎn)e
predecessor.next = e; //由于還要進(jìn)行后續(xù)的插入，因此將新節(jié)點(diǎn)e設(shè)置為前驅(qū)節(jié)點(diǎn)predecessor,以便繼續(xù)循環(huán)
predecessor = e;
} //在循環(huán)數(shù)組中的元素插入完成后，將sucessor.previous屬性指向predecessor節(jié)點(diǎn)，此時已經(jīng)完成了雙向鏈表的閉環(huán)了。
successor.previous = predecessor; //將集合大小size 增加numNew個
size += numNew; return true;
}/**
*返回指定位置index的節(jié)點(diǎn)
*/private Entry<E> entry(int index) { //對參數(shù)index做邊界檢查，無效拋出IndexOutOfBoundsException
if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size); //將頭結(jié)點(diǎn)header設(shè)置為e
Entry<E> e = header; //如果入?yún)ndex小于數(shù)組大小size的一半，即index< size/2的話，則從前往后查找（從下標(biāo)為0開始，到index），否則從后往前查找（從下標(biāo)為size開始，到index+1）
if (index < (size >> 1)) { for (int i = 0; i <= index; i++) //從前往后遍歷
e = e.next;
} else { for (int i = size; i > index; i--) //從后往前遍歷
e = e.previous;
} //找到后返回
return e;
}其他的添加操作：
/**
*追加指定元素e到集合的結(jié)尾，效果和調(diào)用add(E e)方法是一樣的（都是調(diào)用方法addBefore(e,header)），只是該方法沒返回值
*/public void addLast(E e) {
addBefore(e, header);
}/**
*將指定元素e插入到集合的開始位置，調(diào)用方法addBefore(e,header.next)實(shí)現(xiàn)
*/public void addFirst(E e) { //這里插入在header.next節(jié)點(diǎn)的前面，因此可以認(rèn)為是集合的開始位置
addBefore(e, header.next);
}/**
*在指定位置index處插入指定的元素e
*/public void add(int index, E element) { //若index== size,即要追加到集合的結(jié)尾處，即插入到header之前；否則調(diào)用entry(int)方法獲取index處的節(jié)點(diǎn)，插入到該節(jié)點(diǎn)之前
addBefore(element, (index==size ? header : entry(index)));
}/**
*將元素element設(shè)值到位置為index處（即將原index處的值替換為element）,并返回原來index處的值
*/public E set(int index, E element) {
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element; return oldVal;
}/**
*追加元素e到集合結(jié)尾
*/public boolean offer(E e) { return add(e);
}/**
*將元素e插入集合的開始位置，調(diào)用addFirst(E e)方法實(shí)現(xiàn)
*/public boolean offerFirst(E e) {
addFirst(e); return true;
}/**
*將元素e插入集合的結(jié)束位置，調(diào)用addLast(E e)方法實(shí)現(xiàn)
*/public boolean offerLast(E e) {
addLast(e); return true;
}/**
*將元素e推入（push）進(jìn)入棧 （LinkedList也可以當(dāng)做棧使用）
*/public void push(E e) {
addFirst(e);
}刪除操作：
/**
*刪除指定元素在集合中的第一個出現(xiàn)的節(jié)點(diǎn)（下標(biāo)index最小的）
*/public boolean remove(Object o) { //分為兩種情況：1.入?yún) 為null,使用== 比較 2.入?yún)不為null,使用equals比較
//若o == null
if (o==null) { //從前往后開始遍歷(從header節(jié)點(diǎn)的下一個節(jié)點(diǎn)開始）
for (Entry<E> e = header.next; e != header; e = e.next) { //使用 == 比較
if (e.element==null) { //找到第一個為null的節(jié)點(diǎn)，調(diào)用方法remove(Entry e)刪除該節(jié)點(diǎn)
remove(e); //返回true,表示刪除成功
return true;
}
}
} else { //從前往后開始遍歷(從header節(jié)點(diǎn)的下一個節(jié)點(diǎn)開始）
for (Entry<E> e = header.next; e != header; e = e.next) { //使用 equals 比較
if (o.equals(e.element)) { //找到第一個equals為true的節(jié)點(diǎn)，調(diào)用方法remove(Entry e)刪除該節(jié)點(diǎn)
remove(e); //返回true，表示刪除成功
return true;
}
}
} //返回false,表示沒有找到要刪除的元素o
return false;
}/**
*刪除指定的節(jié)點(diǎn)e(該方法是私有的，供LinkedList內(nèi)部調(diào)用,不對外提供),與ArrayList的刪除操作而言，LinkedList的刪除操作不需要進(jìn)行數(shù)組的移動，而是僅僅改變下被刪除元素的前后兩元素的指向而已，因此LinkedList刪除操作效率更高。
*/private E remove(Entry<E> e) { //判斷節(jié)點(diǎn)是否是頭結(jié)點(diǎn)header，我們知道header節(jié)點(diǎn)不存儲數(shù)據(jù)，若入?yún)被發(fā)現(xiàn)實(shí)header節(jié)點(diǎn)，則拋出NoSuchElementException異常。
if (e == header) throw new NoSuchElementException(); //獲取節(jié)點(diǎn)e的存儲的數(shù)據(jù)result
E result = e.element; //將節(jié)點(diǎn)e的前一個節(jié)點(diǎn)的next屬性直接指向e的下一個節(jié)點(diǎn)（斷開e.previous.next=e這個鏈條）
e.previous.next = e.next; //將節(jié)點(diǎn)e的下一個節(jié)點(diǎn)的previous屬性直接指向e的前一個節(jié)點(diǎn)（斷開e.next.previous=e這個鏈條）
e.next.previous = e.previous; //將e的next屬性和previous屬性都設(shè)置為null(斷開e對前一個節(jié)點(diǎn)和后一個節(jié)點(diǎn)的指向的鏈條)
e.next = e.previous = null; //將e的本身存儲的數(shù)據(jù)元素element置為null
e.element = null; //size 大小減一
size--; //由于remove操作影響了集合的結(jié)構(gòu)（大?。虼薽odCount+1
modCount++; //返回被刪除節(jié)點(diǎn)的存儲數(shù)據(jù)result
return result;
}清除集合中的所有節(jié)點(diǎn)clear()方法：
/**
*清除集合中所有的節(jié)點(diǎn)
*/public void clear() { //獲取header節(jié)點(diǎn)的下一個節(jié)點(diǎn)e
Entry<E> e = header.next; //只要遍歷一遍集合即可
while (e != header) { //e節(jié)點(diǎn)的下一個節(jié)點(diǎn)next
Entry<E> next = e.next; //將節(jié)點(diǎn)e的next屬性和previous屬性都設(shè)置為null（不指向任何節(jié)點(diǎn)）
e.next = e.previous = null; //將節(jié)點(diǎn)e的存儲數(shù)據(jù)元素置為null
e.element = null; //將next節(jié)點(diǎn)設(shè)置為當(dāng)前循環(huán)的節(jié)點(diǎn)e
e = next;
} //循環(huán)刪除了集合中的所有有數(shù)據(jù)的元素后，只保留header節(jié)點(diǎn)（不存儲數(shù)據(jù)），并組成一個閉環(huán)
header.next = header.previous = header; //由于清理了所有的元素，此時size 設(shè)置為0
size = 0; //此操作涉及到了集合結(jié)構(gòu)大小的改變，因此modCount + 1
modCount++;
}查找元素在集合中的下標(biāo)indexOf()方法和lastIndexOf()
/**
*返回元素o在集合中首次出現(xiàn)的位置下標(biāo)
*/public int indexOf(Object o) { //維護(hù)一個位置索引index用了記錄變量了多少個元素，從0開始
int index = 0; //若o == null,則使用 == 比較，從前往后
if (o==null) { for (Entry e = header.next; e != header; e = e.next) { if (e.element==null) //找到了第一個為null的，則返回其下標(biāo)index
return index; //在當(dāng)前循環(huán)中沒有找到，則將下標(biāo)index+1
index++;
}
} else { //若o不為 null,則使用 equals 比較，從前往后
for (Entry e = header.next; e != header; e = e.next) { if (o.equals(e.element)) //找到了第一個equals為truel的，則返回其下標(biāo)index
return index; //在當(dāng)前循環(huán)中沒有找到，則將下標(biāo)index+1
index++;
}
} //遍歷完整個鏈表沒有找到的話，返回-1
return -1;
}/**
*返回元素o在集合中最后出現(xiàn)的位置下標(biāo)
*/public int lastIndexOf(Object o) { //維護(hù)一個位置索引index用了記錄變量了多少個元素，從最大size開始
int index = size; //若o == null,則使用 == 比較，從后往前
if (o==null) { for (Entry e = header.previous; e != header; e = e.previous) { //先將index-1
index--; if (e.element==null) //找到了第一個遇見為null的，則返回其下標(biāo)index
return index;
}
} else { //若o != null,則使用 equals 比較，從后往前
for (Entry e = header.previous; e != header; e = e.previous) { //先將index-1
index--; if (o.equals(e.element)) //找到了第一個遇見equals為truel的，則返回其下標(biāo)index
return index;
}
} //在遍歷集合一遍之后，沒有找到元素的，返回-1
return -1;
}判斷集合是否包含某個元素：
/**
*判斷集合是否包含指定元素o,調(diào)用indexOf(Object o)來實(shí)現(xiàn)的
*/public boolean contains(Object o) { return indexOf(o) != -1;
}/**
*獲取指定位置index的元素，調(diào)用entry(int )來實(shí)現(xiàn)，entry(int)這個方法上面已講過
*/public E get(int index) { return entry(index).element;
}將集合轉(zhuǎn)換為數(shù)組：
Object[] toArray() {
Object[] result = Object[size];
int i = 0;
(Entry<E> e = header.next; e != header; e = e.next)
result[i++] = e.element;
result;
} <T> T[] toArray(T[] a) {
(a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size); i = 0;
Object[] result = a;
(Entry<E> e = header.next; e != header; e = e.next)
result[i++] = e.element;
(a.length > size)
a[size] = null;
a;
}LinkedList的迭代器：
/**
*返回一個list的迭代器，直接new了一個內(nèi)部類ListItr來實(shí)現(xiàn)的
*/public ListIterator<E> listIterator(int index) { return new ListItr(index);
}/**
*ListItr是LinkedList的私有內(nèi)部類，實(shí)現(xiàn)了ListIterator接口
*/private class ListItr implements ListIterator<E> { //將header設(shè)置為最近一次返回的節(jié)點(diǎn)
private Entry<E> lastReturned = header; //下一次要返回的節(jié)點(diǎn)
private Entry<E> next; //下次要返回節(jié)點(diǎn)的下標(biāo)
private int nextIndex; //將目前修改集合結(jié)構(gòu)大小的記錄數(shù)賦值給expectedModCount ，用于比較在一個線程遍歷集合時，是否有其他的線程在同步修改該集合結(jié)構(gòu)
private int expectedModCount = modCount;
//入?yún)閕nt的構(gòu)造函數(shù)
ListItr(int index) { //對入?yún)⑦M(jìn)行邊界檢查，如無效則拋出IndexOutOfBoundsException
if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+size); //若index < size/2,則從前往后遍歷nextIndex從0到index-1
if (index < (size >> 1)) { //將header節(jié)點(diǎn)的next屬性賦值給next，即下一次要返回的節(jié)點(diǎn)
next = header.next; //獲取指定位置的節(jié)點(diǎn)
for (nextIndex=0; nextIndex<index; nextIndex++)
next = next.next;
} else { //若index >= size/2，則從后往前遍歷nextIndex從size到index
next = header; //獲取指定位置的節(jié)點(diǎn)
for (nextIndex=size; nextIndex>index; nextIndex--)
next = next.previous;
}
} //根據(jù)nextIndex是否等于size來判斷是否還有沒有遍歷的節(jié)點(diǎn)
public boolean hasNext() { return nextIndex != size;
} //獲取下一個元素
public E next() { //檢查本集合在遍歷的過程中，是否有其他線程對本集合的結(jié)構(gòu)大小做了修改
checkForComodification(); //nextIndex == size,說明鏈表已經(jīng)被遍歷了一遍，不存在沒有被遍歷的節(jié)點(diǎn)了
if (nextIndex == size) throw new NoSuchElementException(); //將next節(jié)點(diǎn)設(shè)置為最近一次返回的節(jié)點(diǎn)
lastReturned = next; //將next節(jié)點(diǎn)往后移動一位
next = next.next; //將nextIndex+1
nextIndex++; //返回最近一次返回節(jié)點(diǎn)的數(shù)據(jù)元素
return lastReturned.element;
} //從后往前遍歷的過程中，判斷是否還有未被遍歷的元素 public boolean hasPrevious() { return nextIndex != 0;
} //獲取上一個元素
public E previous() { //若nextIndex==0,說明在從后往前遍歷（下邊從size 到 0）過程中，已經(jīng)遍歷到頭了，不存在沒有被遍歷的節(jié)點(diǎn)了，則拋出NoSuchElementException
if (nextIndex == 0) throw new NoSuchElementException(); //將next往前移動一位，并將next節(jié)點(diǎn)賦值給最近返回的節(jié)點(diǎn)lastReturned
lastReturned = next = next.previous; //將nextIndex-1
nextIndex--; //檢查本集合在遍歷的過程中，是否有其他線程對本集合的結(jié)構(gòu)大小做了修改
checkForComodification(); //返回最近一次返回節(jié)點(diǎn)的數(shù)據(jù)元素
return lastReturned.element;
} public int nextIndex() { return nextIndex;
} public int previousIndex() { return nextIndex-1;
} //移除當(dāng)前迭代器持有的節(jié)點(diǎn)
public void remove() {
checkForComodification();
Entry<E> lastNext = lastReturned.next; try {
LinkedList.this.remove(lastReturned);
} catch (NoSuchElementException e) { throw new IllegalStateException();
} if (next==lastReturned)
next = lastNext; else
nextIndex--;
lastReturned = header;
expectedModCount++;
} //將當(dāng)前迭代器持有的元素 替換為元素e
public void set(E e) { if (lastReturned == header) throw new IllegalStateException();
checkForComodification();
lastReturned.element = e;
} //在當(dāng)前節(jié)點(diǎn)后面插入元素e
public void add(E e) {
checkForComodification();
lastReturned = header;
addBefore(e, next);
nextIndex++;
expectedModCount++;
} //檢查本集合在遍歷的過程中，是否有其他線程對本集合的結(jié)構(gòu)大小做了修改，如果別的線程對集合做出了修改，則拋出ConcurrentModificationException
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException();
}
}/**
*接口ListIterator,繼承了迭代器接口Iterator
*/public interface ListIterator<E> extends Iterator<E> { //在遍歷集合時(按照從前往后的順序)，是否還存在沒有遍歷的元素
boolean hasNext(); //返回下一個元素
E next(); //在遍歷集合時(按照從后往前的順序)，是否還存在沒有遍歷的元素
boolean hasPrevious(); //返回上一個元素
E previous(); //返回下一個元素的位置下標(biāo)
int nextIndex(); //返回上一個元素的位置下標(biāo)
int previousIndex(); //刪除正在遍歷的元素
void remove(); //將正在遍歷的元素替換為 元素e
void set(E e); //插入元素e
void add(E e);
}使用LinkedList的注意事項(xiàng)：
1.LinkedList是基于雙向鏈表實(shí)現(xiàn)的。
2.LinkedList在插入元素時，必須創(chuàng)建Entry對象，并修改相應(yīng)元素的前后元素的引用；在查找元素時，必須遍歷鏈表；在刪除元素時，遍歷鏈表找到要刪除的元素，修改被刪除元素的前后元素的引用；
到此，關(guān)于“ArrayList和LinkedList源碼是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼