當前位置：首頁 > 编程语言 > java >内容正文

java

java linkedlist源码_Java集合之LinkedList源码分析

發布時間：2024/10/6 java 31 豆豆

生活随笔收集整理的這篇文章主要介紹了 java linkedlist源码_Java集合之LinkedList源码分析小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

一、LinkedList簡介

LinkedList是一種可以在任何位置進行高效地插入和移除操作的有序序列，它是基于雙向鏈表實現的。

ps:這里有一個問題，就是關于實現LinkedList的數據結構是否為循環的雙向鏈表，上網搜了有很多文章都說是循環的，并且有的文章中但是我看了源代碼覺得應該不是循環的？

例如在刪除列表尾部節點的代碼：

private E unlinkLast(Nodel)

{

final E element =l.item;final Node prev =l.prev;

l.item= null;

l.prev= null; //help GC

last =prev;if (prev == null)

first= null;elseprev.next= null;

size--;

modCount++;returnelement;

}

這里刪除尾節點l后，將l前面的節點prev的next置為null，而并沒有指向head節點。不知道是不是因為代碼版本的原因(我的源代碼是在下載的jdk1.8.0_45文件中獲取的)，如果讀者看到知道原因，希望能夠幫忙解答！

在源碼中定義了節點的基本結構：

private static class Node{

E item;//表示該節點包含的值

Node next; //表達當前節點的下一個節點

Node prev; //表示當前節點的上一個節點

Node(Node prev, E element, Nodenext) {this.item =element;this.next =next;this.prev =prev;

}

LinkedList的類圖如下所示：

LinkedList?是一個繼承于AbstractSequentialList的雙向鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作。

LinkedList?實現?List?接口，能對它進行隊列操作。

LinkedList?實現?Deque?接口，即能將LinkedList當作雙端隊列使用。

LinkedList?實現了Cloneable接口，即覆蓋了函數clone()，能克隆。

LinkedList?實現java.io.Serializable接口，這意味著LinkedList支持序列化，能通過序列化去傳輸。

LinkedList?是非同步的。

二、LinkedList源碼分析

1 public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable2 {3 //實現Serilizable接口時，將不需要序列化的屬性前添加關鍵字transient，序列化對象的時候，這個屬性就不會序列化到指定的目的地中。

4 transient int size = 0;5 //指向首節點

6 transient Nodefirst;7 //指向最后一個節點

8 transient Nodelast;9 //構建一個空列表

10 publicLinkedList() {11 }12 //構建一個包含集合c的列表

13 public LinkedList(Collection extends E>c) {14 this();15 addAll(c);16 }17 //將節點值為e的節點作為首節點

18 private voidlinkFirst(E e) {19 final Node f =first;20 //構建一個prev值為null,next為f,節點值為e的節點

21 final Node newNode = new Node<>(null, e, f);22 //將newNode作為首節點

23 first =newNode;24 //如果newNode后面沒有節點就將newNode作為最后一個節點

25 if (f == null)26 last =newNode;27 //否則就將newNode賦給其prev

28 else

29 f.prev =newNode;30 //列表長度加一

31 size++;32 modCount++;33 }34 //將節點值為e的節點作為最后一個節點

35 voidlinkLast(E e) {36 final Node l =last;37 //構建一個prev值為l,next為null,節點值為e的節點

38 final Node newNode = new Node<>(l, e, null);39 last =newNode;40 if (l == null)41 first =newNode;42 else

43 l.next =newNode;44 size++;45 modCount++;46 }47 //在非空節點succ之前插入節點e

48 void linkBefore(E e, Nodesucc) {49 final Node pred =succ.prev;50 //將succ前面的節點和succ作為其prev和next

51 final Node newNode = new Node<>(pred, e, succ);52 //然后將newNode作為succ的prev

53 succ.prev =newNode;54 //如果原來succ是首節點，則將newNode設置為首節點

55 if (pred == null)56 first =newNode;57 else

58 pred.next =newNode;59 size++;60 modCount++;61 }62 //釋放非空的首節點f

63 private E unlinkFirst(Nodef) {64 final E element =f.item;65 final Node next =f.next;66 f.item = null;67 f.next = null; //help GC68 //將first節點后面的節點設為首節點

69 first =next;70 if (next == null)71 last = null;72 else

73 next.prev = null;74 size--;75 modCount++;76 returnelement;77 }78 //釋放非空的尾節點l

79 private E unlinkLast(Nodel) {80 final E element =l.item;81 final Node prev =l.prev;82 l.item = null;83 l.prev = null; //help GC

84 last =prev;85 if (prev == null)86 first = null;87 else

88 prev.next = null;89 size--;90 modCount++;91 returnelement;92 }93 //刪除非空節點x

94 E unlink(Nodex)95 {96 final E element =x.item;97 final Node next = x.next; //x后面的節點

98 final Node prev = x.prev; //x前面的節點

100 if (prev == null) {101 first =next;102 } else{103 prev.next =next;104 x.prev = null;105 }106 if (next == null) {107 last =prev;108 } else{109 next.prev =prev;110 x.next = null;111 }112 x.item = null;113 size--;114 modCount++;115 returnelement;116 }117 //返回列表首節點元素值

118 publicE getFirst() {119 final Node f =first;120 if (f == null)121 throw newNoSuchElementException();122 returnf.item;123 }124 //返列表尾節點元素值

125 publicE getLast() {126 final Node l =last;127 if (l == null)128 throw newNoSuchElementException();129 returnl.item;130 }131 //移除首節點

132 publicE removeFirst() {133 final Node f =first;134 if (f == null)135 throw newNoSuchElementException();136 returnunlinkFirst(f);137 }138 //刪除尾節點

139 publicE removeLast() {140 final Node l =last;141 if (l == null)142 throw newNoSuchElementException();143 returnunlinkLast(l);144 }145 //在列表首部插入節點e

146 public voidaddFirst(E e) {147 linkFirst(e);148 }149 //在列表尾部插入節點e

150 public voidaddLast(E e) {151 linkLast(e);152 }153 //判斷列表中是否包含有元素o

154 public booleancontains(Object o) {155 return indexOf(o) != -1;156 }157 //返回列表長度大小

158 public intsize() {159 returnsize;160 }161 //在列表尾部插入元素

162 public booleanadd(E e) {163 linkLast(e);164 return true;165 }166 //刪除元素為o的節點

167 public booleanremove(Object o)168 {169 if (o == null) {170 for (Node x = first; x != null; x =x.next) {171 if (x.item == null) {172 unlink(x);173 return true;174 }175 }176 } else{177 for (Node x = first; x != null; x =x.next) {178 if(o.equals(x.item)) {179 unlink(x);180 return true;181 }182 }183 }184 return false;185 }186 //將集合c中所有元素添加到列表的尾部

187 public boolean addAll(Collection extends E>c) {188 returnaddAll(size, c);189 }190 //從指定的位置index開始，將集合c中的元素插入到列表中

191 public boolean addAll(int index, Collection extends E>c) {192 //首先判斷插入位置的合法性

193 checkPositionIndex(index);194 Object[] a =c.toArray();195 int numNew =a.length;196 if (numNew == 0)197 return false;198 Nodepred, succ;199 if (index == size) {//說明在列表尾部插入集合元素

200 succ = null;201 pred =last;202 }203 else { //否則，找到index所在的節點

204 succ =node(index);205 pred =succ.prev;206 }207 for(Object o : a) {208 @SuppressWarnings("unchecked") E e =(E) o;209 Node newNode = new Node<>(pred, e, null);210 if (pred == null)211 first =newNode;212 else

213 pred.next =newNode;214 pred =newNode;215 }216 if (succ == null) {217 last =pred;218 } else{219 pred.next =succ;220 succ.prev =pred;221 }222 size +=numNew;223 modCount++;224 return true;225 }226 //刪除列表中所有節點

227 public voidclear() {228 for (Node x = first; x != null; )229 {230 Node next =x.next;231 x.item = null;232 x.next = null;233 x.prev = null;234 x =next;235 }236 first = last = null;237 size = 0;238 modCount++;239 }240 //獲取指定索引位置節點的元素值

241 public E get(intindex) {242 checkElementIndex(index);243 returnnode(index).item;244 }245 //替換指定索引位置節點的元素值

246 public E set(intindex, E element) {247 checkElementIndex(index);248 Node x =node(index);249 E oldVal =x.item;250 x.item =element;251 returnoldVal;252 }253 //在指定索引位置之前插入元素e

254 public void add(intindex, E element) {255 checkPositionIndex(index);256 if (index ==size)257 linkLast(element);258 else

259 linkBefore(element, node(index));260 }261 //刪除指定位置的元素

262 public E remove(intindex) {263 checkElementIndex(index);264 returnunlink(node(index));265 }266 //判斷指定索引位置的元素是否存在

267 private boolean isElementIndex(intindex) {268 return index >= 0 && index = 0 && index <=size;272 }273 //構建 IndexOutOfBoundsException詳細信息

274 private String outOfBoundsMsg(intindex) {275 return "Index: "+index+", Size: "+size;276 }277 private void checkElementIndex(intindex) {278 if (!isElementIndex(index))279 throw newIndexOutOfBoundsException(outOfBoundsMsg(index));280 }281 private void checkPositionIndex(intindex) {282 if (!isPositionIndex(index))283 throw newIndexOutOfBoundsException(outOfBoundsMsg(index));284 }285 //返回指定索引位置的節點

286 Node node(intindex) {287 //此處是一個小技巧，當index

288 if (index < (size >> 1)) {289 Node x =first;290 for (int i = 0; i < index; i++)291 x =x.next;292 returnx;293 } else{294 Node x =last;295 for (int i = size - 1; i > index; i--)296 x =x.prev;297 returnx;298 }299 }//返回列表中第一次出現o的位置，若不存在則返回-1

300 public intindexOf(Object o) {301 int index = 0;302 if (o == null) {303 for (Node x = first; x != null; x =x.next) {304 if (x.item == null)305 returnindex;306 index++;307 }308 } else{309 for (Node x = first; x != null; x =x.next) {310 if(o.equals(x.item))311 returnindex;312 index++;313 }314 }315 return -1;316 }317 //逆向搜索，返回第一出現o的位置，不存在則返回-1

318 public intlastIndexOf(Object o) {319 int index =size;320 if (o == null) {321 for (Node x = last; x != null; x =x.prev) {322 index--;323 if (x.item == null)324 returnindex;325 }326 } else{327 for (Node x = last; x != null; x =x.prev) {328 index--;329 if(o.equals(x.item))330 returnindex;331 }332 }333 return -1;334 }335 //獲取列表首節點元素值

336 publicE peek() {337 final Node f =first;338 return (f == null) ? null: f.item;339 }340

341 //獲取列表首節點元素值，若為空則拋異常

342 publicE element() {343 returngetFirst();344 }345 //檢索首節點，若空則返回null,不為空則返回其元素值并刪除首節點

346 publicE poll() {347 final Node f =first;348 return (f == null) ? null: unlinkFirst(f);349 }350 //檢索首節點，若空則拋異常,不為空則返回其元素值并刪除首節點

351 publicE remove() {352 returnremoveFirst();353 }354 //在列表尾部增加節點e

355 public booleanoffer(E e) {356 returnadd(e);357 }358 //在列表首部插入節點e

359 public booleanofferFirst(E e) {360 addFirst(e);361 return true;362 }363 //在列表尾部插入節點e

364 public booleanofferLast(E e) {365 addLast(e);366 return true;367 }368 publicE peekFirst() {369 final Node f =first;370 return (f == null) ? null: f.item;371 }372 //獲取列表尾節點元素值

373 publicE peekLast() {374 final Node l =last;375 return (l == null) ? null: l.item;376 }377 publicE pollFirst() {378 final Node f =first;379 return (f == null) ? null: unlinkFirst(f);380 }381 publicE pollLast() {382 final Node l =last;383 return (l == null) ? null: unlinkLast(l);384 }385 //入棧

386 public voidpush(E e)387 {388 addFirst(e);389 }390 //出棧

391 publicE pop() {392 returnremoveFirst();393 }394 //刪除列表中第一出現o的節點

395 public booleanremoveFirstOccurrence(Object o) {396 returnremove(o);397 }398 //逆向搜索，刪除第一次出現o的節點

399 public booleanremoveLastOccurrence(Object o) {400 if (o == null) {401 for (Node x = last; x != null; x =x.prev) {402 if (x.item == null) {403 unlink(x);404 return true;405 }406 }407 } else{408 for (Node x = last; x != null; x =x.prev) {409 if(o.equals(x.item)) {410 unlink(x);411 return true;412 }413 }414 }415 return false;416 }

三、關于LinkedList的幾點說明

1、注意源碼中的?Node node(int index)方法：

Node node(intindex)

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

{

Node x =first;for (int i = 0; i < index; i++)

x=x.next;returnx;

}else{

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

x=x.prev;returnx;

}

該方法返回雙向鏈表中指定位置處的節點，而鏈表中是沒有下標索引的，要指定位置出的元素，就要遍歷該鏈表，從源碼的實現中，我們看到這里有一個加速動作。源碼中先將index與長度size的一半比較，如果indexsize/2，就只從位置size往前遍歷到位置index處。這樣可以減少一部分不必要的遍歷。

2、LinkedList與ArrayList的區別：

LinkedList與ArrayList在性能上各有優缺點，都有各自適用的地方，總結如下：

ArrayList是實現了基于動態數組的數據結構，LinkedList基于鏈表的數據結構。

LinkedList不支持高效的隨機元素訪問。

ArrayList的空間浪費主要體現在在list列表的結尾預留一定的容量空間，而LinkedList的空間花費則體現在它的每一個元素都需要消耗相當的空間，就存儲密度來說，ArrayList是優于LinkedList的。

總之，當操作是在一列數據的后面添加數據而不是在前面或中間,并且需要隨機地訪問其中的元素時,使用ArrayList會提供比較好的性能，當你的操作是在一列數據的前面或中間添加或刪除數據,并且按照順序訪問其中的元素時,就應該使用LinkedList了。

3、LinkedList中允許元素為null

在查找和刪除時，源代碼如下所示：

public intindexOf(Object o) {int index = 0;if (o == null) {for (Node x = first; x != null; x =x.next) {if (x.item == null)returnindex;

index++;

}

}else{for (Node x = first; x != null; x =x.next) {if(o.equals(x.item))returnindex;

index++;

}

}return -1;

}

4、利用LinkedList實現棧操作

public class Stack{private LinkedListstack;//無參構造函數

publicStack()

{

stack=new LinkedList();

}//構造一個包含指定collection中所有元素的棧

public Stack(Collection extends T>c)

{

stack=new LinkedList(c);

}//入棧

public voidpush(T t)

{

stack.addFirst(t);

}//出棧

publicT pull()

{returnstack.remove();

}//棧是否為空

booleanisEmpty()

{returnstack.isEmpty();

}//打印棧元素

public voiddisplay()

{for(Object o:stack)

System.out.println(o);

}

5、LinkedList的基本用法：

總結

以上是生活随笔為你收集整理的java linkedlist源码_Java集合之LinkedList源码分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： java判断字符串有中文_JAVA入门之
下一篇： java redis释放连接_redis