當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

collection 源码

發(fā)布時(shí)間：2025/7/14 编程问答 25 豆豆

生活随笔收集整理的這篇文章主要介紹了 collection 源码小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

轉(zhuǎn)自：http://blog.csdn.net/longlong2015/article/details/48174421

http://blog.csdn.net/mra__s__/article/details/55517204

http://www.cnblogs.com/chenssy/p/3746600.html

?

JDK 1.7源碼閱讀筆記（三）集合類之LinkedList

標(biāo)簽：?jdklinkedlist源碼閱讀 2015-09-02 09:58?644人閱讀?評(píng)論(0)?收藏?舉報(bào) ?分類： JDK源碼（6）?

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

目錄(?)[+]

前言

　　（1）LinkedList的內(nèi)部實(shí)現(xiàn)是雙向鏈表，繼承了AbstractSequentialList，實(shí)現(xiàn)了List, Deque, Cloneable,?Java.io.Serializable接口，因此LinkdeList本身支持就支持雙端隊(duì)列操作。LinkedList**允許所有元素（包括 null）**。除了實(shí)現(xiàn) List 接口外，LinkedList 類還為在列表的開頭及結(jié)尾 get、remove 和 insert 元素提供了統(tǒng)一的命名方法。這些操作允許將鏈接列表用作堆棧、隊(duì)列或雙端隊(duì)列。

　　此類實(shí)現(xiàn) Deque 接口，為 add、poll 提供先進(jìn)先出隊(duì)列操作，以及其他堆棧和雙端隊(duì)列操作。?
　　LinkedList與ArrayList一樣實(shí)現(xiàn)List接口，只是ArrayList是List接口的大小可變數(shù)組的實(shí)現(xiàn)，LinkedList是List接口鏈表的實(shí)現(xiàn)。基于鏈表實(shí)現(xiàn)的方式使得LinkedList在插入和刪除時(shí)更優(yōu)于ArrayList，而隨機(jī)訪問則比ArrayList遜色些。

　　（2）此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問一個(gè)鏈接列表，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了該列表，則它必須保持外部同步。（結(jié)構(gòu)修改指添加或刪除一個(gè)或多個(gè)元素的任何操作；僅設(shè)置元素的值不是結(jié)構(gòu)修改。）這一般通過對(duì)自然封裝該列表的對(duì)象進(jìn)行同步操作來完成。如果不存在這樣的對(duì)象，則應(yīng)該使用 Collections.synchronizedList 方法來“包裝”該列表。最好在創(chuàng)建時(shí)完成這一操作，以防止對(duì)列表進(jìn)行意外的不同步訪問，如下所示：

List list = Collections.synchronizedList(new LinkedList(...));

　　（3）此類的 iterator 和 listIterator 方法返回的迭代器是快速失敗的：在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對(duì)列表進(jìn)行修改，除非通過迭代器自身的 remove 或 add 方法，其他任何時(shí)間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對(duì)并發(fā)的修改，迭代器很快就會(huì)完全失敗，而不冒將來不確定的時(shí)間任意發(fā)生不確定行為的風(fēng)險(xiǎn)。

　　注意，迭代器的快速失敗行為不能得到保證，一般來說，存在不同步的并發(fā)修改時(shí)，不可能作出任何硬性保證。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯(cuò)誤的，正確做法是：迭代器的快速失敗行為應(yīng)該僅用于檢測程序錯(cuò)誤。

　　（4）和ArrayList類似，在類內(nèi)部同樣出現(xiàn)了transient關(guān)鍵字，這在ArrayList中已經(jīng)解釋過了，在這里不做過多的解釋了。

transient int size = 0;transient Node<E> first;transient Node<E> last;

源碼

1>LinkedList內(nèi)部通過Node來抽象一個(gè)節(jié)點(diǎn)，結(jié)點(diǎn)包括值和前向指針和后向指針。Node的定義是在LinkedList內(nèi)部，作為靜態(tài)內(nèi)部類存在。

private static class Node<E> { E item;//結(jié)點(diǎn)的值 Node<E> next;//結(jié)點(diǎn)的后向指針 Node<E> prev;//結(jié)點(diǎn)的前向指針 //構(gòu)造函數(shù)中已完成Node成員的賦值 Node(Node<E> prev, E element, Node<E> next) { this.item = element;//結(jié)點(diǎn)的值賦值為element this.next = next;//后向指針賦值 this.prev = prev;//前向指針賦值 } }

2>LinkedList 的關(guān)鍵源碼

//LinedList繼承了AbstractSequentialList，支持泛型 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable { transient int size = 0;//鏈表元素個(gè)數(shù) transient Node<E> first;//鏈表頭結(jié)點(diǎn) transient Node<E> last;//鏈表尾結(jié)點(diǎn) //生成一個(gè)空的鏈表 public LinkedList() { } //按c里面的元素生成一個(gè)LinkedList public LinkedList(Collection<? extends E> c) { this();//調(diào)用空的構(gòu)造函數(shù) addAll(c);//將c里面的元素添加到空鏈表尾部 } //首部增加結(jié)點(diǎn)，結(jié)點(diǎn)的值為e private void linkFirst(E e) { final Node<E> f = first;//f指向頭結(jié)點(diǎn) //生成一個(gè)新結(jié)點(diǎn)，結(jié)點(diǎn)的值為e,其前向指針為null，后向指針為f final Node<E> newNode = new Node<>(null, e, f); //first指向新生成的結(jié)點(diǎn)，f保存著老的頭結(jié)點(diǎn)信息 first = newNode; if (f == null) //如果f為null，則表示整個(gè)鏈表目前是空的，則尾結(jié)點(diǎn)也指向新結(jié)點(diǎn) last = newNode; else //f(老的頭結(jié)點(diǎn))的前向指針指向最新的結(jié)點(diǎn)信息 f.prev = newNode; size++;//元素個(gè)數(shù)+1. modCount++;//修改次數(shù)+1 } //尾部增加結(jié)點(diǎn)，結(jié)點(diǎn)的值為e void linkLast(E e) { final Node<E> l = last;//l指向尾結(jié)點(diǎn) //生成一個(gè)新結(jié)點(diǎn)，結(jié)點(diǎn)的值為e，其前向指針為l，后向指針為null final Node<E> newNode = new Node<>(l, e, null); //last指向新生成的結(jié)點(diǎn),l保存著老的尾結(jié)點(diǎn)信息 last = newNode; if (l == null) //如果l為null,則表示整個(gè)鏈表目前是空的，則頭結(jié)點(diǎn)也指向新結(jié)點(diǎn) first = newNode; else //l(老的尾結(jié)點(diǎn))的后向指針指向最新的結(jié)點(diǎn)信息 l.next = newNode; size++;//元素個(gè)數(shù)+1 modCount++;//修改次數(shù)+1 } //非空結(jié)點(diǎn)succ之前插入新結(jié)點(diǎn)，新結(jié)點(diǎn)的值為e void linkBefore(E e, Node<E> succ) { // assert succ != null;//外界調(diào)用需保證succ不為null,否則程序會(huì)拋出空指針異常 final Node<E> pred = succ.prev;//pred指向succ的前向結(jié)點(diǎn) //生成一個(gè)新結(jié)點(diǎn)，結(jié)點(diǎn)的值為e,其前向指針指向pred，后向指針指向succ final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode;//succ的前向指針指向newNode if (pred == null) //如果pred為null，則表示succ為頭結(jié)點(diǎn)，此時(shí)頭結(jié)點(diǎn)指向最新生成的結(jié)點(diǎn)newNode first = newNode; else //pred的后向指針指向新生成的結(jié)點(diǎn)，此時(shí)已經(jīng)完成了結(jié)點(diǎn)的插入操作 pred.next = newNode; size++;//元素個(gè)數(shù)+1 modCount++;//修改次數(shù)+1 } //刪除頭結(jié)點(diǎn)，并返回該結(jié)點(diǎn)的值 private E unlinkFirst(Node<E> f) { // assert f == first && f != null;//需確保f為頭結(jié)點(diǎn),且鏈表不為Null final E element = f.item;//獲得結(jié)點(diǎn)的值 final Node<E> next = f.next;//next指向f的后向結(jié)點(diǎn) f.item = null;//釋放數(shù)據(jù)結(jié)點(diǎn) f.next = null;//釋放f的后向指針 first = next;//first指向f的后向結(jié)點(diǎn) if (next == null) //如果next為null，則表示f為last結(jié)點(diǎn)，此時(shí)鏈表即為空鏈表 last = null; else //修改next的前向指針，因?yàn)閒irst結(jié)點(diǎn)的前向指針為null next.prev = null; size--;//元素個(gè)數(shù)-1 modCount++;//修改次數(shù)+1 return element; } //刪除尾結(jié)點(diǎn)，并返回尾結(jié)點(diǎn)的內(nèi)容 private E unlinkLast(Node<E> l) { // assert l == last && l != null;//需確保l為尾結(jié)點(diǎn)，且鏈表不為null final E element = l.item;//獲得結(jié)點(diǎn)的值 final Node<E> prev = l.prev;//prev執(zhí)行l(wèi)的前向結(jié)點(diǎn) l.item = null;//釋放l結(jié)點(diǎn)的值 l.prev = null; //釋放l結(jié)點(diǎn)的前向指針 last = prev;//last結(jié)點(diǎn)指向l的前向結(jié)點(diǎn) if (prev == null) //如果prev為null，則表示l為first結(jié)點(diǎn),此時(shí)鏈表即為空鏈表 first = null; else //修改prev的后向指針，因?yàn)閘ast結(jié)點(diǎn)的后向指針為null prev.next = null; size--;//元素個(gè)數(shù)-1 modCount++;//修改次數(shù)+1 return element; } //刪除結(jié)點(diǎn)x E unlink(Node<E> x) { // assert x != null;//需確保x不為null，否則后續(xù)操作會(huì)拋出空指針異常 final E element = x.item;//保存x結(jié)點(diǎn)的值 final Node<E> next = x.next;//next指向x的后向結(jié)點(diǎn) final Node<E> prev = x.prev;//prev指向x的前向結(jié)點(diǎn) if (prev == null) { //如果prev為空，則x結(jié)點(diǎn)為first結(jié)點(diǎn)，此時(shí)first結(jié)點(diǎn)指向next結(jié)點(diǎn)（x的后向結(jié)點(diǎn)） first = next; } else { prev.next = next;//x的前向結(jié)點(diǎn)的后向指針指向x的后向結(jié)點(diǎn) x.prev = null;//釋放x的前向指針 } if (next == null) { //如果next結(jié)點(diǎn)為空，則x結(jié)點(diǎn)為尾部結(jié)點(diǎn)，此時(shí)last結(jié)點(diǎn)指向prev結(jié)點(diǎn)(x的前向結(jié)點(diǎn)) last = prev; } else { next.prev = prev;//x的后向結(jié)點(diǎn)的前向指針指向x的前向結(jié)點(diǎn) x.next = null;//釋放x的后向指針 } x.item = null;//釋放x的值節(jié)點(diǎn),此時(shí)x節(jié)點(diǎn)可以完全被GC回收 size--;//元素個(gè)數(shù)-1 modCount++;//修改次數(shù)+1 return element; } //獲得頭結(jié)點(diǎn)的值 public E getFirst() { final Node<E> f = first;//f指向first結(jié)點(diǎn) if (f == null)//此時(shí)鏈表為空 throw new NoSuchElementException(); return f.item;//返回first結(jié)點(diǎn)的值 } //獲得尾結(jié)點(diǎn)的值 public E getLast() { final Node<E> l = last;//l指向last結(jié)點(diǎn) if (l == null)//此時(shí)鏈表為空 throw new NoSuchElementException(); return l.item;//返回last結(jié)點(diǎn)的值 } //移除頭結(jié)點(diǎn) public E removeFirst() { final Node<E> f = first;//獲得頭結(jié)點(diǎn) if (f == null)//此時(shí)鏈表為空 throw new NoSuchElementException(); return unlinkFirst(f);//摘除頭結(jié)點(diǎn) } //移除尾結(jié)點(diǎn) public E removeLast() { final Node<E> l = last;//獲得尾結(jié)點(diǎn) if (l == null)//此時(shí)鏈表為空 throw new NoSuchElementException(); return unlinkLast(l);//摘除尾結(jié)點(diǎn) } //添加到頭結(jié)點(diǎn)，結(jié)點(diǎn)的值為e public void addFirst(E e) { linkFirst(e);//添加到頭部 } //添加到尾結(jié)點(diǎn)，結(jié)點(diǎn)值為e public void addLast(E e) { linkLast(e);//添加到尾部 } //判斷元素（值為o）是o否在鏈表中 public boolean contains(Object o) { return indexOf(o) != -1;//定位元素 } //返回元素個(gè)數(shù) public int size() { return size; } //添加元素，元素值為e public boolean add(E e) { linkLast(e);//添加到鏈表尾部 return true; } //移除值為o的元素，o可以為null,找到一個(gè)刪除即返回 public boolean remove(Object o) { if (o == null) {//元素為null for (Node<E> x = first; x != null; x = x.next) {//從頭結(jié)點(diǎn)開始遍歷 if (x.item == null) {//找到一個(gè)結(jié)點(diǎn) 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; } //將c中的元素都添加到當(dāng)前鏈表中 public boolean addAll(Collection<? extends E> c) { return addAll(size, c);//添加到鏈表尾部 } //第序號(hào)為index處，添加c中所有的元素到當(dāng)前鏈表中(后向添加的) public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index);//判斷index是否超出界 Object[] a = c.toArray();//將集合轉(zhuǎn)換為數(shù)組 int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; if (index == size) {//如果index為元素個(gè)數(shù)，即第index個(gè)結(jié)點(diǎn)為尾結(jié)點(diǎn) succ = null; pred = last;//指向?yàn)榻Y(jié)點(diǎn) }

轉(zhuǎn)載于:https://www.cnblogs.com/thxu/p/7406971.html

總結(jié)

以上是生活随笔為你收集整理的collection 源码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇： HTTP 错误 404.15 - Not
下一篇：项目管理三大认证体系，该选择谁?