Java 集合系列 04 LinkedList详细介绍(源码解析)和使用示例
2020-11-18 09:19
阅读：722
标签：des com http blog style class div img code java size
java 集合系列目录：
Java 集合系列 01 总体框架
Java 集合系列 02 Collection架构
Java 集合系列 03 ArrayList详细介绍(源码解析)和使用示例
Java 集合系列 04 LinkedList详细介绍(源码解析)和使用示例
概要
和学习ArrayList一样，接下来呢，我们先对LinkedList有个整体认识，然后再学习它的源码；最后再通过实例来学会使用LinkedList。内容包括：
第1部分
LinkedList介绍
第2部分 LinkedList数据结构
第3部分 LinkedList源码解析(基于JDK1.7)
第4部分
LinkedList遍历方式
第5部分 LinkedList示例
第1部分 LinkedList介绍
LinkedList简介
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
LinkedList 实现 List 接口，能对它进行队列操作。
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList 是非同步的。
LinkedList构造函数
// 默认构造函数 LinkedList() // 创建一个LinkedList，保护Collection中的全部元素。 LinkedList(Collection extends E> collection)
LinkedList的API
LinkedList的API boolean add(E object) void add(int location, E object) boolean addAll(Collection extends E> collection) boolean addAll(int location, Collection extends E> collection) void addFirst(E object) void addLast(E object) void clear() Object clone() boolean contains(Object object) IteratordescendingIterator() E element() E get(int location) E getFirst() E getLast() int indexOf(Object object) int lastIndexOf(Object object) ListIterator listIterator(int location) boolean offer(E o) boolean offerFirst(E e) boolean offerLast(E e) E peek() E peekFirst() E peekLast() E poll() E pollFirst() E pollLast() E pop() void push(E e) E remove() E remove(int location) boolean remove(Object object) E removeFirst() boolean removeFirstOccurrence(Object o) E removeLast() boolean removeLastOccurrence(Object o) E set(int location, E object) int size() T[] toArray(T[] contents) Object[] toArray()
AbstractSequentialList简介
在介绍LinkedList的源码之前，先介绍一下AbstractSequentialList。毕竟，LinkedList是AbstractSequentialList的子类。
AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的，LinkedList是双向链表；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。
此外，我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。
第2部分 LinkedList数据结构
LinkedList的继承关系
java.lang.Object ? java.util.AbstractCollection? java.util.AbstractList ? java.util.AbstractSequentialList ? java.util.LinkedList public class LinkedList extends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable {}
LinkedList与Collection关系如下图：
LinkedList的本质是双向链表。
(01)
LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
(02)
LinkedList包含两个重要的成员：header 和 size。
header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量：
previous, next,
element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
size是双向链表中节点的个数。
第3部分 LinkedList源码解析(基于JDK1.7)
为了更了解LinkedList的原理，下面对LinkedList源码代码作出分析。
在阅读源码之前，我们先对LinkedList的整体实现进行大致说明：
LinkedList实际上是通过双向链表去实现的。既然是双向链表，那么它的顺序访问会非常高效，而随机访问效率比较低。
既然LinkedList是通过双向链表的，但是它也实现了List接口{也就是说，它实现了get(int
location)、remove(int
location)等“根据索引值来获取、删除节点的函数”}。LinkedList是如何实现List的这些接口的，如何将“双向链表和索引值联系起来的”？
实际原理非常简单，它就是通过一个计数索引值来实现的。例如，当我们调用get(int
location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置。
这就是“双线链表和索引值联系起来”的方法。
好了，接下来开始阅读源码(只要理解双向链表，那么LinkedList的源码很容易理解的)。
有关LinkedList在JDK1.6和JDK1.7的区别以及优化，参看 JDK1.7-LinkedList循环链表优化，这里列出是1.7的源码
其中 Node：
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
1 public class LinkedList2 extends AbstractSequentialList 3 implements List , Deque , Cloneable, java.io.Serializable 4 { 5 transient int size = 0; 6 7 /** 8 * Pointer to first node. 9 * Invariant: (first == null && last == null) || 10 * (first.prev == null && first.item != null) 11 */ 12 transient Node first; 13 14 /** 15 * Pointer to last node. 16 * Invariant: (first == null && last == null) || 17 * (last.next == null && last.item != null) 18 */ 19 transient Node last; 20 21 /** 22 * Constructs an empty list. 23 */ 24 public LinkedList() { 25 } 26 27 /** 28 * Constructs a list containing the elements of the specified 29 * collection, in the order they are returned by the collection‘s 30 * iterator. 31 * 32 * @param c the collection whose elements are to be placed into this list 33 * @throws NullPointerException if the specified collection is null 34 */ 35 public LinkedList(Collection extends E> c) { 36 this(); 37 addAll(c); 38 } 39 40 /** 41 * Links e as first element. 42 */ 43 private void linkFirst(E e) { 44 final Node f = first; 45 final Node newNode = new Node(null, e, f); 46 first = newNode; 47 if (f == null) 48 last = newNode; 49 else 50 f.prev = newNode; 51 size++; 52 modCount++; 53 } 54 55 /** 56 * Links e as last element. 57 */ 58 void linkLast(E e) { 59 final Node l = last; 60 final Node newNode = new Node(l, e, null); 61 last = newNode; 62 if (l == null) 63 first = newNode; 64 else 65 l.next = newNode; 66 size++; 67 modCount++; 68 } 69 70 /** 71 * Inserts element e before non-null Node succ. 72 */ 73 void linkBefore(E e, Node succ) { 74 // assert succ != null; 75 final Node pred = succ.prev; 76 final Node newNode = new Node(pred, e, succ); 77 succ.prev = newNode; 78 if (pred == null) 79 first = newNode; 80 else 81 pred.next = newNode; 82 size++; 83 modCount++; 84 } 85 86 /** 87 * Unlinks non-null first node f. 88 */ 89 private E unlinkFirst(Node f) { 90 // assert f == first && f != null; 91 final E element = f.item; 92 final Node next = f.next; 93 f.item = null; 94 f.next = null; // help GC 95 first = next; 96 if (next == null) 97 last = null; 98 else 99 next.prev = null; 100 size--; 101 modCount++; 102 return element; 103 } 104 105 /** 106 * Unlinks non-null last node l. 107 */ 108 private E unlinkLast(Node l) { 109 // assert l == last && l != null; 110 final E element = l.item; 111 final Node prev = l.prev; 112 l.item = null; 113 l.prev = null; // help GC 114 last = prev; 115 if (prev == null) 116 first = null; 117 else 118 prev.next = null; 119 size--; 120 modCount++; 121 return element; 122 } 123 124 /** 125 * Unlinks non-null node x. 126 */ 127 E unlink(Node x) { 128 // assert x != null; 129 final E element = x.item; 130 final Node next = x.next; 131 final Node prev = x.prev; 132 133 if (prev == null) { 134 first = next; 135 } else { 136 prev.next = next; 137 x.prev = null; 138 } 139 140 if (next == null) { 141 last = prev; 142 } else { 143 next.prev = prev; 144 x.next = null; 145 } 146 147 x.item = null; 148 size--; 149 modCount++; 150 return element; 151 } 152 153 /** 154 * Returns the first element in this list. 155 * 156 * @return the first element in this list 157 * @throws NoSuchElementException if this list is empty 158 */ 159 public E getFirst() { 160 final Node f = first; 161 if (f == null) 162 throw new NoSuchElementException(); 163 return f.item; 164 } 165 166 /** 167 * Returns the last element in this list. 168 * 169 * @return the last element in this list 170 * @throws NoSuchElementException if this list is empty 171 */ 172 public E getLast() { 173 final Node l = last; 174 if (l == null) 175 throw new NoSuchElementException(); 176 return l.item; 177 } 178 179 /** 180 * Removes and returns the first element from this list. 181 * 182 * @return the first element from this list 183 * @throws NoSuchElementException if this list is empty 184 */ 185 public E removeFirst() { 186 final Node f = first; 187 if (f == null) 188 throw new NoSuchElementException(); 189 return unlinkFirst(f); 190 } 191 192 /** 193 * Removes and returns the last element from this list. 194 * 195 * @return the last element from this list 196 * @throws NoSuchElementException if this list is empty 197 */ 198 public E removeLast() { 199 final Node l = last; 200 if (l == null) 201 throw new NoSuchElementException(); 202 return unlinkLast(l); 203 } 204 205 /** 206 * Inserts the specified element at the beginning of this list. 207 * 208 * @param e the element to add 209 */ 210 public void addFirst(E e) { 211 linkFirst(e); 212 } 213 214 /** 215 * Appends the specified element to the end of this list. 216 * 217 * This method is equivalent to {
@link #add}. 218 * 219 * @param e the element to add 220 */ 221 public void addLast(E e) { 222 linkLast(e); 223 } 224 225 /** 226 * Returns {@code true} if this list contains the specified element. 227 * More formally, returns {@code true} if and only if this list contains 228 * at least one element {@code e} such that 229 * (o==null ? e==null : o.equals(e)). 230 * 231 * @param o element whose presence in this list is to be tested 232 * @return {@code true} if this list contains the specified element 233 */ 234 public boolean contains(Object o) { 235 return indexOf(o) != -1; 236 } 237 238 /** 239 * Returns the number of elements in this list. 240 * 241 * @return the number of elements in this list 242 */ 243 public int size() { 244 return size; 245 } 246 247 /** 248 * Appends the specified element to the end of this list. 249 * 250 *This method is equivalent to {
@link #addLast}. 251 * 252 * @param e element to be appended to this list 253 * @return {@code true} (as specified by {@link Collection#add}) 254 */ 255 public boolean add(E e) { 256 linkLast(e); 257 return true; 258 } 259 260 /** 261 * Removes the first occurrence of the specified element from this list, 262 * if it is present. If this list does not contain the element, it is 263 * unchanged. More formally, removes the element with the lowest index 264 * {@code i} such that 265 * (o==null ? get(i)==null : o.equals(get(i))) 266 * (if such an element exists). Returns {@code true} if this list 267 * contained the specified element (or equivalently, if this list 268 * changed as a result of the call). 269 * 270 * @param o element to be removed from this list, if present 271 * @return {@code true} if this list contained the specified element 272 */ 273 public boolean remove(Object o) { 274 if (o == null) { 275 for (Nodex = first; x != null; x = x.next) { 276 if (x.item == null) { 277 unlink(x); 278 return true; 279 } 280 } 281 } else { 282 for (Node x = first; x != null; x = x.next) { 283 if (o.equals(x.item)) { 284 unlink(x); 285 return true; 286 } 287 } 288 } 289 return false; 290 } 291 292 /** 293 * Appends all of the elements in the specified collection to the end of 294 * this list, in the order that they are returned by the specified 295 * collection‘s iterator. The behavior of this operation is undefined if 296 * the specified collection is modified while the operation is in 297 * progress. (Note that this will occur if the specified collection is 298 * this list, and it‘s nonempty.) 299 * 300 * @param c collection containing elements to be added to this list 301 * @return {@code true} if this list changed as a result of the call 302 * @throws NullPointerException if the specified collection is null 303 */ 304 public boolean addAll(Collection extends E> c) { 305 return addAll(size, c); 306 } 307 308 /** 309 * Inserts all of the elements in the specified collection into this 310 * list, starting at the specified position. Shifts the element 311 * currently at that position (if any) and any subsequent elements to 312 * the right (increases their indices). The new elements will appear 313 * in the list in the order that they are returned by the 314 * specified collection‘s iterator. 315 * 316 * @param index index at which to insert the first element 317 * from the specified collection 318 * @param c collection containing elements to be added to this list 319 * @return {@code true} if this list changed as a result of the call 320 * @throws IndexOutOfBoundsException {@inheritDoc} 321 * @throws NullPointerException if the specified collection is null 322 */ 323 public boolean addAll(int index, Collection extends E> c) { 324 checkPositionIndex(index); 325 326 Object[] a = c.toArray(); 327 int numNew = a.length; 328 if (numNew == 0) 329 return false; 330 331 Node pred, succ; 332 if (index == size) { 333 succ = null; 334 pred = last; 335 } else { 336 succ = node(index); 337 pred = succ.prev; 338 } 339 340 for (Object o : a) { 341 @SuppressWarnings("unchecked") E e = (E) o; 342 Node newNode = new Node(pred, e, null); 343 if (pred == null) 344 first = newNode; 345 else 346 pred.next = newNode; 347 pred = newNode; 348 } 349 350 if (succ == null) { 351 last = pred; 352 } else { 353 pred.next = succ; 354 succ.prev = pred; 355 } 356 357 size += numNew; 358 modCount++; 359 return true; 360 } 361 362 /** 363 * Removes all of the elements from this list. 364 * The list will be empty after this call returns. 365 */ 366 public void clear() { 367 // Clearing all of the links between nodes is "unnecessary", but: 368 // - helps a generational GC if the discarded nodes inhabit 369 // more than one generation 370 // - is sure to free memory even if there is a reachable Iterator 371 for (Node x = first; x != null; ) { 372 Node next = x.next; 373 x.item = null; 374 x.next = null; 375 x.prev = null; 376 x = next; 377 } 378 first = last = null; 379 size = 0; 380 modCount++; 381 } 382 383 384 // Positional Access Operations 385 386 /** 387 * Returns the element at the specified position in this list. 388 * 389 * @param index index of the element to return 390 * @return the element at the specified position in this list 391 * @throws IndexOutOfBoundsException {@inheritDoc} 392 */ 393 public E get(int index) { 394 checkElementIndex(index); 395 return node(index).item; 396 } 397 398 /** 399 * Replaces the element at the specified position in this list with the 400 * specified element. 401 * 402 * @param index index of the element to replace 403 * @param element element to be stored at the specified position 404 * @return the element previously at the specified position 405 * @throws IndexOutOfBoundsException {@inheritDoc} 406 */ 407 public E set(int index, E element) { 408 checkElementIndex(index); 409 Node x = node(index); 410 E oldVal = x.item; 411 x.item = element; 412 return oldVal; 413 } 414 415 /** 416 * Inserts the specified element at the specified position in this list. 417 * Shifts the element currently at that position (if any) and any 418 * subsequent elements to the right (adds one to their indices). 419 * 420 * @param index index at which the specified element is to be inserted 421 * @param element element to be inserted 422 * @throws IndexOutOfBoundsException {@inheritDoc} 423 */ 424 public void add(int index, E element) { 425 checkPositionIndex(index); 426 427 if (index == size) 428 linkLast(element); 429 else 430 linkBefore(element, node(index)); 431 } 432 433 /** 434 * Removes the element at the specified position in this list. Shifts any 435 * subsequent elements to the left (subtracts one from their indices). 436 * Returns the element that was removed from the list. 437 * 438 * @param index the index of the element to be removed 439 * @return the element previously at the specified position 440 * @throws IndexOutOfBoundsException {@inheritDoc} 441 */ 442 public E remove(int index) { 443 checkElementIndex(index); 444 return unlink(node(index)); 445 } 446 447 /** 448 * Tells if the argument is the index of an existing element. 449 */ 450 private boolean isElementIndex(int index) { 451 return index >= 0 && index size; 452 } 453 454 /** 455 * Tells if the argument is the index of a valid position for an 456 * iterator or an add operation. 457 */ 458 private boolean isPositionIndex(int index) { 459 return index >= 0 && index size; 460 } 461 462 /** 463 * Constructs an IndexOutOfBoundsException detail message. 464 * Of the many possible refactorings of the error handling code, 465 * this "outlining" performs best with both server and client VMs. 466 */ 467 private String outOfBoundsMsg(int index) { 468 return "Index: "+index+", Size: "+size; 469 } 470 471 private void checkElementIndex(int index) { 472 if (!isElementIndex(index)) 473 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 474 } 475 476 private void checkPositionIndex(int index) { 477 if (!isPositionIndex(index)) 478 throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 479 } 480 481 /** 482 * Returns the (non-null) Node at the specified element index. 483 */ 484 Node node(int index) { 485 // assert isElementIndex(index); 486 487 if (index > 1)) { 488 Node x = first; 489 for (int i = 0; i ) 490 x = x.next; 491 return x; 492 } else { 493 Node x = last; 494 for (int i = size - 1; i > index; i--) 495 x = x.prev; 496 return x; 497 } 498 } 499 500 // Search Operations 501 502 /** 503 * Returns the index of the first occurrence of the specified element 504 * in this list, or -1 if this list does not contain the element. 505 * More formally, returns the lowest index {@code i} such that 506 * (o==null ? get(i)==null : o.equals(get(i))), 507 * or -1 if there is no such index. 508 * 509 * @param o element to search for 510 * @return the index of the first occurrence of the specified element in 511 * this list, or -1 if this list does not contain the element 512 */ 513 public int indexOf(Object o) { 514 int index = 0; 515 if (o == null) { 516 for (Node x = first; x != null; x = x.next) { 517 if (x.item == null) 518 return index; 519 index++; 520 } 521 } else { 522 for (Node x = first; x != null; x = x.next) { 523 if (o.equals(x.item)) 524 return index; 525 index++; 526 } 527 } 528 return -1; 529 } 530 531 /** 532 * Returns the index of the last occurrence of the specified element &l
文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Java 集合系列 04 LinkedList详细介绍(源码解析)和使用示例
文章链接：http://soscw.com/essay/21835.html
文章标题：Java 集合系列 04 LinkedList详细介绍(源码解析)和使用示例
文章链接：http://soscw.com/essay/21835.html
评论
亲，登录后才可以留言！