LinkedList源碼分析

LinkedList的基本存儲結(jié)構(gòu)是鏈表

LinkedList的節(jié)點(diǎn)元素的存儲結(jié)構(gòu)為:

? ? ?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的add源碼為:

public boolean add(E e){

? ? ?linkLast(e);

? ? ?return true;

}

void linkLast(E e){

? ? ?final Node<E> l = last;

? ? ?final Node<E> newNode = new Node<>(l,e,null);

? ? ?last = newNode;

? ? ?if(l==null)

? ? ? ? ? first = newNode;

? ? ?else

? ? ? ? ? l.next = newNode;

? ? ?size++;

? ? ?modCount++;

}

因?yàn)長inkedList的基本結(jié)構(gòu)是鏈表祈远,所以add就是在鏈表的末尾添加一個(gè)節(jié)點(diǎn)氢橙,然后size++,當(dāng)last==null代表改list為空的碧囊,所以頭結(jié)點(diǎn)置為newNode

linkedList的remove源碼為:

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;

}

linkedList的remove就是從頭遍歷節(jié)點(diǎn)责语,然后調(diào)用unlink來remove節(jié)點(diǎn)鸟辅,unlink的源碼如下:

? ?E unlink(Node<E> x){

? ? ? ? ? final E element = x.item;

? ? ? ? ? final Node<E> next = x.next;

? ? ? ? ? final Node<E> prev = x.prev;

? ? ? ? ? if(prev == null){

? ? ? ? ? ? ? ?first=next;

? ? ? ? ? }else{

? ? ? ? ? ? ? ?prev.next = next;

? ? ? ? ? ? ? ?x.prev = null;

? ? ? ? ? }

? ? ? ? ? if(next == null){

? ? ? ? ? ? ? ?last=prev;

? ? ? ? ? }else{

? ? ? ? ? ? ? ?next.prev=prev;

? ? ? ? ? ? ? ?x.next = null;

? ? ? ? ? }

? ? ? ? ? x.item = null;

? ? ? ? ? size--;

? ? ? ? ? modCount++;

? ? ? ? ? return element;

? ? ?}

``unlink就是把元素的前節(jié)點(diǎn)的next指向該元素的next,把元素的后節(jié)點(diǎn)的prev指向該元素的prev,然后把該元素的prev和next和item置為null,方便GC回收庶溶。

linkedList的get的源碼為:

public E get(int index){

? ? ?checkElementIndex(index);

? ? ?return node(index).item;

}

get的時(shí)候先檢測了index是否<0或者大于size,若是則拋出異常宅此。node()的源碼為:

Node<E> node(int index){

? ? ?if(index<(size>>1)){

? ? ? ? ? Node<E> x = first;

? ? ? ? ? for(int i=0;i<index;i++)

? ? ? ? ? ? ? ?x=x.next;

? ? ? ? ? return x;

? ? ?}else{

? ? ? ? ? Node<E> x = last;

? ? ? ? ? for(int i=size-1;i>index;i--)

? ? ? ? ? ? ? ?x = x.prev;

? ? ? ? ? return x;

? ? ?}

}

node方法就是先判斷一下index接近first還是last秦踪,然后決定從哪個(gè)方向開始查找褐捻。

linkedList的contains的源碼為:

public boolean contains(Object o){

? ? ?return indexOf(o)!=-1;

}

public int indexOf(Object o){

? ? ?int index = 0;

?????if(o==null){

? ? ? ? ? for(Node<E> x=first;x!=null;x=x.next){

? ? ? ? ? ? ? ?if(x.item == null)

? ? ? ? ? ? ? ? ? ? return index;

? ? ? ? ? ? ? ?index++;

? ? ? ? ? }

? ? ?}else{

? ? ? ? ? for(Node<E> x = first;x!=null;x=x.next){

? ? ? ? ? ? ? ? ? if(o.equals(x.item))

? ? ? ? ? ? ? ? ? ? ? ? ?return index;

? ? ? ? ? ? ? ? ? ? index++;

? ? ? ? ? }

? ? ?}

? ? ?return -1;

}

contains就是從first開始遍歷掸茅,查到就返回index

linkedList的clone的源碼為:

public Object clone(){

? ? ?LinkedList<E> clone = superClone();

? ? ?clone.first = clone.last=null;

? ? ?clone.size=0;

? ? ?clone.modCount = 0;

? ? ?for(Node<E> x=first;x!=null;x=x.next)

? ? ? ? ? clone.add(x.item);

? ? ?return clone;

}

``LinkedList的clone是淺克隆,只是克隆了引用柠逞。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末昧狮,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子板壮,更是在濱河造成了極大的恐慌逗鸣,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件绰精,死亡現(xiàn)場離奇詭異撒璧,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)笨使,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門卿樱,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人硫椰,你說我怎么就攤上這事繁调。” “怎么了靶草?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵蹄胰,是天一觀的道長。 經(jīng)常有香客問我奕翔,道長裕寨,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任派继,我火速辦了婚禮帮坚,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘互艾。我一直安慰自己试和,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布纫普。 她就那樣靜靜地躺著阅悍,像睡著了一般。 火紅的嫁衣襯著肌膚如雪昨稼。 梳的紋絲不亂的頭發(fā)上节视,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天,我揣著相機(jī)與錄音假栓,去河邊找鬼寻行。 笑死,一個(gè)胖子當(dāng)著我的面吹牛匾荆,可吹牛的內(nèi)容都是我干的拌蜘。 我是一名探鬼主播杆烁,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼简卧!你這毒婦竟也來了兔魂?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤举娩,失蹤者是張志新(化名)和其女友劉穎析校,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體铜涉,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡智玻,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了芙代。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片尚困。...
    茶點(diǎn)故事閱讀 40,865評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖链蕊,靈堂內(nèi)的尸體忽然破棺而出事甜,到底是詐尸還是另有隱情,我是刑警寧澤滔韵,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布逻谦,位于F島的核電站,受9級特大地震影響陪蜻,放射性物質(zhì)發(fā)生泄漏邦马。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一宴卖、第九天 我趴在偏房一處隱蔽的房頂上張望滋将。 院中可真熱鬧,春花似錦症昏、人聲如沸随闽。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽掘宪。三九已至,卻和暖如春攘烛,著一層夾襖步出監(jiān)牢的瞬間魏滚,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工坟漱, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留鼠次,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像腥寇,于是被迫代替她去往敵國和親成翩。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容