LinkedList的源碼解析

public class LinkedList<E>

??? extends AbstractSequentialList<E>

??? implements List<E>, Deque<E>, Cloneable, java.io.Serializable

{

??? transient int size = 0;? // transient不可序列化

??? transient Node<E> first;

??? transient Node<E> last;

構造方法:

??? public LinkedList() {

??? }

??? public LinkedList(Collection<? extends E> c) {

??????? this();

??????? addAll(c);

??? }

//內(nèi)部私有類Node:

? 構造方法的參數(shù)順序是：前繼節(jié)點的引用潭千，數(shù)據(jù)灾搏，后繼節(jié)點的引用套媚。

??? 關于為什么Node這個類是靜態(tài)的侣背？答案是：這跟內(nèi)存泄露有關，Node類是在LinkedList類中的走越，也就是一個內(nèi)部類椭豫，若不使用static修飾，那么Node就是一個普通的內(nèi)部類旨指，在java中赏酥，一個普通內(nèi)部類在實例化之后，默認會持有外部類的引用谆构，這就有可能造成內(nèi)存泄露裸扶。但使用static修飾過的內(nèi)部類（稱為靜態(tài)內(nèi)部類），不用再創(chuàng)建外部類的對象了,就不會有這種問題

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;

??????? }

??? }

Add 方法

//addFirst 執(zhí)行linkFirst方法

public void addFirst(E e) {

??????? linkFirst(e);

}

//addLast 和add執(zhí)行的都是同一個方法

public void addLast(E e) {

??????? linkLast(e);

??? }

public boolean add(E e) {

??????? linkLast(e);

??????? return true;

}

add(index,element)

//在某個索引位置添加元素

//該add方法將添加集合元素分為2種情況搬素，

//一種是在集合尾部添加呵晨，另一種是在集合中間或頭部添加，

public void add(int index, E element) {

//調用方法去檢查輸入的索引是否存在,不在就拋異常

??????? checkPositionIndex(index);

//如果你所輸入的索引值剛好等于集合的大小,就屬于把元素插入到鏈表尾部,索引從0開始

??????? if (index == size)

??????????? linkLast(element);

??????? else

//先調用node(int index)方法得到指定位置的元素節(jié)點,也就是linkBefore()方法中的形參 succ熬尺。

??????????? linkBefore(element, node(index));

??? }

addAll 方法

public boolean addAll(Collection<? extends E> c) {

??????? return addAll(size, c);

??? }

public boolean addAll(int index, Collection<? extends E> c) {

??????? checkPositionIndex(index);? // 檢查是否越界

??????? Object[] a = c.toArray();? // 將集合轉為數(shù)組

??????? int numNew = a.length;??? // 獲取到集合的大小

??????? if (numNew == 0)????? //長度為空返回false

??????????? return false;

??????? Node<E> pred, succ;?? // pred：中間變量何荚， succ：插入位置的后一個元素

??????? if (index == size) {? // 如果插入位置為尾元素的下一個位置

??????????? succ = null;?????? // 插入位置后面沒有元素了

??????????? pred = last;?????? // 新插入集合的前一個元素為原來的尾元素

??????? } else {????????????? // 如果不是在尾部的下一個元素插入

??????????? succ = node(index); // 通過node()方法獲取到index位置的元素

??????????? pred = succ.prev;? // 插入集合的首元素的前指向為index位置的前一個元素

??????? }

??????? for (Object o : a) {? // 循環(huán)遍歷，使新插入集合元素的排列起來猪杭，并使pred指向新插入集合的最后一個元素

??????????? @SuppressWarnings("unchecked") E e = (E) o;

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

??????????? if (pred == null)

??????????????? first = newNode;

??????????? else

??????????????? pred.next = newNode;

??????????? pred = newNode;

??????? }

??????? if (succ == null) {?? // 如果插入位置后一個元素為空，說明是尾部

??????????? last = pred; ????? // 則尾元素置為插入集合的尾元素

??????? } else {

??????????? pred.next = succ;? // 否則將插入集合的尾元素后指向為插入位置的下一個元素

??????????? succ.prev = pred;? // 插入位置的下一個元素的前指向為插入集合的尾元素

??????? }

??????? size += numNew;

??????? modCount++;

??????? return true;

??? }

LinkFirst

//linkFirst方法是私有的所以不能從外部調用

該方法,從外部傳入我們要add的參數(shù)

private void linkFirst(E e) {

//讓此時集合中的頭節(jié)點（即first"指針"指向的節(jié)點）賦給變量f

??????? final Node<E> f = first;??

//創(chuàng)建一個新節(jié)點妥衣，結合Node的構造函數(shù)皂吮，我們可以知道戒傻，在創(chuàng)建新節(jié)點（newNode）的同時，newNode的next指向了f(即之前集合中的頭節(jié)點)蜂筹，變量f 就是newNode的后驅節(jié)點了需纳，newNode的前繼節(jié)點為null。

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

//再將first指向newNode艺挪，也就是說newNode成為該鏈表新的頭節(jié)點

??????? first = newNode;

??????? if (f == null)

//接著不翩，判斷變量f 是否為null，若是null麻裳，說明之前集合中沒有元素（此時newNode是集合中唯一一個元素）口蝠，則將last指向newNode，也就是說此時的newNode既是頭節(jié)點又是尾節(jié)點（要知道津坑，這時newNode中的prev和next均是null妙蔗，但被first和last同時指向）；若變量f 不是null疆瑰，說明之前集合中已經(jīng)存在了至少一個元素眉反，則讓之前集合中的頭節(jié)點（即變量f ）的prev指向newNode。（結合步驟2穆役，此時的newNode與newNode的后驅節(jié)點f已經(jīng)是相互指向了）

??????????? last = newNode;

??????? else

??????????? f.prev = newNode;

??????? size++;

??????? modCount++;??? //理解為修改的次數(shù)

??? }

linkLast方法

?//讓此時集合中的尾節(jié)點（即last"指針"指向的節(jié)點）賦給變量l

??? void linkLast(E e) {

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

//創(chuàng)建一個新節(jié)點寸五，結合Node的構造函數(shù)，我們可以知道耿币，在創(chuàng)建新節(jié)點（newNode）的同時梳杏，newNode的prev指向了l(即之前集合中的尾節(jié)點)，變量 l 就是newNode的前驅節(jié)點了掰读，newNode的后繼節(jié)點為null秘狞。

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

//再將last指向newNode，也就是說newNode成為該鏈表新的末尾節(jié)點蹈集。

??????? last = newNode;

//接著烁试，判斷變量 l 是否為null，若是null拢肆，說明之前集合中沒有元素（此時newNode是集合中唯一一個元素）减响，則將first指向newNode，也就是說此時的newNode既是頭節(jié)點又是尾節(jié)點（要知道郭怪，這時newNode中的prev和next均是null支示，但被first和last同時指向）；若變量 l 不是null鄙才，說明之前集合中已經(jīng)存在了至少一個元素颂鸿，則讓之前集合中的尾節(jié)點（即變量 l ）的next指向newNode。（結合步驟2攒庵，此時的newNode與newNode的前驅節(jié)點 l 已經(jīng)是相互指向了）

??????? if (l == null)

??????????? first = newNode;

??????? else

??????????? l.next = newNode;

??????? size++;

??????? modCount++;

}

LinkBefore方法

??? void linkBefore(E e, Node<E> succ) {

??????? // assertsucc != null;

//通過succ.prevt得到succ的前一個元素pred嘴纺。（此時拿到了第index個元素succ败晴，和第index-1個元素pred）

??????? final Node<E> pred = succ.prev;

//再創(chuàng)建一個新節(jié)點newNode，newNode的prev指向了pred栽渴，newNode的next指向了succ尖坤。（即newNode往succ和pred的中間插入，并單向與它們分別建立聯(lián)系闲擦，eg：pred ← newNode → succ）

??????? final Node<E> newNode = new Node<>(pred, e, succ);

//再讓succ的prev指向newNode慢味。（succ與跟newNode建立聯(lián)系了，此時succ與newNode是雙向關聯(lián)墅冷，eg：pred ← newNode ? succ）纯路。

??????? succ.prev = newNode;

//接著，判斷pred是否為null俺榆，若是null感昼，說明之前succ是集合中的第一個元素（即index值為0），現(xiàn)在newNode跑到了succ前面罐脊，所以只需要將first指向newNode（eg：first ? newNode ?succ）;若pred不為null定嗓，則將pred的next指向newNode。（這時pred也主動與newNode建立聯(lián)系了萍桌，此時pred與newNode也是雙向關聯(lián)宵溅，eg：pred?newNode ? succ）

??????? if (pred == null)

??????????? first = newNode;

??????? else

??????????? pred.next = newNode;

??????? size++;

??????? modCount++;

??? }

remove方法

?? //removeFirst方法

//獲取到LinkedList的首元素，然后判斷是否為空上炎，如果為空恃逻，則拋出NoSuchElementException異常，否則通過調用unlinkFirst(Node<E> f)方法來移除首元素藕施。

unlinkFirst這個方法是LinkedList的內(nèi)部方法寇损，源代碼如下。首先拿到首元素的下一個元素(新的首元素)裳食，然后將首元素的值矛市，和指向下一個元素的變量都置為空，然后等待垃圾回收器空閑的時候把首元素GC掉诲祸，然后判斷新的首元素是否為空浊吏，如果為空，則置尾元素也為空救氯，并且新的首元素的前指向也置空找田，size(列表存儲個數(shù))減一，modeCount(結構變化次數(shù))也減一着憨，返回新的首元素墩衙。

??? public E removeFirst() {

??????? final Node<E> f = first;

??????? if (f == null)???

??????????? throw new NoSuchElementException();

????? return unlinkFirst(f);? // 調用unlinkFirst(Node<E>f)來移除首元素

??? }

??? public E removeLast() {

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

??????? if (l == null)

??????????? throw new NoSuchElementException();

??????? return unlinkLast(l);

??? }

??? 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 = next;

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

??????????? last = null;

??????? else

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

??????? size--;

??????? modCount++;

??????? return element;

??? }

??? private E unlinkLast(Node<E> l) {

??????? // assert l

== last && l != null;

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

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

??????? l.item = null;

??????? l.prev = null; // help GC

??????? last = prev;

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

??????????? first = null;

??????? else

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

??????? size--;

??????? modCount++;

??????? return element;

??? }

//首先通過查找是否包含該元素植袍，實現(xiàn)原理和contains方法一致暮顺，在找到的時候或链，調用unlink方法，移除元素。

unlink方法就是將，要移除元素的前一個元素的后指針指向移除元素的下一個元素，要移除元素的下一個元素的前指針指向要移除元素的上一個元素，當然软能，要判斷前后元素是否為空的狀態(tài)。

?

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;

??? }

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;

??????? 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;

??? }

public E remove(int index) {

??????? checkElementIndex(index);

??????? return unlink(node(index));

??? }

get方法

public E get(int index) {

//先查看索引是否越界

??????? checkElementIndex(index);

??????? return node(index).item;

??? }

??? 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;

??? }

Set方法

public E set(int index, E element) {

??????? checkElementIndex(index);

??????? Node<E> x = node(index);

??????? E oldVal = x.item;

??????? x.item = element;

??????? return oldVal;

??? }

node方法

//根據(jù)索引值查找相應的Node

Node<E> node(int index) {

??????? // assert

isElementIndex(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;

??????? }

??? }

? ?clear方法

? //通過遍歷鏈表椒功，將每一個結點的結構體內(nèi)的變量置為空荠锭，等待垃圾處理器進行回收删豺，并置size為0?

??? public void clear() {

??????? // Clearing

all of the links between nodes is "unnecessary", but:

??????? // - helps a

generational GC if the discarded nodes inhabit

??????? //?? more than one generation

??????? // - is sure

to free memory even if there is a reachable Iterator

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

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

??????????? x.item = null;

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

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

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

??????? }

??????? first = last = null;

??????? size = 0;

??????? modCount++;

??? }

//查看是否包含該元素

public boolean contains(Object o) {

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

??? }

//如果傳入的參數(shù)為空,遍歷是只要得到的item為空的時候就返回當前的index,如果不為空,遍歷是比較器值

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;

??? }

?public int size() {

??????? return size;

??? }

??? private boolean isElementIndex(int index) {

??????? return index >= 0 && index < size;

??? }

??? private boolean isPositionIndex(int index) {

??????? return index >= 0 && index <= size;

??? }

??? private String outOfBoundsMsg(int index) {

??????? return "Index:

"+index+", Size: "+size;

??? }

??? private void checkElementIndex(int index) {

??????? if (!isElementIndex(index))

??????????? throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

??? }

??? private void checkPositionIndex(int index) {

??????? if (!isPositionIndex(index))

??????????? throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

??? }

??? lastIndex方法

??? //返回此列表中最后出現(xiàn)的指定元素的索引惨奕，如果此列表中不包含該元素，則返回 -1港粱。

??? public int lastIndexOf(Object o) {

??????? int index = size;

?? //如果傳入的值為空,遍歷集合,從后往前遍歷,如果得到的item為空就剛好就是那個地方所對應的index

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

??????????? for (Node<E> x = last; x != null; x = x.prev) {

??????????????? index--;

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

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

??????????? }

??????? } else {

??????????? for (Node<E> x = last; x != null; x = x.prev) {

??????????????? index--;

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

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

??????????? }

??????? }

??????? return -1;

??? }

??? public E peek() {

??????? final Node<E> f = first;

??????? return (f == null) ? null : f.item;

??? }

??? public E element() {

??????? return getFirst();

??? }

??? public E poll() {

??????? final Node<E> f = first;

??????? return (f == null) ? null : unlinkFirst(f);

??? }

??? public E remove() {

??????? return removeFirst();

??? }

??? public boolean offer(E e) {

??????? return add(e);

??? }

??? public boolean offerFirst(E e) {

??????? addFirst(e);

??????? return true;

??? }

??? public boolean offerLast(E e) {

??????? addLast(e);

??????? return true;

??? }

??? public E peekFirst() {

??????? final Node<E> f = first;

??????? return (f == null) ? null : f.item;

???? }

??? public E peekLast() {

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

??????? return (l == null) ? null : l.item;

??? }

??? public E pollFirst() {

??????? final Node<E> f = first;

??????? return (f == null) ? null : unlinkFirst(f);

??? }

??? public E pollLast() {

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

??????? return (l == null) ? null : unlinkLast(l);

??? }

??? public void push(E e) {

??????? addFirst(e);

??? }

??? public E pop() {

??????? return removeFirst();

??? }

??? public boolean removeFirstOccurrence(Object o) {

??????? return remove(o);

??? }

??? public boolean removeLastOccurrence(Object o) {

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

??????????? for (Node<E> x = last; x != null; x = x.prev) {

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

???????????????????unlink(x);

???????????????????return true;

??????????????? }

??????????? }

??????? } else {

??????????? for (Node<E> x = last; x != null; x = x.prev) {

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

???????????????????unlink(x);

???????????????????return true;

??????????????? }

??????????? }

??????? }

??????? return false;

??? }

??? public ListIterator<E> listIterator(int index) {

??????? checkPositionIndex(index);

??????? return new ListItr(index);

??? }

}