1 package java.util;
2
3 public class LinkedList<E> extends AbstractSequentialList<E> implements
4 List<E>, Deque<E>, Cloneable, java.io.Serializable {
5 /**
6 * header是鏈表的頭節點，但不用來存放實際的數據。
7 * header.next是鏈表的第一個元素，header.previous是最后一個元素，參見方法getFirst()和getLast()
8 */
9 private transient Entry<E> header = new Entry<E>(null, null, null);
10 /**
11 * size保存鏈表的長度
12 */
13 private transient int size = 0;
14
15 /**
16 * Constructs an empty list.
17 */
18 public LinkedList() {
19 // 初始化頭節點
20 header.next = header.previous = header;
21 }
22
23 /**
24 * Constructs a list containing the elements of the specified collection, in
25 * the order they are returned by the collection's iterator.
26 *
27 * @param c
28 * the collection whose elements are to be placed into this list
29 * @throws NullPointerException
30 * if the specified collection is null
31 */
32 public LinkedList(Collection<? extends E> c) {
33 // 先調用默認構造方法，再向鏈表中插入指定的元素
34 this();
35 addAll(c);
36 }
37
38 /**
39 * Returns the first element in this list.
40 *
41 * @return the first element in this list
42 * @throws NoSuchElementException
43 * if this list is empty
44 */
45 public E getFirst() {
46 if (size == 0)
47 throw new NoSuchElementException();
48
49 // 返回頭指針后繼元素的對象
50 return header.next.element;
51 }
52
53 /**
54 * Returns the last element in this list.
55 *
56 * @return the last element in this list
57 * @throws NoSuchElementException
58 * if this list is empty
59 */
60 public E getLast() {
61 if (size == 0)
62 throw new NoSuchElementException();
63
64 // 返回頭指針前驅元素的對象
65 return header.previous.element;
66 }
67
68 /**
69 * Removes and returns the first element from this list.
70 *
71 * @return the first element from this list
72 * @throws NoSuchElementException
73 * if this list is empty
74 */
75 public E removeFirst() {
76 return remove(header.next);
77 }
78
79 /**
80 * Removes and returns the last element from this list.
81 *
82 * @return the last element from this list
83 * @throws NoSuchElementException
84 * if this list is empty
85 */
86 public E removeLast() {
87 return remove(header.previous);
88 }
89
90 /**
91 * Inserts the specified element at the beginning of this list.
92 *
93 * @param e
94 * the element to add
95 */
96 public void addFirst(E e) {
97 // 插入在第一個元素之前
98 addBefore(e, header.next);
99 }
100
101 /**
102 * Appends the specified element to the end of this list.
103 *
104 * <p>
105 * This method is equivalent to {@link #add}.
106 *
107 * @param e
108 * the element to add
109 */
110 public void addLast(E e) {
111 // 插入在頭節點之前，即末尾元素之后
112 addBefore(e, header);
113 }
114
115 /**
116 * Returns <tt>true</tt> if this list contains the specified element. More
117 * formally, returns <tt>true</tt> if and only if this list contains at
118 * least one element <tt>e</tt> such that
119 * <tt>(o==null ? e==null : o.equals(e))</tt>.
120 *
121 * @param o
122 * element whose presence in this list is to be tested
123 * @return <tt>true</tt> if this list contains the specified element
124 */
125 public boolean contains(Object o) {
126 return indexOf(o) != -1;
127 }
128
129 /**
130 * Returns the number of elements in this list.
131 *
132 * @return the number of elements in this list
133 */
134 public int size() {
135 return size;
136 }
137
138 /**
139 * Appends the specified element to the end of this list.
140 *
141 * <p>
142 * This method is equivalent to {@link #addLast}.
143 *
144 * @param e
145 * element to be appended to this list
146 * @return <tt>true</tt> (as specified by {@link Collection#add})
147 */
148 public boolean add(E e) {
149 addBefore(e, header);
150 return true;
151 }
152
153 /**
154 * Removes the first occurrence of the specified element from this list, if
155 * it is present. If this list does not contain the element, it is
156 * unchanged. More formally, removes the element with the lowest index
157 * <tt>i</tt> such that
158 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
159 * (if such an element exists). Returns <tt>true</tt> if this list contained
160 * the specified element (or equivalently, if this list changed as a result
161 * of the call).
162 *
163 * @param o
164 * element to be removed from this list, if present
165 * @return <tt>true</tt> if this list contained the specified element
166 */
167 public boolean remove(Object o) {
168 if (o == null) {
169 // 從鏈表第一個元素開始遍歷
170 for (Entry<E> e = header.next; e != header; e = e.next) {
171 if (e.element == null) {
172 remove(e);
173 return true;
174 }
175 }
176 } else {
177 for (Entry<E> e = header.next; e != header; e = e.next) {
178 // 使用equals方法進行比較
179 if (o.equals(e.element)) {
180 remove(e);
181 return true;
182 }
183 }
184 }
185 return false;
186 }
187
188 /**
189 * Appends all of the elements in the specified collection to the end of
190 * this list, in the order that they are returned by the specified
191 * collection's iterator. The behavior of this operation is #ff0000 if the
192 * specified collection is modified while the operation is in progress.
193 * (Note that this will occur if the specified collection is this list, and
194 * it's nonempty.)
195 *
196 * @param c
197 * collection containing elements to be added to this list
198 * @return <tt>true</tt> if this list changed as a result of the call
199 * @throws NullPointerException
200 * if the specified collection is null
201 */
202 public boolean addAll(Collection<? extends E> c) {
203 return addAll(size, c);
204 }
205
206 /**
207 * Inserts all of the elements in the specified collection into this list,
208 * starting at the specified position. Shifts the element currently at that
209 * position (if any) and any subsequent elements to the right (increases
210 * their indices). The new elements will appear in the list in the order
211 * that they are returned by the specified collection's iterator.
212 *
213 * @param index
214 * index at which to insert the first element from the specified
215 * collection
216 * @param c
217 * collection containing elements to be added to this list
218 * @return <tt>true</tt> if this list changed as a result of the call
219 * @throws IndexOutOfBoundsException
220 * {@inheritDoc}
221 * @throws NullPointerException
222 * if the specified collection is null
223 */
224 public boolean addAll(int index, Collection<? extends E> c) {
225 if (index < 0 || index > size)
226 throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
227 + size);
228 Object[] a = c.toArray();
229 int numNew = a.length;
230 if (numNew == 0)
231 return false;
232 modCount++;
233
234 // index==size, 插在鏈表的末尾，即頭指針header之前；否則，插在指定元素之前
235 Entry<E> successor = (index == size ? header : entry(index));
236 Entry<E> predecessor = successor.previous;
237 for (int i = 0; i < numNew; i++) {
238 // 插入新元素
239 Entry<E> e = new Entry<E>((E) a[i], successor, predecessor);
240 // 修改前一元素的next指針
241 predecessor.next = e;
242 // 修改變量，準備下一次插入
243 predecessor = e;
244 }
245 // 修改插入位置元素的previous指針
246 successor.previous = predecessor;
247
248 size += numNew;
249 return true;
250 }
251
252 /**
253 * Removes all of the elements from this list.
254 */
255 public void clear() {
256 // 取鏈表第一個元素
257 Entry<E> e = header.next;
258 while (e != header) {
259 Entry<E> next = e.next;
260 // 刪除指針和元素
261 e.next = e.previous = null;
262 e.element = null;
263 // 修改循環變量
264 e = next;
265 }
266 // 恢復頭節點
267 header.next = header.previous = header;
268 size = 0;
269 modCount++;
270 }
271
272 // Positional Access Operations
273
274 /**
275 * Returns the element at the specified position in this list.
276 *
277 * @param index
278 * index of the element to return
279 * @return the element at the specified position in this list
280 * @throws IndexOutOfBoundsException
281 * {@inheritDoc}
282 */
283 public E get(int index) {
284 return entry(index).element;
285 }
286
287 /**
288 * Replaces the element at the specified position in this list with the
289 * specified element.
290 *
291 * @param index
292 * index of the element to replace
293 * @param element
294 * element to be stored at the specified position
295 * @return the element previously at the specified position
296 * @throws IndexOutOfBoundsException
297 * {@inheritDoc}
298 */
299 public E set(int index, E element) {
300 Entry<E> e = entry(index);
301 E oldVal = e.element;
302 e.element = element;
303 return oldVal;
304 }
305
306 /**
307 * Inserts the specified element at the specified position in this list.
308 * Shifts the element currently at that position (if any) and any subsequent
309 * elements to the right (adds one to their indices).
310 *
311 * @param index
312 * index at which the specified element is to be inserted
313 * @param element
314 * element to be inserted
315 * @throws IndexOutOfBoundsException
316 * {@inheritDoc}
317 */
318 public void add(int index, E element) {
319 // 插入指定位置之前
320 addBefore(element, (index == size ? header : entry(index)));
321 }
322
323 /**
324 * Removes the element at the specified position in this list. Shifts any
325 * subsequent elements to the left (subtracts one from their indices).
326 * Returns the element that was removed from the list.
327 *
328 * @param index
329 * the index of the element to be removed
330 * @return the element previously at the specified position
331 * @throws IndexOutOfBoundsException
332 * {@inheritDoc}
333 */
334 public E remove(int index) {
335 return remove(entry(index));
336 }
337
338 /**
339 * Returns the indexed entry.
340 */
341 private Entry<E> entry(int index) {
342 if (index < 0 || index >= size)
343 throw new IndexOutOfBoundsException("Index: " + index + ", Size: "
344 + size);
345 Entry<E> e = header;
346 // index小于size的一半，從首部開始遍歷
347 if (index < (size >> 1)) {
348 // index >= 0
349 for (int i = 0; i <= index; i++)
350 e = e.next;
351 }
352 // 否則，從尾部開始遍歷
353 else {
354 // index <= size-1
355 for (int i = size; i > index; i--)
356 e = e.previous;
357 }
358 return e;
359 }
360
361 // Search Operations
362
363 /**
364 * Returns the index of the first occurrence of the specified element in
365 * this list, or -1 if this list does not contain the element. More
366 * formally, returns the lowest index <tt>i</tt> such that
367 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
368 * or -1 if there is no such index.
369 *
370 * @param o
371 * element to search for
372 * @return the index of the first occurrence of the specified element in
373 * this list, or -1 if this list does not contain the element
374 */
375 // 參見函數 remove(Object o)
376 public int indexOf(Object o) {
377 int index = 0;
378 if (o == null) {
379 for (Entry e = header.next; e != header; e = e.next) {
380 if (e.element == null)
381 return index;
382 index++;
383 }
384 } else {
385 for (Entry e = header.next; e != header; e = e.next) {
386 if (o.equals(e.element))
387 return index;
388 index++;
389 }
390 }
391 return -1;
392 }
393
394 /**
395 * Returns the index of the last occurrence of the specified element in this
396 * list, or -1 if this list does not contain the element. More formally,
397 * returns the highest index <tt>i</tt> such that
398 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
399 * or -1 if there is no such index.
400 *
401 * @param o
402 * element to search for
403 * @return the index of the last occurrence of the specified element in this
404 * list, or -1 if this list does not contain the element
405 */
406 public int lastIndexOf(Object o) {
407 int index = size;
408 if (o == null) {
409 // 從鏈表的末尾開始遍歷
410 for (Entry e = header.previous; e != header; e = e.previous) {
411 index--;
412 if (e.element == null)
413 return index;
414 }
415 } else {
416 for (Entry e = header.previous; e != header; e = e.previous) {
417 index--;
418 if (o.equals(e.element))
419 return index;
420 }
421 }
422 return -1;
423 }
424
425 // Queue operations.
426
427 /**
428 * Retrieves, but does not remove, the head (first element) of this list.
429 *
430 * @return the head of this list, or <tt>null</tt> if this list is empty
431 * @since 1.5
432 */
433 public E peek() {
434 if (size == 0)
435 return null;
436 return getFirst();
437 }
438
439 /**
440 * Retrieves, but does not remove, the head (first element) of this list.
441 *
442 * @return the head of this list
443 * @throws NoSuchElementException
444 * if this list is empty
445 * @since 1.5
446 */
447 public E element() {
448 return getFirst();
449 }
450
451 /**
452 * Retrieves and removes the head (first element) of this list
453 *
454 * @return the head of this list, or <tt>null</tt> if this list is empty
455 * @since 1.5
456 */
457 public E poll() {
458 if (size == 0)
459 return null;
460 return removeFirst();
461 }
462
463 /**
464 * Retrieves and removes the head (first element) of this list.
465 *
466 * @return the head of this list
467 * @throws NoSuchElementException
468 * if this list is empty
469 * @since 1.5
470 */
471 public E remove() {
472 return removeFirst();
473 }
474
475 /**
476 * Adds the specified element as the tail (last element) of this list.
477 *
478 * @param e
479 * the element to add
480 * @return <tt>true</tt> (as specified by {@link Queue#offer})
481 * @since 1.5
482 */
483 public boolean offer(E e) {
484 return add(e);
485 }
486
487 // Deque operations
488 /**
489 * Inserts the specified element at the front of this list.
490 *
491 * @param e
492 * the element to insert
493 * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
494 * @since 1.6
495 */
496 public boolean offerFirst(E e) {
497 addFirst(e);
498 return true;
499 }
500
501 /**
502 * Inserts the specified element at the end of this list.
503 *
504 * @param e
505 * the element to insert
506 * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
507 * @since 1.6
508 */
509 public boolean offerLast(E e) {
510 addLast(e);
511 return true;
512 }
513
514 /**
515 * Retrieves, but does not remove, the first element of this list, or
516 * returns <tt>null</tt> if this list is empty.
517 *
518 * @return the first element of this list, or <tt>null</tt> if this list is
519 * empty
520 * @since 1.6
521 */
522 public E peekFirst() {
523 if (size == 0)
524 return null;
525 return getFirst();
526 }
527
528 /**
529 * Retrieves, but does not remove, the last element of this list, or returns
530 * <tt>null</tt> if this list is empty.
531 *
532 * @return the last element of this list, or <tt>null</tt> if this list is
533 * empty
534 * @since 1.6
535 */
536 public E peekLast() {
537 if (size == 0)
538 return null;
539 return getLast();
540 }
541
542 /**
543 * Retrieves and removes the first element of this list, or returns
544 * <tt>null</tt> if this list is empty.
545 *
546 * @return the first element of this list, or <tt>null</tt> if this list is
547 * empty
548 * @since 1.6
549 */
550 public E pollFirst() {
551 if (size == 0)
552 return null;
553 return removeFirst();
554 }
555
556 /**
557 * Retrieves and removes the last element of this list, or returns
558 * <tt>null</tt> if this list is empty.
559 *
560 * @return the last element of this list, or <tt>null</tt> if this list is
561 * empty
562 * @since 1.6
563 */
564 public E pollLast() {
565 if (size == 0)
566 return null;
567 return removeLast();
568 }
569
570 /**
571 * Pushes an element onto the stack represented by this list. In other
572 * words, inserts the element at the front of this list.
573 *
574 * <p>
575 * This method is equivalent to {@link #addFirst}.
576 *
577 * @param e
578 * the element to push
579 * @since 1.6
580 */
581 public void push(E e) {
582 addFirst(e);
583 }
584
585 /**
586 * Pops an element from the stack represented by this list. In other words,
587 * removes and returns the first element of this list.
588 *
589 * <p>
590 * This method is equivalent to {@link #removeFirst()}.
591 *
592 * @return the element at the front of this list (which is the top of the
593 * stack represented by this list)
594 * @throws NoSuchElementException
595 * if this list is empty
596 * @since 1.6
597 */
598 public E pop() {
599 return removeFirst();
600 }
601
602 /**
603 * Removes the first occurrence of the specified element in this list (when
604 * traversing the list from head to tail). If the list does not contain the
605 * element, it is unchanged.
606 *
607 * @param o
608 * element to be removed from this list, if present
609 * @return <tt>true</tt> if the list contained the specified element
610 * @since 1.6
611 */
612 public boolean removeFirstOccurrence(Object o) {
613 return remove(o);
614 }
615
616 /**
617 * Removes the last occurrence of the specified element in this list (when
618 * traversing the list from head to tail). If the list does not contain the
619 * element, it is unchanged.
620 *
621 * @param o
622 * element to be removed from this list, if present
623 * @return <tt>true</tt> if the list contained the specified element
624 * @since 1.6
625 */
626 public boolean removeLastOccurrence(Object o) {
627 if (o == null) {
628 for (Entry<E> e = header.previous; e != header; e = e.previous) {
629 if (e.element == null) {
630 remove(e);
631 return true;
632 }
633 }
634 } else {
635 for (Entry<E> e = header.previous; e != header; e = e.previous) {
636 if (o.equals(e.element)) {
637 remove(e);
638 return true;
639 }
640 }
641 }
642 return false;
643 }
644
645 /**
646 * Returns a list-iterator of the elements in this list (in proper
647 * sequence), starting at the specified position in the list. Obeys the
648 * general contract of <tt>List.listIterator(int)</tt>.
649 * <p>
650 *
651 * The list-iterator is <i>fail-fast</i>: if the list is structurally
652 * modified at any time after the Iterator is created, in any way except
653 * through the list-iterator's own <tt>remove</tt> or <tt>add</tt> methods,
654 * the list-iterator will throw a <tt>ConcurrentModificationException</tt>.
655 * Thus, in the face of concurrent modification, the iterator fails quickly
656 * and cleanly, rather than risking arbitrary, non-deterministic behavior at
657 * an undetermined time in the future.
658 *
659 * @param index
660 * index of the first element to be returned from the
661 * list-iterator (by a call to <tt>next</tt>)
662 * @return a ListIterator of the elements in this list (in proper sequence),
663 * starting at the specified position in the list
664 * @throws IndexOutOfBoundsException
665 * {@inheritDoc}
666 * @see List#listIterator(int)
667 */
668 public ListIterator<E> listIterator(int index) {
669 return new ListItr(index);
670 }
671
672 // 內部類實現ListIterator接口
673 private class ListItr implements ListIterator<E> {
674 private Entry<E> lastReturned = header;
675 private Entry<E> next;
676 private int nextIndex;
677 private int expectedModCount = modCount;
678
679 // index是第一個被next()返回的元素
680 ListItr(int index) {
681 if (index < 0 || index > size)
682 throw new IndexOutOfBoundsException("Index: " + index
683 + ", Size: " + size);
684 if (index < (size >> 1)) {
685 // next指向第0個元素
686 next = header.next;
687 // next指向第index個元素,nextIndex=index
688 for (nextIndex = 0; nextIndex < index; nextIndex++)
689 next = next.next;
690 } else {
691 // 指向頭節點
692 next = header;
693 for (nextIndex = size; nextIndex > index; nextIndex--)
694 next = next.previous;
695 }
696 }
697
698 public boolean hasNext() {
699 return nextIndex != size;
700 }
701
702 public E next() {
703 // 鏈表狀態是否一致？
704 checkForComodification();
705 if (nextIndex == size)
706 throw new NoSuchElementException();
707
708 // 記錄next元素，并準備返回
709 lastReturned = next;
710 next = next.next;
711 nextIndex++;
712 return lastReturned.element;
713 }
714
715 public boolean hasPrevious() {
716 return nextIndex != 0;
717 }
718
719 public E previous() {
720 if (nextIndex == 0)
721 throw new NoSuchElementException();
722
723 lastReturned = next = next.previous;
724 nextIndex--;
725 checkForComodification();
726 return lastReturned.element;
727 }
728
729 public int nextIndex() {
730 // 最大為size,當指向鏈表末尾的時候
731 return nextIndex;
732 }
733
734 public int previousIndex() {
735 // 最小為-1,當指向鏈表首部的時候
736 return nextIndex - 1;
737 }
738
739 public void remove() {
740 checkForComodification();
741 Entry<E> lastNext = lastReturned.next;
742 try {
743 // 刪除lastReturned元素
744 LinkedList.this.remove(lastReturned);
745 } catch (NoSuchElementException e) {
746 throw new IllegalStateException();
747 }
748 // 之前調用了 previous()方法
749 if (next == lastReturned)
750 next = lastNext;
751 else
752 // 之前調用了next()方法
753 nextIndex--;
754 // 修改lastReturned，保證只能remove一次
755 lastReturned = header;
756 expectedModCount++;
757 }
758
759 public void set(E e) {
760 if (lastReturned == header)
761 throw new IllegalStateException();
762 checkForComodification();
763 lastReturned.element = e;
764 }
765
766 // 插入在next()元素之前
767 public void add(E e) {
768 checkForComodification();
769 // 修改lastReturned，保證只能add一次
770 lastReturned = header;
771 addBefore(e, next);
772 // next()不會取得新加入的元素
773 nextIndex++;
774 expectedModCount++;
775 }
776
777 final void checkForComodification() {
778 if (modCount != expectedModCount)
779 throw new ConcurrentModificationException();
780 }
781 }
782
783 // 類似struct結構體，鏈表中的數據元素都是一個Entry對象
784 private static class Entry<E> {
785 E element;
786 Entry<E> next;
787 Entry<E> previous;
788
789 Entry(E element, Entry<E> next, Entry<E> previous) {
790 this.element = element;
791 this.next = next;
792 this.previous = previous;
793 }
794 }
795
796 // 私有輔助方法，添加元素到鏈表指定元素之前
797 private Entry<E> addBefore(E e, Entry<E> entry) {
798 Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);
799 newEntry.previous.next = newEntry;
800 newEntry.next.previous = newEntry;
801 size++;
802 modCount++;
803 return newEntry;
804 }
805
806 // 私有輔助方法，刪除一個鏈表元素
807 private E remove(Entry<E> e) {
808 if (e == header)
809 throw new NoSuchElementException();
810
811 E result = e.element;
812 // 修改前后元素的指針
813 e.previous.next = e.next;
814 e.next.previous = e.previous;
815 // 刪除當前元素
816 e.next = e.previous = null;
817 e.element = null;
818 size--;
819 modCount++;
820 return result;
821 }
822
823 /**
824 * @since 1.6
825 */
826 public Iterator<E> descendingIterator() {
827 return new DescendingIterator();
828 }
829
830 /** Adapter to provide descending iterators via ListItr.previous */
831 // Iterator接口的實現類，提供對鏈表的反向遍歷
832 private class DescendingIterator implements Iterator {
833 final ListItr itr = new ListItr(size());
834
835 public boolean hasNext() {
836 return itr.hasPrevious();
837 }
838
839 public E next() {
840 return itr.previous();
841 }
842
843 public void remove() {
844 itr.remove();
845 }
846 }
847
848 /**
849 * Returns a shallow copy of this <tt>LinkedList</tt>. (The elements
850 * themselves are not cloned.)
851 *
852 * @return a shallow copy of this <tt>LinkedList</tt> instance
853 */
854 public Object clone() {
855 LinkedList<E> clone = null;
856 try {
857 clone = (LinkedList<E>) super.clone();
858 } catch (CloneNotSupportedException e) {
859 throw new InternalError();
860 }
861
862 // Put clone into "virgin" state
863 // 初始化clone對象
864 clone.header = new Entry<E>(null, null, null);
865 clone.header.next = clone.header.previous = clone.header;
866 clone.size = 0;
867 clone.modCount = 0;
868
869 // Initialize clone with our elements
870 for (Entry<E> e = header.next; e != header; e = e.next)
871 clone.add(e.element);
872
873 // 返回的clone對象包括所有元素對象的引用
874 return clone;
875 }
876
877 /**
878 * Returns an array containing all of the elements in this list in proper
879 * sequence (from first to last element).
880 *
881 * <p>
882 * The returned array will be "safe" in that no references to it are
883 * maintained by this list. (In other words, this method must allocate a new
884 * array). The caller is thus free to modify the returned array.
885 *
886 * <p>
887 * This method acts as bridge between array-based and collection-based APIs.
888 *
889 * @return an array containing all of the elements in this list in proper
890 * sequence
891 */
892 public Object[] toArray() {
893 Object[] result = new Object[size];
894 int i = 0;
895 for (Entry<E> e = header.next; e != header; e = e.next)
896 result[i++] = e.element;
897 return result;
898 }
899
900 /**
901 * Returns an array containing all of the elements in this list in proper
902 * sequence (from first to last element); the runtime type of the returned
903 * array is that of the specified array. If the list fits in the specified
904 * array, it is returned therein. Otherwise, a new array is allocated with
905 * the runtime type of the specified array and the size of this list.
906 *
907 * <p>
908 * If the list fits in the specified array with room to spare (i.e., the
909 * array has more elements than the list), the element in the array
910 * immediately following the end of the list is set to <tt>null</tt>. (This
911 * is useful in determining the length of the list <i>only</i> if the caller
912 * knows that the list does not contain any null elements.)
913 *
914 * <p>
915 * Like the {@link #toArray()} method, this method acts as bridge between
916 * array-based and collection-based APIs. Further, this method allows
917 * precise control over the runtime type of the output array, and may, under
918 * certain circumstances, be used to save allocation costs.
919 *
920 * <p>
921 * Suppose <tt>x</tt> is a list known to contain only strings. The following
922 * code can be used to dump the list into a newly allocated array of
923 * <tt>String</tt>:
924 *
925 * <pre>
926 * String[] y = x.toArray(new String[0]);
927 * </pre>
928 *
929 * Note that <tt>toArray(new Object[0])</tt> is identical in function to
930 * <tt>toArray()</tt>.
931 *
932 * @param a
933 * the array into which the elements of the list are to be
934 * stored, if it is big enough; otherwise, a new array of the
935 * same runtime type is allocated for this purpose.
936 * @return an array containing the elements of the list
937 * @throws ArrayStoreException
938 * if the runtime type of the specified array is not a supertype
939 * of the runtime type of every element in this list
940 * @throws NullPointerException
941 * if the specified array is null
942 */
943 public <T> T[] toArray(T[] a) {
944 // 若指定的數組容量小于鏈表長度，新建數組
945 if (a.length < size)
946 a = (T[]) java.lang.reflect.Array.newInstance(a.getClass()
947 .getComponentType(), size);
948 int i = 0;
949 Object[] result = a;
950 for (Entry<E> e = header.next; e != header; e = e.next)
951 result[i++] = e.element;
952
953 // 將數組中第一個無效元素置為null
954 if (a.length > size)
955 a[size] = null;
956
957 return a;
958 }
959
960 private static final long serialVersionUID = 876323262645176354L;
961
962 /**
963 * Save the state of this <tt>LinkedList</tt> instance to a stream (that is,
964 * serialize it).
965 *
966 * @serialData The size of the list (the number of elements it contains) is
967 * emitted (int), followed by all of its elements (each an
968 * Object) in the proper order.
969 */
970 private void writeObject(java.io.ObjectOutputStream s)
971 throws java.io.IOException {
972 // Write out any hidden serialization magic
973 s.defaultWriteObject();
974
975 // Write out size
976 s.writeInt(size);
977
978 // Write out all elements in the proper order.
979 for (Entry e = header.next; e != header; e = e.next)
980 s.writeObject(e.element);
981 }
982
983 /**
984 * Reconstitute this <tt>LinkedList</tt> instance from a stream (that is
985 * deserialize it).
986 */
987 private void readObject(java.io.ObjectInputStream s)
988 throws java.io.IOException, ClassNotFoundException {
989 // Read in any hidden serialization magic
990 s.defaultReadObject();
991
992 // Read in size
993 int size = s.readInt();
994
995 // Initialize header
996 header = new Entry<E>(null, null, null);
997 header.next = header.previous = header;
998
999 // Read in all elements in the proper order.
1000 for (int i = 0; i < size; i++)
1001 addBefore((E) s.readObject(), header);
1002 }
1003 }
1004
小結：
- LinkedList內部是一個雙向鏈表，每個元素包含數據域、前驅指針、后繼指針。內部類Entry實現了對鏈表元素的封裝，非常類似C語言里的struct結構體。用java實現鏈表的數據結構，是通過保存對象的引用實現的，區別去C語言里的指針，但是非常相似。
- 鏈表有一個頭節點，頭節點的后繼是首元素，頭節點的前驅是末尾元素。
- 元素的查找會根據其位置來確定遍歷的方向，索引小于長度的一半用正向遍歷，反之逆向。
- 通過一個內部類實現ListIterator接口，以支持通用的Iterator模式。
- 還包括許多操作隊列和棧的方法，很簡單，只是對通用方法的名稱包裝。