什么是LinkedList?

創(chuàng)新互聯(lián)專注于蘆山企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站開發(fā),購物商城網(wǎng)站建設(shè)。蘆山網(wǎng)站建設(shè)公司,為蘆山等地區(qū)提供建站服務(wù)。全流程按需定制，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)

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

LinkedList與ArrayList的區(qū)別

大致區(qū)別如下：

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

2、對(duì)于隨機(jī)訪問 get() 和 set() 操作，ArrayList優(yōu)于LinkedList，因?yàn)長(zhǎng)inkedList沒有繼承RandomAccess，而且LinkedList要移動(dòng)指針

3、對(duì)于add(新增)操作和remove(刪除)操作，LinkedList比較占優(yōu)勢(shì)，因?yàn)锳rrayList要移動(dòng)數(shù)據(jù)

LinkedList繼承了哪些類與接口?

public class LinkedList

extends AbstractSequentialList

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

}

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

LinkedList中主要的成員變量

// 初始化鏈表的長(zhǎng)度為0

transient int size = 0;

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

transient Node first;

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

transient Node last;

LinkedList的構(gòu)造方法

LinkedList()

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

public LinkedList() {

}

LinkedList(Collection c)

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

public LinkedList(Collection c) {

this();

addAll(c);

}

addAll(Collection c)方法

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

public boolean addAll(Collection c) {

return addAll(size, c);

}

addAll(int index, Collection c)方法

public boolean addAll(int index, Collection c) {

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

checkPositionIndex(index);

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

Object[] a = c.toArray();

// 計(jì)算Object數(shù)組的長(zhǎng)度

int numNew = a.length;

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

if (numNew == 0)

// 返回布爾值false

return false;

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

Node pred, succ;

// 如果下標(biāo)等于鏈表長(zhǎng)度的時(shí)候

if (index == size) {

// succ節(jié)點(diǎn)指向?yàn)閚ull

succ = null;

// pred節(jié)點(diǎn)指向尾節(jié)點(diǎn)

pred = last;

} else {

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

succ = node(index);

// 獲得鏈表中的對(duì)應(yīng)的節(jié)點(diǎn)對(duì)象

pred = succ.prev;

}

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

for (Object o : a) {

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

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

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

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

if (pred == null)

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

first = newNode;

else

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

pred.next = newNode;

// pred節(jié)點(diǎn)往后移動(dòng)一位

pred = newNode;

}

// 因?yàn)閜red節(jié)點(diǎn)是succ節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，反過來也就是說succ是pred的后繼節(jié)點(diǎn)

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

if (succ == null) {

last = pred;

} else {

/**

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

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

*/

pred.next = succ;

succ.prev = pred;

}

// 元素個(gè)數(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) {

// 這個(gè)這么簡(jiǎn)單就不解釋了吧

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

}

Node節(jié)點(diǎn)

private static class Node {

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

Node next; // 指向前一個(gè)節(jié)點(diǎn)

Node prev; // 指向后一個(gè)節(jié)點(diǎn)

// 初始化

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é)點(diǎn)為尾節(jié)點(diǎn)

void linkLast(E e) {

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

final Node l = last;

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

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

// 因?yàn)槭窃阪湵淼奈膊坎迦牍?jié)點(diǎn)，所以新的節(jié)點(diǎn)作為尾節(jié)點(diǎn)(這個(gè)不難理解)

last = newNode;

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

if (l == null)

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

first = newNode;

else

// 否則 l 的下一個(gè)節(jié)點(diǎn)指向該節(jié)點(diǎn)

l.next = newNode;

// 鏈表長(zhǎng)度+1

size++;

modCount++;

}

add(int index, E element)

// 指定位置插入元素

public void add(int index, E element) {

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

checkPositionIndex(index);

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

if (index == size)

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

linkLast(element);

else

// 否則采用頭插法

linkBefore(element, node(index));

}

linkBefore()

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

void linkBefore(E e, Node succ) {

// assert succ != null;

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

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

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

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

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

succ.prev = newNode;

// 如果pred為null

if (pred == null)

// 則newNode為頭節(jié)點(diǎn)

first = newNode;

else

// 否則pred的下一個(gè)節(jié)點(diǎn)指向newNode

pred.next = newNode;

// 鏈表長(zhǎng)度+1

size++;

modCount++;

}

remove(Object o)

// 刪除元素

public boolean remove(Object o) {

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

* 判斷是否存在元素和要?jiǎng)h除的元素相同。

* 如果遍歷到了，那么就刪除元素，并且返回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é)點(diǎn)

E unlink(Node x) {

// assert x != null;

final E element = x.item;

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

final Node next = x.next;

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

final Node prev = x.prev;

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

if (prev == null) {

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

first = next;

} else {

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

prev.next = next;

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

x.prev = null;

}

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

if (next == null) {

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

last = prev;

} else {

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

next.prev = prev;

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

x.next = null;

}

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

x.item = null;

// 鏈表長(zhǎng)度-1

size--;

modCount++;

return element;

}

get(int index)

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

public E get(int index) {

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

checkElementIndex(index);

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

return node(index).item;

}

node(int index)

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

Node node(int index) {

// assert isElementIndex(index);

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

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

// 獲取頭節(jié)點(diǎn)

Node x = first;

// 遍歷index的節(jié)點(diǎn)

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

x = x.next;

return x;

} else {

// 獲取尾節(jié)點(diǎn)

Node x = last;

// 遍歷index的節(jié)點(diǎn)

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

x = x.prev;

return x;

}

}

總結(jié)

1、LinkedList 添加的元素在取的時(shí)候與添加的時(shí)候的順序一致。因?yàn)橄螂p向鏈表的尾部添加元素，然后按照頭節(jié)點(diǎn)順序遍歷獲取，所以一致

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

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

4、LinkedList 允許添加 null 元素

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

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

文章標(biāo)題：LinkedList的深入了解
文章起源：http://chinadenli.net/article12/gsjidc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、企業(yè)網(wǎng)站制作、品牌網(wǎng)站建設(shè)、面包屑導(dǎo)航、標(biāo)簽優(yōu)化、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)