Java之LinkedList詳解

太極混元天尊 2018-05-23

展開全文

為什么要用LinkedList?

我們?cè)诂F(xiàn)實(shí)開發(fā)中我們都是會(huì)大量使用到數(shù)組以及動(dòng)態(tài)的ArrayList類。然而，數(shù)組和數(shù)組列表都有一個(gè)重大的缺陷。

這就是從數(shù)組的中間位置刪除一個(gè)元素要付出很大的代價(jià)，其原因是數(shù)組中處于被刪除元素之后的所有元素都要向數(shù)組的前端移動(dòng)。在數(shù)組中間的位置上插入一個(gè)元素也是如此。

那么LinkedList(鏈表)就能解決了這個(gè)問(wèn)題盡管數(shù)組在連續(xù)的存儲(chǔ)位置上存放對(duì)象引用，但鏈表卻將每個(gè)對(duì)象存放在獨(dú)立的節(jié)點(diǎn)中。每個(gè)節(jié)點(diǎn)還存放著序列中下一個(gè)結(jié)點(diǎn)的引用。

LinkedList

LinkedList是一個(gè)實(shí)現(xiàn)了List接口和Deque接口的雙向鏈表。

有關(guān)索引的操作可能從鏈表頭開始遍歷到鏈表尾部，也可能從尾部遍歷到鏈表頭部，這取決于看索引更靠近哪一端。

LinkedList不是線程安全的，如果想使LinkedList變成線程安全的，可以使用如下方式：

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

如下圖：

以上圖可以看出，雙向鏈表是一個(gè)和現(xiàn)在的動(dòng)車組類似，2端都是可以當(dāng)作頭來(lái)使用，意思就是說(shuō)可以從前往后面查找，也可以從后往前查找。

LinkedList構(gòu)造方法

LinkedList()

構(gòu)造一個(gè)空列表

LinkedList(Collection c)

構(gòu)造一個(gè)包含指定 collection 中的元素的列表，這些元素按其 collection 的迭代器返回的順序排列。

LinkedList常用方法介紹

public boolean add(Object element)

向鏈表末尾添加一個(gè)新節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù)element指定的對(duì)象。

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
  System.out.println(iterator.next());
}

結(jié)果：
hello1
hello2
hello3
hello4

public void add(int index,Object element)

向鏈表指定位置添加一個(gè)新節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù)element指定的對(duì)象

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
list.add(1,'我是新插入的');
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
   System.out.println(iterator.next());
}

結(jié)果
hello1
我是新插入的
hello2
hello3
hello4

public void addFirist(Object element)

向鏈表表頭添加一個(gè)新節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù)element指定的對(duì)象

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
list.addFirst('addFirst');
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
   System.out.println(iterator.next());
}

結(jié)果
addFirst
hello1
hello2
hello3
hello4

public void addLast(Object element)

向鏈表表尾添加一個(gè)新節(jié)點(diǎn)，該節(jié)點(diǎn)中的數(shù)據(jù)是參數(shù)element指定的對(duì)象

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
list.addLast('addLast');
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
   System.out.println(iterator.next());
}

結(jié)果
hello1
hello2
hello3
hello4
addLast

public Object removeFirst()

刪除第一個(gè)節(jié)點(diǎn)并返回這個(gè)節(jié)點(diǎn)中的對(duì)象

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
String str = list.removeFirst();//刪除第一個(gè)節(jié)點(diǎn)
System.out.println('刪除第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)為：'+str);

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
   System.out.println(iterator.next());
}

結(jié)果
刪除第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)為：hello1
hello2
hello3
hello4

public Object removeLast()

刪除最后一個(gè)節(jié)點(diǎn)并返回這個(gè)節(jié)點(diǎn)中的對(duì)象

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
String str = list.removeLast();//刪除最后節(jié)點(diǎn)
System.out.println('刪除最后節(jié)點(diǎn)的數(shù)據(jù)為：'+str);

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
   System.out.println(iterator.next());
}

結(jié)果
刪除最后節(jié)點(diǎn)的數(shù)據(jù)為：hello4
hello1
hello2
hello3

public Object remove(int index)

刪除指定位置的節(jié)點(diǎn)

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
String str = list.remove(1);//刪除索引為1的節(jié)點(diǎn)
System.out.println('刪除索引為1的節(jié)點(diǎn)數(shù)據(jù)為：'+str);

Iterator iterator = list.iterator();
while (iterator.hasNext()) {
   System.out.println(iterator.next());
}

結(jié)果
刪除索引為1的節(jié)點(diǎn)數(shù)據(jù)為：hello2
hello1
hello3
hello4

public Object get(int index)

得到指定位置的節(jié)點(diǎn)

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
String str = list.get(1);//獲取索引為1的值
System.out.println('獲取索引為1的值：'+str);

結(jié)果
獲取索引為1的值：hello2

public Object getFirst()

得到鏈表第一個(gè)節(jié)點(diǎn)的對(duì)象

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
String str = list.getFirst();//獲取鏈表第一個(gè)元素的值
System.out.println('獲取鏈表第一個(gè)元素的值：'+str);

結(jié)果
獲取鏈表第一個(gè)元素的值：hello1

public Object getLast()

得到鏈表最后一個(gè)節(jié)點(diǎn)的對(duì)象

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
String str = list.getLast();//獲取鏈表最后一個(gè)元素的值
System.out.println('獲取鏈表最后一個(gè)元素的值：'+str);

結(jié)果
獲取鏈表最后一個(gè)元素的值：hello4

int indexOf(Object element)

返回節(jié)點(diǎn)對(duì)象element在鏈表中首次出現(xiàn)的位置，如果鏈表中無(wú)此節(jié)點(diǎn)的對(duì)象則返回-1

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
//返回節(jié)點(diǎn)對(duì)象element在鏈表中首次出現(xiàn)的位置，如果鏈表中無(wú)此節(jié)點(diǎn)的對(duì)象則返回-1
int index = list.indexOf('hello2');
System.out.println('返回節(jié)點(diǎn)對(duì)象element在鏈表中首次出現(xiàn)的位置：'+index);

結(jié)果
返回節(jié)點(diǎn)對(duì)象element在鏈表中首次出現(xiàn)的位置：1

public int lastIndexOf(Object element)

返回節(jié)點(diǎn)對(duì)象element在鏈表中最后出現(xiàn)的位置，如果鏈表中無(wú)此節(jié)點(diǎn)的對(duì)象則返回-1

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
//返回節(jié)點(diǎn)對(duì)象element在鏈表中最后出現(xiàn)的位置，如果鏈表中無(wú)此節(jié)點(diǎn)的對(duì)象則返回-1
int index = list.lastIndexOf('hello3');
System.out.println('返回節(jié)點(diǎn)對(duì)象element在鏈表中最后出現(xiàn)的位置：'+index);

結(jié)果
返回節(jié)點(diǎn)對(duì)象element在鏈表中最后出現(xiàn)的位置：2

public Object set(int index,Object element)

將當(dāng)前鏈表index位置節(jié)點(diǎn)中的對(duì)象替換成參數(shù)element指定的對(duì)象，返回被替換對(duì)象

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
// 將當(dāng)前鏈表index位置節(jié)點(diǎn)中的對(duì)象替換成參數(shù)element指定的對(duì)象，返回被替換對(duì)象
list.set(1,'我把索引為1的值改變了');
System.out.println('替換鏈表中索引為1的值：'+list.get(1));

結(jié)果
替換鏈表中索引為1的值：我把索引為1的值改變了

public int size()

返回鏈表的長(zhǎng)度即節(jié)點(diǎn)個(gè)數(shù)

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
System.out.println('鏈表中的元素?cái)?shù)量為：'+list.size());

結(jié)果
鏈表中的元素?cái)?shù)量為：4

public boolean contains(Object element)

判斷鏈表節(jié)點(diǎn)對(duì)象中是否含有element

LinkedList list = new LinkedList<>();
list.add('hello1');
list.add('hello2');
list.add('hello3');
list.add('hello4');
//判斷鏈表節(jié)點(diǎn)對(duì)象中是否含有element
System.out.println('hello2是否在鏈表中存在：'+list.contains('hello2'));

結(jié)果
hello2是否在鏈表中存在：true

ArrayList/Vector/LinkedList原理總結(jié)

ArrayList:

1、實(shí)現(xiàn)原理，采用了動(dòng)態(tài)對(duì)象數(shù)組實(shí)現(xiàn)，默認(rèn)構(gòu)造函數(shù)創(chuàng)建了一個(gè)空的對(duì)象數(shù)組

2、第一次添加元素，擴(kuò)展了10個(gè)位置的容量。

3、擴(kuò)充算法，原來(lái)數(shù)組的大小+原來(lái)數(shù)組大小的一半

4、不適合進(jìn)行刪除或插入操作

5、為了防止數(shù)組動(dòng)態(tài)擴(kuò)充次數(shù)較多，建議大家創(chuàng)建ArrayList的時(shí)候給定默認(rèn)初始容量

6、線程不安全，適合單線程訪問(wèn)時(shí)使用。

Vector:

1、實(shí)現(xiàn)原理，采用了動(dòng)態(tài)對(duì)象數(shù)組實(shí)現(xiàn)，默認(rèn)構(gòu)造函數(shù)創(chuàng)建了一個(gè)大小為10的對(duì)象數(shù)組

2、擴(kuò)充算法，當(dāng)增量為0時(shí)，擴(kuò)充為原來(lái)容量的2倍，當(dāng)增量大小大于0時(shí)，擴(kuò)充為原來(lái)的大小+增量大小

3、不適合進(jìn)行刪除或插入操作

4、線程安全，適合在多線程訪問(wèn)時(shí)使用，效率較低。

LinkedList:

1、實(shí)現(xiàn)原理，使用雙向列表結(jié)構(gòu)實(shí)現(xiàn)。

2、適合插入，或者修改，性能高

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自：太極混元天尊 > 《學(xué)習(xí)資料》

舉報(bào)/認(rèn)領(lǐng)