Java總結(jié) - List實(shí)現(xiàn)類ArrayList&LinkedList
來源：期待l 發(fā)布時間：2019-02-23 17:11:10 閱讀量：1092
本文是根據(jù)源碼進(jìn)行學(xué)習(xí)的,如果我有什么理解不對的地方請多指正,謝謝您
上面基本就是List集合類的類圖關(guān)系了,圖中省略掉了比如
Cloneable等標(biāo)記接口,那么List分別具體的主要實(shí)現(xiàn)類有:ArrayList,Vector,LinkedList,Stack,那么這篇文章會對這四個實(shí)現(xiàn)類進(jìn)行介紹(由于篇幅原因,本文只說到了ArrayList和LinkedList)
ArrayList
這是最常用的List的實(shí)現(xiàn)類,那么這個類的存儲是由數(shù)組實(shí)現(xiàn)的,如果超過數(shù)組規(guī)定閥值,那么就會進(jìn)行自動擴(kuò)容,自動擴(kuò)容其實(shí)就是將數(shù)組數(shù)據(jù)復(fù)制到一個新的更大的數(shù)組中以達(dá)到擴(kuò)容的目的,我們來看一下ArrayList的部分屬性源碼
//默認(rèn)容量,將在添加第一個元素時擴(kuò)展為 DEFAULT_CAPACITYprivate static final int DEFAULT_CAPACITY = 10;//共享空數(shù)組實(shí)例private static final Object[] EMPTY_ELEMENTDATA = {};//這是保存數(shù)據(jù)的數(shù)組,非私有以簡化嵌套類訪問//arraylist 的容量是此array數(shù)組的長度//當(dāng)?shù)谝粋€元素被添加時,當(dāng)任何一個空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都會被擴(kuò)展為DEFAULT_CAPACITYtransient Object[] elementData;//共享空數(shù)組實(shí)例，用于默認(rèn)大小的空實(shí)例//將其與 EMPTY_ELEMENTDATA 區(qū)分開來,以了解添加第一個元素時要增加多少private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};private int size; ...
初始化
ArrayList提供了三種構(gòu)造方法,如下
public ArrayList() {...}public ArrayList(int initialCapacity) {...}public ArrayList(Collection<? extends E> c) {...}空參 : 我們從第一個ArrayList的空參的構(gòu)造方法介紹,下面是源碼的實(shí)現(xiàn)
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }怎么理解之前的代碼注釋
當(dāng)?shù)谝粋€元素被添加時,任何一個空ArrayList的elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA都會被擴(kuò)展為DEFAULT_CAPACITY呢?ArrayList為空并且兩個屬性值相等的時候,說明是調(diào)用了無參構(gòu)造,在構(gòu)造執(zhí)行完的時候,并沒有被構(gòu)造為默認(rèn)大小,而是當(dāng)?shù)谝粋€元素添加時候,判斷的條件成立即兩屬性值相等,才會進(jìn)行擴(kuò)展為默認(rèn)大小所以說當(dāng)我們構(gòu)建空參對象的時候,初始值數(shù)組長度是為0的,并沒有直接擴(kuò)充為長度為10的數(shù)組,代碼驗(yàn)證
public static void main(String[] args) throws Exception { ArrayList<String> arrayList = new ArrayList<>(); getSize(arrayList); arrayList.add("x"); getSize(arrayList); }private static void getSize(ArrayList<String> arrayList) throws Exception { Field elementData = arrayList.getClass().getDeclaredField("elementData"); elementData.setAccessible(true); Object[] o = (Object[]) elementData.get(arrayList); System.out.println(o.length); }//0 10//而當(dāng)我們以0為初始化長度參數(shù)創(chuàng)建ArrayList的時候,其實(shí)就是告訴他我一個都不存,所以他就創(chuàng)建了一個0長度的數(shù)組,而當(dāng)我們添加數(shù)據(jù)的時候,就會自動擴(kuò)容一個//驗(yàn)證 : 可以將初始化改成這樣 ArrayList<String> arrayList = new ArrayList<>(0);//然后輸出為 0 1//所以這也就是為什么要區(qū)分DEFAULTCAPACITY_EMPTY_ELEMENTDATA 與 EMPTY_ELEMENTDATA從中我們可以看到,只是初始化空參的ArrayList的話,那么只是將一個空數(shù)組賦值給elementData屬性,那么
EMPTY_ELEMENTDATA也是空數(shù)組對象,他是用來干啥的呢?他只是用作是構(gòu)造有參空ArrayLIst的時候=0.而DEFAULTCAPACITY_EMPTY_ELEMENTDATA才是我們構(gòu)造空參ArrayList時候使用的對象,即這樣的,從下面一個分析另一個構(gòu)造的時候就能看出來//使用EMPTY_ELEMENTDATAList<String> arrayList = new ArrayList<>(0);//使用DEFAULTCAPACITY_EMPTY_ELEMENTDATAList<String> arrayList = new ArrayList<>();
我們還注意到
DEFAULTCAPACITY_EMPTY_ELEMENTDATA與EMPTY_ELEMENTDATA都是以private static final修飾,所以這兩個空數(shù)組是屬于類的,僅存在一份,說這個的意思就是,當(dāng)你創(chuàng)建兩個容量為0的ArrayList的時候,都會指向一個堆內(nèi)存中的對象,我們可以嘗試一下public static void main(String[] args) throws Exception { ArrayList<String> list1 = new ArrayList<>(); Field elementData1 = list1.getClass().getDeclaredField("elementData"); elementData1.setAccessible(true); Object o1 = elementData1.get(list1); ArrayList<String> list2 = new ArrayList<>(); Field elementData2 = list2.getClass().getDeclaredField("elementData"); elementData2.setAccessible(true); Object o2 = elementData1.get(list2); System.out.println(o1 == o2); } //true所以ArrayList其實(shí)已經(jīng)想好了為我們的空集合做一個緩存,而當(dāng)我們向空集合中添加數(shù)據(jù)的時候,elementData就會指向其他的對象,這個是add方法的源碼范圍,所以一會再說,到這第一個空參的構(gòu)造方法已經(jīng)介紹的差不多了,下面是有int類型參數(shù)的構(gòu)造方法的源碼實(shí)現(xiàn)
public ArrayList(int initialCapacity) { //不為0,按照指定長度創(chuàng)建數(shù)組 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //為0就直接指向創(chuàng)建好的數(shù)組 this.elementData = EMPTY_ELEMENTDATA; } else { //參數(shù)不合法 throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); } }不用細(xì)說,這個是很容易的,也可以看出來為什么ArrayList要設(shè)計(jì)兩個空數(shù)組以備使用,這個構(gòu)造沒什么可說的,那么下面就是以集合為參數(shù)的創(chuàng)建方式的源碼
//將參數(shù)轉(zhuǎn)換為ArrayListpublic ArrayList(Collection<? extends E> c) { //因?yàn)镃ollection中就定義了toArray方法,所以他的實(shí)現(xiàn)類就都會實(shí)現(xiàn)自己的toArray,所以可以直接調(diào)用返回?cái)?shù)組而不會出錯 elementData = c.toArray(); //如果返回的數(shù)組的長度不是空的數(shù)組的話 if ((size = elementData.length) != 0) { //防范c.ToArray錯誤不返回Object[] if (elementData.getClass() != Object[].class) //那么就將elementData中的元素都轉(zhuǎn)換為Object類型 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { //到這就是空數(shù)組,所以直接引用創(chuàng)建好的空數(shù)組即可,還能節(jié)省空間 this.elementData = EMPTY_ELEMENTDATA; } }到這ArrayList的創(chuàng)建方式大概的就過了一邊,那么下面的ArrayList的實(shí)現(xiàn)方法,我就只挑幾個核心方法來看一下源碼
add
首當(dāng)其沖的就是add,我們使用一下ArrayList來add元素,然后我們進(jìn)行代碼走讀,那么我們看一下源碼
//使用ArrayList<String> arrayList = new ArrayList<>(); arrayList.add("A");//源碼開始public boolean add(E e) { modCount++; //代表操作ArrayList的次數(shù),有關(guān)于fast-fail機(jī)制,之后再說 //參數(shù)值:并不是A參數(shù)是一個URL, 數(shù)組對象 , 2 add(e, elementData, size); //調(diào)用類中方法 return true; //返回結(jié)果} // 結(jié)束代碼上面可以說是很簡單了,但是在debug的時候我發(fā)現(xiàn)存儲元素的elementData數(shù)組中其實(shí)已經(jīng)有東西了,如下圖
然后當(dāng)我debug step over到結(jié)束代碼的時候,程序跳到這這樣一個代碼
public synchronized void addURL(URL url) { if (closed || url == null) return; synchronized (unopenedUrls) { if (! path.contains(url)) { unopenedUrls.addLast(url); path.add(url); } } }//再跳public InternalError(String message) { super(message); }//還跳static { System.loadLibrary("instrument"); }//還有很多...上面的一些代碼其實(shí)不用知道其意思,但是可以告訴我們的是,ArrayList中的elementData不單純是存儲我們需要存儲的元素的,而是在首次add的時候會借助elementData這個數(shù)組去加載一些文件或者其他東西,而在第二次add的時候就不需要這個步驟了,并且在首次加載完一些路徑后或者庫后,elementData就會將他們清除,以為已經(jīng)加載上了,然后這時候才會來存儲我們的元素,錄了一段小視頻,可以下載來看一下
經(jīng)過后面再次實(shí)驗(yàn), 除了首次使用ArrayList的add方法會加載一些東西,當(dāng)我們再次new出ArrayList的時候,首次使用add方法就不會再家在任何東西了,如下的測試代碼
List<String> list = new ArrayList<>(); list.add("X"); List<String> list2 = new ArrayList<>(); list2.add("X");其中在我debug時候會看到很多
getLoader`loders一些方法或者屬性,那么在這感覺是首次使用ArrayList的類加載機(jī)制在起作用,我在社區(qū)提問題了,所以大家可以看一下,聯(lián)想到類加載機(jī)制非常感謝回復(fù)我的1382148494135822`大哥, 問答頁 : 關(guān)于ArrayList的問題,請大佬進(jìn)來看看回到add方法上來,我們發(fā)現(xiàn)它會調(diào)用類中的另一個add方法.源碼如下
private void add(E e, Object[] elementData, int s) { //如果滿了就擴(kuò)容 if (s == elementData.length) elementData = grow(); //然后將要存的元素存入到數(shù)組指定位置 elementData[s] = e; //加一 size = s + 1; }這個方法中用到的grow方法源碼如下
private Object[] grow() { return grow(size + 1); }private Object[] grow(int minCapacity) { return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity)); }//返回至少與給定最小容量相同的容量private int newCapacity(int minCapacity) { int oldCapacity = elementData.length; //10+(10>>1)=15 ,即擴(kuò)容1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); //擴(kuò)容后如果還比最小的容量小或者相等的話 if (newCapacity - minCapacity <= 0) { //判斷是否是初始化的情況 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) //是的話就直接返回默認(rèn)容量10,從這就可以看出來才剛開始初始化大小 return Math.max(DEFAULT_CAPACITY, minCapacity); if (minCapacity < 0) // overflow錯誤,最小值不可能是負(fù)數(shù) throw new OutOfMemoryError(); //如果不是初始化也不是參數(shù)錯誤,那么就返回最小的容量 return minCapacity; } //到這表示擴(kuò)容后的容量比最小容量要大 //是否達(dá)到了最大長度,如果沒到達(dá)就返回?cái)U(kuò)容后的長度,否則就調(diào)用hugeCapacity return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity); }private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow錯誤 throw new OutOfMemoryError(); //如果達(dá)到了規(guī)定的最大數(shù)組長度,那么就擴(kuò)容到整數(shù)的最大長度,否則就是當(dāng)前默認(rèn)的數(shù)組最大長度 return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;還有一個指定位置的add方法,下面是源碼實(shí)現(xiàn)
public void add(int index, E element) { //檢查是否數(shù)組越界 rangeCheckForAdd(index); modCount++; final int s; //臨時保存size Object[] elementData; //臨時保存elementData if ((s = size) == (elementData = this.elementData).length) elementData = grow(); //如果長度等于size代表要擴(kuò)容了 //核心方法System.arraycopy,他會將你要操作的index地方的位置空出了 System.arraycopy(elementData, index, elementData, index + 1, s - index); //然后index空出來的位置賦值 elementData[index] = element; //加一 size = s + 1; }好了ArrayList的add方法已經(jīng)介紹完了,如果有不對的地方請指正
addAll
源碼實(shí)現(xiàn)
public boolean addAll(Collection<? extends E> c) { //轉(zhuǎn)換數(shù)組 Object[] a = c.toArray(); modCount++; //獲取傳入集合的長度 int numNew = a.length; //是空集合的話直接返回 if (numNew == 0) return false; Object[] elementData; final int s; //如果傳入集合的長度大于elementData中空余的位置個數(shù)就增長 if (numNew > (elementData = this.elementData).length - (s = size)) elementData = grow(s + numNew); //增長完了就將傳入的數(shù)據(jù)copy進(jìn)去 System.arraycopy(a, 0, elementData, s, numNew); //元素個數(shù)修改 size = s + numNew; //返回成功 return true; }
Get
源碼實(shí)現(xiàn)
public E get(int index) { //檢查index Objects.checkIndex(index, size); //然后調(diào)用方法 return elementData(index); }E elementData(int index) { //直接下標(biāo)取元素 return (E) elementData[index]; }很簡單就不說了
remove
源碼實(shí)現(xiàn)按照索引刪除
public E remove(int index) { //檢查index Objects.checkIndex(index, size); final Object[] es = elementData; //用于返回值 E oldValue = (E) es[index]; fastRemove(es, index); return oldValue; }private void fastRemove(Object[] es, int i) { modCount++; final int newSize; //去掉一個元素后的長度如果大于指定刪除的索引的位置 if ((newSize = size - 1) > i) //把刪除元素后面的元素往前挪一位 System.arraycopy(es, i + 1, es, i, newSize - i); //避免內(nèi)存泄露 es[size = newSize] = null; }源碼實(shí)現(xiàn)按照對象刪除
public boolean remove(Object o) { final Object[] es = elementData; final int size = this.size; int i = 0; //元素首次出現(xiàn)位置記錄 //尋找元素的邏輯 found: { if (o == null) { for (; i < size; i++) if (es[i] == null) break found; } else { for (; i < size; i++) if (o.equals(es[i])) break found; } //到這代表沒找到.返回false return false; } //找到了就按照下標(biāo)刪除 fastRemove(e s, i); return true; }
indexOf
源碼實(shí)現(xiàn)
public int indexOf(Object o) { return indexOfRange(o, 0, size); }int indexOfRange(Object o, int start, int end) { Object[] es = elementData; if (o == null) { for (int i = start; i < end; i++) { if (es[i] == null) { //尋找到首個想等元素的時候返回索引 return i; } } } else { for (int i = start; i < end; i++) { if (o.equals(es[i])) { //尋找到首個想等元素的時候返回索引 return i; } } } //未找到返回-1 return -1; }這個實(shí)現(xiàn)比較簡單,并且ArrayList的一些
*indexOf*類似的方法的大致思路都是如此的
writeObject
這是序列化的方法
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { //將操作次數(shù)記錄 int expectedModCount = modCount; //將類中的no-static和no-transient屬性寫到流中 s.defaultWriteObject(); s.writeInt(size); //依次寫出元素 for (int i=0; i<size; i++) { s.writeObject(elementData[i]); } //如果再次過程中數(shù)組中內(nèi)容遭到改變,序列化停止并且拋出異常 if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } }
readObject
這是反序列化的方法
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // 讀取大小和其他的內(nèi)容 s.defaultReadObject(); //讀取容量 s.readInt(); //如果讀取到size>0 if (size > 0) { // 與clone()一樣,根據(jù)大小而非容量分配數(shù)組 SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size); //創(chuàng)建存儲數(shù)組 Object[] elements = new Object[size]; //依次將數(shù)據(jù)讀出來并賦值 for (int i = 0; i < size; i++) { elements[i] = s.readObject(); } //然后賦值給本類的全局變量 elementData = elements; } else if (size == 0) { //size為0代表空集合,那么就直接使用常量替換 elementData = EMPTY_ELEMENTDATA; } else { //非法的,出異常 throw new java.io.InvalidObjectException("Invalid size: " + size); } }好了到這我自己認(rèn)為比較重要的方法源碼就都列出來的,所以將ArrayList的介紹就告一段落了,那么到這我就只有一個疑問就是關(guān)于elementData在首次add時加載jar或者路徑是做什么用的,如果您知道,請?jiān)u論在下面,非常謝謝您
總結(jié)一下ArrayList,我們在分析源碼的時候,除了在首次add時會添加路徑之類的信息會設(shè)計(jì)到其他類的同步加載方法,但是本類的方法并沒有涉及同步,所以ArrayList并不是線程安全的,并且他是懶加載的,首次默認(rèn)初始化并不會就初始化為初始化容量,而是在之后才會初始化為初始化容量,這個類的核心就是
System.arraycopy方法,所以以后我們在操作數(shù)組移動的時候,我們也可以使用這個native方法使得程序更加的快速準(zhǔn)確,在add和get的時候是相當(dāng)迅速而直接的,就是將制定位置元素后移并在此位置上插入元素,所以ArrayList的增加和查詢是很迅速的,但是我們也需要注意,當(dāng)ArrayList的元素滿的時候他是創(chuàng)建新數(shù)組進(jìn)行copy的,所以當(dāng)ArrayList的元素相當(dāng)大的時候,這無疑是一個恐怖的事情,所以ArrayList并不適合存儲很多元素
LinkedList
可以先參考一下這篇關(guān)于鏈表的文章,如果你有了解一點(diǎn)就可以不用看了 : 鏈表
這是一個鏈表實(shí)現(xiàn)的List的實(shí)現(xiàn)類,對于ArrayList這個類要并不存在擴(kuò)容copy的問題,如果你了解一點(diǎn)鏈表內(nèi)容就會知道,增加元素在鏈表中無非就是改變引用的事情,所以它并沒有這樣的問題,好了讓我們直接上源碼吧
依舊先看一下他的成員屬性
//元素個數(shù) transient int size = 0; //頭節(jié)點(diǎn) transient Node<E> first; //尾節(jié)點(diǎn) transient Node<E> last;
transient代表不會被序列化,那么Node是啥東西,看一下源碼
private static class Node<E> { E item; //本元素值 Node<E> next; //前元素指向 Node<E> prev; //后元素指向 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }從中可以LinkedList實(shí)現(xiàn)是一個雙鏈表,我們接下來看看他的初始化方法的實(shí)現(xiàn)
public LinkedList() { }空參構(gòu)造什么都沒做,接下來看其他的初始化方法
public LinkedList(Collection<? extends E> c) { this(); addAll(c); }那么這個有參的構(gòu)造方法其實(shí)主要邏輯是addAll方法,我暫時先不說這個方法,那么我們先來看看其他的核心實(shí)現(xiàn)方法
add
源碼如下
public boolean add(E e) { linkLast(e); //添加到鏈表最后面 return true; }void linkLast(E e) { //將最后一個元素引用保留 final Node<E> l = last; //創(chuàng)建一個新的元素根據(jù)傳入的add參數(shù),新的對象的前一個元素的引用 //就是之前的最后一個元素 final Node<E> newNode = new Node<>(l, e, null); //將最后的元素指針指向新元素 last = newNode; //如果之前的尾元素是空的代表是空鏈表, if (l == null) //即首尾都是此元素 first = newNode; else //就不是空鏈表,那么倒數(shù)第二個的元素的下一個元素就是新元素 l.next = newNode; size++; modCount++; }還有一種是根據(jù)index位置插入的
public void add(int index, E element) { //是否越界 checkPositionIndex(index); //如果index等于元素個數(shù) if (index == size) //那么就添加到尾部 linkLast(element); else //否則就按位置添加 //node方法,傳入index,返回指定元素索引處的（非空）節(jié)點(diǎn) linkBefore(element, node(index)); }void linkBefore(E e, Node<E> succ) { //已經(jīng)確保了succ不為空,在上面node方法中確保的 //取出指定index索引上的元素的前一個元素引用 final Node<E> pred = succ.prev; //創(chuàng)建新的元素,新元素的前一個元素就是目前指定index上的元素的前一個元素 //下一個元素是index上面的元素 final Node<E> newNode = new Node<>(pred, e, succ); //將指定索引位置的原元素的前指針指向新元素 succ.prev = newNode; //如果是在頭部添加,那么當(dāng)前元素的前一個元素肯定為空 if (pred == null) //然后新元素就成為了頭元素 first = newNode; else //否則就將index-1位置的元素的后指針指向新元素 pred.next = newNode; size++; modCount++; }如果你熟悉鏈表,那么上面的代碼就很簡單就能理解了,如果看不懂,可以自己畫一下圖,瞬間明白
addAll
這也是構(gòu)造中調(diào)用的方法,我們來看一下實(shí)現(xiàn)
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); }public boolean addAll(int index, Collection<? extends E> c) { //檢查位置是否越界 checkPositionIndex(index); //集合轉(zhuǎn)數(shù)組 Object[] a = c.toArray(); //確定集合元素個數(shù) int numNew = a.length; //如果是空集合返回 if (numNew == 0) return false; //記錄前指向和當(dāng)前節(jié)點(diǎn) Node<E> pred, succ; //如果相等代表在最后追加 if (index == size) { //在最后追加,就不需要當(dāng)前元素了,因?yàn)閘ast已經(jīng)指向了 succ = null; //添加集合的時候的,集合中首個被添加的元素的前一個節(jié)點(diǎn)就是當(dāng)前鏈表中的最后一個節(jié)點(diǎn) pred = last; } else { //到這就代表不是在尾部追加,而是將元素追加到鏈表中間位置 //node方法之前說過就是根據(jù)index來返回index位置上的節(jié)點(diǎn) //node返回節(jié)點(diǎn)后保存引用 succ = node(index); //記錄當(dāng)前index節(jié)點(diǎn)的前節(jié)點(diǎn)的引用 pred = succ.prev; //到這就記錄好了當(dāng)前節(jié)點(diǎn)和前節(jié)點(diǎn)的引用 } //開始循環(huán)創(chuàng)建集合中的元素的節(jié)點(diǎn)了,然后修改相關(guān)指向 for (Object o : a) { //將集合元素強(qiáng)轉(zhuǎn)一下,泛型約束不會classcast E e = (E) o; //創(chuàng)建節(jié)點(diǎn),此節(jié)點(diǎn)的前一個元素指向已經(jīng)確定 Node<E> newNode = new Node<>(pred, e, null); //代表從頭開始添加 if (pred == null) //新節(jié)點(diǎn)就是first節(jié)點(diǎn) first = newNode; else //新節(jié)點(diǎn)前指向是pred,perd.next指向新元素,所以到這形成了前元素和新元素的雙向鏈接 pred.next = newNode; //到這就連接好了舊節(jié)點(diǎn)和新節(jié)點(diǎn),需要移動pred指向,指向新節(jié)點(diǎn) //然后將新節(jié)點(diǎn)當(dāng)做舊節(jié)點(diǎn),然后在于新創(chuàng)建的節(jié)點(diǎn)做雙向鏈接 pred = newNode; } //到這就把鏈表從頭到集合所有元素都連接完成了,需要處理集合的尾節(jié)點(diǎn)和鏈表的原index節(jié)點(diǎn)的鏈接問題了 //如果原來的尾index節(jié)點(diǎn)沒有 if (succ == null) { //那么last就指向集合的尾節(jié)點(diǎn) last = pred; } else { //代表之前的鏈表有index節(jié)點(diǎn),那么就修改index節(jié)點(diǎn)和集合的尾節(jié)點(diǎn)的鏈接 pred.next = succ; succ.prev = pred; } //做一些計(jì)數(shù)操作 size += numNew; modCount++; return true; }到這其實(shí)add方法基本就解析完了,那么順便前面的構(gòu)造也就沒有問題了,下面是其他方法的源代碼
remove
remove()public E remove() { return removeFirst(); }//可以看到默認(rèn)從頭開始刪除public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); }private E unlinkFirst(Node<E> f) { // assert f == first && f != null; //取出頭元素屬性值 final E element = f.item; //取出頭元素的下一個元素的引用 final Node<E> next = f.next; //將頭元素的屬性值置空 f.item = null; f.next = null; // help GC //然后將first指針指向下一個元素 first = next; //如果存在就只有一個元素的情況 if (next == null) //first和last都是null last = null; else //否則就將原來頭節(jié)點(diǎn)的下一個節(jié)點(diǎn)的前引用取消,因?yàn)椴淮嬖诹?自己已經(jīng)變成了頭結(jié)點(diǎn) next.prev = null; size--; modCount++; return element; }remove(Object)public boolean remove(Object o) { //遍歷,邏輯比較簡單,就不一句代碼一句代碼的說了 if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //整體邏輯就是:已經(jīng)獲得了一個node,那么node的前后引用關(guān)系就找到了,然后剩下的就是改引用關(guān)系E unlink(Node<E> x) { // assert x != null; //取出元素的所有屬性值 final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; //如果前引用是null,就代表是頭元素 if (prev == null) { //頭指針,指向下一個元素 first = next; } else { //那么前引用就不是空的 //就將此元素的前元素的后指針指向此元素的后一個元素 prev.next = next; //此節(jié)點(diǎn)的前置引用可以取消了 x.prev = null; } //如果后置引用為空 if (next == null) { //代表是尾節(jié)點(diǎn),尾指針,指向前一個 last = prev; } else { //代表不是尾節(jié)點(diǎn),就將次元素的后一個元素的前引用指向次元素的前一個元素 next.prev = prev; //次元素的后置引用可以取消了 x.next = null; } //到這x節(jié)點(diǎn)已經(jīng)完全脫離鏈表,置空 x.item = null; size--; modCount++; return element; }removeFirst()public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); //方法實(shí)現(xiàn)上面已經(jīng)寫出了}removeLast()public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); // 跟之前的unlinkFirst類似就不再詳細(xì)說了}remove(int)public E remove(int index) { checkElementIndex(index); return unlink(node(index)); //實(shí)現(xiàn)有說明在前面}removeFirstOccurrence&removeLastOccurrence其源碼就不去實(shí)現(xiàn)了,這個方法的作用是在于:如果指定的刪除元素在鏈表中就刪除,(區(qū)別:刪除最開始出現(xiàn)的&刪除最后一個出現(xiàn)的),如果不存在鏈表不變
Get
getFirst() & getLast(),實(shí)現(xiàn)比較簡單就不注釋了public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; }public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }get(int),實(shí)現(xiàn)比較簡單就不注釋了public E get(int index) { checkElementIndex(index); return node(index).item; }
set
set(int,E)public E set(int index, E element) { //檢查索引 checkElementIndex(index); //利用node方法取出index上的節(jié)點(diǎn) Node<E> x = node(index); //保存作為返回 E oldVal = x.item; //替換 x.item = element; return oldVal; }
隊(duì)列操作
對于LinkedList還支持隊(duì)列操作,其實(shí)現(xiàn)也是比較簡單的,都是依靠于之前介紹的add方法和remove方法(unlink),所以不打算貼出源碼了,所支持的操作有類似
peek,poll,push,pop等等,只了列舉部分
writeObject&readObject
至于LinkedList的序列化機(jī)制也是類似ArrayList的序列化方式和步驟,都是先將類中no-static和no-transient屬性寫到流中,然后寫size,然后依次寫元素,反序列化即相同步驟即可
總結(jié):我們可以看到LinkedList是雙向鏈表的實(shí)現(xiàn),并沒有首尾相連,所以也不是環(huán)形鏈表,并且其中不存在初始化容量概念,并且不存在ArrayList中的容量限制常量,所以說這個類可以做到理論上的無限大,并且從中沒發(fā)現(xiàn)同步代碼塊,所以這個類也不是同步的,需要我們在使用的時候注意使用場景,對于其他的操作就是常規(guī)的鏈表操作
13450931319
微信登錄
QQ登錄
微博登錄
售前咨詢
