LinkedList的深入了解

　　什么是LinkedList?

　　LinkedList是一種雙向鏈表。那什么是雙向鏈表?根據(jù)雙向鏈表的特點就是會有頭節(jié)點和尾節(jié)點，并且節(jié)點之間是通過前驅(qū)指針和后繼指針來維護關(guān)系的，而不是像數(shù)組那樣通過上下標(biāo)來維護節(jié)點之間的關(guān)系的。也就是說雙向鏈表即可以從頭到尾遍歷，也可以從尾到頭遍歷

　　LinkedList與ArrayList的區(qū)別

　　大致區(qū)別如下：

　　1、ArrayList是基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，LinkedList是基于鏈表的數(shù)據(jù)結(jié)構(gòu)

　　2、對于隨機訪問 get() 和 set() 操作，ArrayList優(yōu)于LinkedList，因為LinkedList沒有繼承RandomAccess，而且LinkedList要移動指針

　　3、對于add(新增)操作和remove(刪除)操作，LinkedList比較占優(yōu)勢，因為ArrayList要移動數(shù)據(jù)

　　LinkedList繼承了哪些類與接口?

　　public class LinkedList

　　extends AbstractSequentialList

　　implements List, Deque, Cloneable, java.io.Serializable{

　　}

　　LinkedList 類繼承了 AbstractSequentialList 類，并實現(xiàn)了 List、Deque、Cloneable、Serializable

　　LinkedList中主要的成員變量

　　// 初始化鏈表的長度為0

　　transient int size = 0;

　　// 指向頭節(jié)點的變量

　　transient Node first;

　　// 指向尾節(jié)點的變量

　　transient Node last;

　　LinkedList的構(gòu)造方法

　　LinkedList()

　　// 創(chuàng)建一個空的構(gòu)造方法

　　public LinkedList() {

　　}

　　LinkedList(Collection c)

　　// 創(chuàng)建一個指定Collection對象作為參數(shù)的構(gòu)造函數(shù)，元素的順內(nèi)由這個對象迭代返回的順序決定

　　public LinkedList(Collection c) {

　　this();

　　addAll(c);

　　}

　　addAll(Collection c)方法

　　// 將集合中的所有元素從指定的位置開始插入這個列表

　　public boolean addAll(Collection c) {

　　return addAll(size, c);

　　}

　　addAll(int index, Collection c)方法

　　public boolean addAll(int index, Collection c) {

　　// 判斷下標(biāo)元素是否在鏈表的長度范圍之內(nèi)

　　checkPositionIndex(index);

　　// 將集合轉(zhuǎn)換為Object數(shù)組

　　Object[] a = c.toArray();

　　// 計算Object數(shù)組的長度

　　int numNew = a.length;

　　// 如果Object數(shù)組長度為0

　　if (numNew == 0)

　　// 返回布爾值false

　　return false;

　　// pred節(jié)點為succ節(jié)點的前驅(qū)

　　Node pred, succ;

　　// 如果下標(biāo)等于鏈表長度的時候

　　if (index == size) {

　　// succ節(jié)點指向為null

　　succ = null;

　　// pred節(jié)點指向尾節(jié)點

　　pred = last;

　　} else {

　　// 否則如果下標(biāo)不等于鏈表長度的話，那么succ節(jié)點就是node()方法通過下標(biāo)索引獲得

　　succ = node(index);

　　// 獲得鏈表中的對應(yīng)的節(jié)點對象

　　pred = succ.prev;

　　}

　　// 遍歷要添加內(nèi)容的數(shù)組

　　for (Object o : a) {

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

　　// 創(chuàng)建新的節(jié)點，將遍歷的值包裝成Node節(jié)點

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

　　// 如果前驅(qū)節(jié)點為null

　　if (pred == null)

　　// 那么新的節(jié)點就是頭節(jié)點

　　first = newNode;

　　else

　　// 否則pred指向新創(chuàng)建的節(jié)點

　　pred.next = newNode;

　　// pred節(jié)點往后移動一位

　　pred = newNode;

　　}

　　// 因為pred節(jié)點是succ節(jié)點的前驅(qū)節(jié)點，反過來也就是說succ是pred的后繼節(jié)點

　　// 所以如果succ為null，表示pred為尾節(jié)點

　　if (succ == null) {

　　last = pred;

　　} else {

　　/**

　　* 否則如果succ不是尾節(jié)點，那么只要保證pred節(jié)點是succ節(jié)點的前驅(qū)節(jié)點、

　　succ節(jié)點是pred的后繼節(jié)點這種雙向鏈表的關(guān)系就可以了

　　*/

　　pred.next = succ;

　　succ.prev = pred;

　　}

　　// 元素個數(shù)增加

　　size += numNew;

　　modCount++;

　　return true;

　　}

　　checkPositionIndex(int index)方法

　　private void checkPositionIndex(int index) {

　　if (!isPositionIndex(index))

　　// 拋出 IndexOutOfBoundsException 異常

　　throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

　　}

　　isPositionIndex(int index)方法

　　private boolean isPositionIndex(int index) {

　　// 這個這么簡單就不解釋了吧

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

　　}

　　Node節(jié)點

　　private static class Node {

　　E item; // 節(jié)點的值

　　Node next; // 指向前一個節(jié)點

　　Node prev; // 指向后一個節(jié)點

　　// 初始化

　　Node(Node prev, E element, Node next) {

　　this.item = element;

　　this.next = next;

　　this.prev = prev;

　　}

　　}

　　LinkedList的常用方法

　　add(E e)

　　// 使用雙向鏈表的尾插法

　　public boolean add(E e) {

　　// 將元素插入到鏈表尾部

　　linkLast(e);

　　return true;

　　}

　　linkLast(E e)

　　// 插入的節(jié)點為尾節(jié)點

　　void linkLast(E e) {

　　// 創(chuàng)建一個節(jié)點并初始化為尾節(jié)點

　　final Node l = last;

　　// 初始化新的節(jié)點，前驅(qū)的節(jié)點為l，后繼節(jié)點為null

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

　　// 因為是在鏈表的尾部插入節(jié)點，所以新的節(jié)點作為尾節(jié)點(這個不難理解)

　　last = newNode;

　　// l節(jié)點作為newNode節(jié)點的前驅(qū)節(jié)點，如果l為空，則說明newNode前驅(qū)節(jié)點為空

　　if (l == null)

　　// 在雙向鏈表中，前驅(qū)節(jié)點為空，那么該節(jié)點為頭節(jié)點

　　first = newNode;

　　else

　　// 否則 l 的下一個節(jié)點指向該節(jié)點

　　l.next = newNode;

　　// 鏈表長度+1

　　size++;

　　modCount++;

　　}

　　add(int index, E element)

　　// 指定位置插入元素

　　public void add(int index, E element) {

　　// 判斷下標(biāo)索引是否在鏈表長度范圍內(nèi)(上述講到過)

　　checkPositionIndex(index);

　　// 如果下標(biāo)索引等于鏈表長度

　　if (index == size)

　　// 則采用尾插法(剛剛講到過)

　　linkLast(element);

　　else

　　// 否則采用頭插法

　　linkBefore(element, node(index));

　　}

　　linkBefore()

　　// 插入的節(jié)點為頭節(jié)點，在節(jié)點succ之前插入元素e

　　void linkBefore(E e, Node succ) {

　　// assert succ != null;

　　// succ節(jié)點的前驅(qū)節(jié)點為pred

　　final Node pred = succ.prev;鄭州哪家醫(yī)院看婦科好 http://www.120zzkd.com/

　　// 初始化新的前驅(qū)節(jié)點為pred，后繼節(jié)點為succ(簡單地說就是在pred和succ節(jié)點之間插入元素)

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

　　// 后繼節(jié)點為succ，succ的前驅(qū)節(jié)點為newNode

　　succ.prev = newNode;

　　// 如果pred為null

　　if (pred == null)

　　// 則newNode為頭節(jié)點

　　first = newNode;

　　else

　　// 否則pred的下一個節(jié)點指向newNode

　　pred.next = newNode;

　　// 鏈表長度+1

　　size++;

　　modCount++;

　　}

　　remove(Object o)

　　// 刪除元素

　　public boolean remove(Object o) {

　　/** 通過雙向鏈表的前后關(guān)系，遍歷雙向鏈表。

　　* 判斷是否存在元素和要刪除的元素相同。

　　* 如果遍歷到了，那么就刪除元素，并且返回true

　　*/

　　if (o == null) {

　　for (Node x = first; x != null; x = x.next) {

　　if (x.item == null) {

　　unlink(x);

　　return true;

　　}

　　}

　　} else {

　　for (Node x = first; x != null; x = x.next) {

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

　　unlink(x);

　　return true;

　　}

　　}

　　}

　　// 如果沒遍歷到，那么就返回false

　　return false;

　　}

　　unlink()

　　// 刪除非空節(jié)點

　　E unlink(Node x) {

　　// assert x != null;

　　final E element = x.item;

　　// 獲取該元素的后繼節(jié)點

　　final Node next = x.next;

　　// 獲取該元素的前驅(qū)節(jié)點

　　final Node prev = x.prev;

　　// 如果前驅(qū)節(jié)點pred為null

　　if (prev == null) {

　　// 表示當(dāng)前要刪除的節(jié)點為頭節(jié)點，讓pred的后繼節(jié)點作為頭節(jié)點

　　first = next;

　　} else {

　　// 否則直接使用雙向鏈表刪除節(jié)點

　　prev.next = next;

　　// 將刪除節(jié)點x的前驅(qū)節(jié)點設(shè)置為null

　　x.prev = null;

　　}

　　// 如果后繼節(jié)點為null

　　if (next == null) {

　　// 表示當(dāng)前刪除的節(jié)點為尾節(jié)點，將前驅(qū)節(jié)點作為尾節(jié)點

　　last = prev;

　　} else {

　　// 否則如果后繼節(jié)點不為null，使用雙向鏈表刪除節(jié)點

　　next.prev = prev;

　　// 將刪除節(jié)點x的后繼節(jié)點設(shè)置為null

　　x.next = null;

　　}

　　// 將刪除節(jié)點的值設(shè)置為null，方便垃圾回收

　　x.item = null;

　　// 鏈表長度-1

　　size--;

　　modCount++;

　　return element;

　　}

　　get(int index)

　　// 獲取下標(biāo)元素

　　public E get(int index) {

　　// 判斷下標(biāo)是否在鏈表長度范圍內(nèi)(上述講到過)

　　checkElementIndex(index);

　　// 獲取下標(biāo)節(jié)點，返回節(jié)點的值

　　return node(index).item;

　　}

　　node(int index)

　　// 獲取下標(biāo)節(jié)點

　　Node node(int index) {

　　// assert isElementIndex(index);

　　// 判斷下標(biāo)索引是靠近頭節(jié)點還是尾節(jié)點

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

　　// 獲取頭節(jié)點

　　Node x = first;

　　// 遍歷index的節(jié)點

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

　　x = x.next;

　　return x;

　　} else {

　　// 獲取尾節(jié)點

　　Node x = last;

　　// 遍歷index的節(jié)點

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

　　x = x.prev;

　　return x;

　　}

　　}

　　總結(jié)

　　1、LinkedList 添加的元素在取的時候與添加的時候的順序一致。因為向雙向鏈表的尾部添加元素，然后按照頭節(jié)點順序遍歷獲取，所以一致

　　2、LinkedList 允許添加重復(fù)元素

　　3、LinkedList 不是線程安全的集合

　　4、LinkedList 允許添加 null 元素

　　5、add 方法插入元素是在雙向鏈表的尾部插入

　　6、get 方法遍歷雙向鏈表，先判斷下標(biāo)靠近頭節(jié)點還是尾節(jié)點，這樣會減少多余的循環(huán)