1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package java.util;
19
20 import java.io.IOException;
21 import java.io.ObjectInputStream;
22 import java.io.ObjectOutputStream;
23 import java.io.Serializable;
24 import java.lang.reflect.Array;
25
26 /**
27 * LinkedList is an implementation of List, backed by a linked list. All
28 * optional operations are supported, adding, removing and replacing. The
29 * elements can be any objects.
30 *
31 * @since 1.2
32 */
33 public class LinkedList<E> extends AbstractSequentialList<E> implements
34 List<E>, Deque<E>, Cloneable, Serializable {
35
36
37 private static final long serialVersionUID = 876323262645176354L;
38
39 transient int size = 0;
40
41 transient Link<E> voidLink;
42
43 private static final class Link<ET> {
44 ET data;
45
46 Link<ET> previous, next;
47
48 Link(ET o, Link<ET> p, Link<ET> n) {
49 data = o;
50 previous = p;
51 next = n;
52 }
53 }
54
55 private static final class LinkIterator<ET> implements ListIterator<ET> {
56 int pos, expectedModCount;
57
58 final LinkedList<ET> list;
59
60 Link<ET> link, lastLink;
61
62 LinkIterator(LinkedList<ET> object, int location) {
63 list = object;
64 expectedModCount = list.modCount;
65 if (0 <= location && location <= list.size) {
66 // pos ends up as -1 if list is empty, it ranges from -1 to
67 // list.size - 1
68 // if link == voidLink then pos must == -1
69 link = list.voidLink;
70 if (location < list.size / 2) {
71 for (pos = -1; pos + 1 < location; pos++) {
72 link = link.next;
73 }
74 } else {
75 for (pos = list.size; pos >= location; pos--) {
76 link = link.previous;
77 }
78 }
79 } else {
80 throw new IndexOutOfBoundsException();
81 }
82 }
83
84 public void add(ET object) {
85 if (expectedModCount == list.modCount) {
86 Link<ET> next = link.next;
87 Link<ET> newLink = new Link<ET>(object, link, next);
88 link.next = newLink;
89 next.previous = newLink;
90 link = newLink;
91 lastLink = null;
92 pos++;
93 expectedModCount++;
94 list.size++;
95 list.modCount++;
96 } else {
97 throw new ConcurrentModificationException();
98 }
99 }
100
101 public boolean hasNext() {
102 return link.next != list.voidLink;
103 }
104
105 public boolean hasPrevious() {
106 return link != list.voidLink;
107 }
108
109 public ET next() {
110 if (expectedModCount == list.modCount) {
111 LinkedList.Link<ET> next = link.next;
112 if (next != list.voidLink) {
113 lastLink = link = next;
114 pos++;
115 return link.data;
116 }
117 throw new NoSuchElementException();
118 }
119 throw new ConcurrentModificationException();
120 }
121
122 public int nextIndex() {
123 return pos + 1;
124 }
125
126 public ET previous() {
127 if (expectedModCount == list.modCount) {
128 if (link != list.voidLink) {
129 lastLink = link;
130 link = link.previous;
131 pos--;
132 return lastLink.data;
133 }
134 throw new NoSuchElementException();
135 }
136 throw new ConcurrentModificationException();
137 }
138
139 public int previousIndex() {
140 return pos;
141 }
142
143 public void remove() {
144 if (expectedModCount == list.modCount) {
145 if (lastLink != null) {
146 Link<ET> next = lastLink.next;
147 Link<ET> previous = lastLink.previous;
148 next.previous = previous;
149 previous.next = next;
150 if (lastLink == link) {
151 pos--;
152 }
153 link = previous;
154 lastLink = null;
155 expectedModCount++;
156 list.size--;
157 list.modCount++;
158 return;
159 }
160 throw new IllegalStateException();
161 }
162 throw new ConcurrentModificationException();
163 }
164
165 public void set(ET object) {
166 if (expectedModCount == list.modCount) {
167 if (lastLink != null) {
168 lastLink.data = object;
169 } else {
170 throw new IllegalStateException();
171 }
172 } else {
173 throw new ConcurrentModificationException();
174 }
175 }
176 }
177
178 /*
179 * NOTES:descendingIterator is not fail-fast, according to the documentation
180 * and test case.
181 */
182 private class ReverseLinkIterator<ET> implements Iterator<ET> {
183 private int expectedModCount;
184
185 private final LinkedList<ET> list;
186
187 private Link<ET> link;
188
189 private boolean canRemove;
190
191 ReverseLinkIterator(LinkedList<ET> linkedList) {
192 super();
193 list = linkedList;
194 expectedModCount = list.modCount;
195 link = list.voidLink;
196 canRemove = false;
197 }
198
199 public boolean hasNext() {
200 return link.previous != list.voidLink;
201 }
202
203 public ET next() {
204 if (expectedModCount == list.modCount) {
205 if (hasNext()) {
206 link = link.previous;
207 canRemove = true;
208 return link.data;
209 }
210 throw new NoSuchElementException();
211 }
212 throw new ConcurrentModificationException();
213
214 }
215
216 public void remove() {
217 if (expectedModCount == list.modCount) {
218 if (canRemove) {
219 Link<ET> next = link.previous;
220 Link<ET> previous = link.next;
221 next.next = previous;
222 previous.previous = next;
223 link = previous;
224 list.size--;
225 list.modCount++;
226 expectedModCount++;
227 canRemove = false;
228 return;
229 }
230 throw new IllegalStateException();
231 }
232 throw new ConcurrentModificationException();
233 }
234 }
235
236 /**
237 * Constructs a new empty instance of {@code LinkedList}.
238 */
239 public LinkedList() {
240 voidLink = new Link<E>(null, null, null);
241 voidLink.previous = voidLink;
242 voidLink.next = voidLink;
243 }
244
245 /**
246 * Constructs a new instance of {@code LinkedList} that holds all of the
247 * elements contained in the specified {@code collection}. The order of the
248 * elements in this new {@code LinkedList} will be determined by the
249 * iteration order of {@code collection}.
250 *
251 * @param collection
252 * the collection of elements to add.
253 */
254 public LinkedList(Collection<? extends E> collection) {
255 this();
256 addAll(collection);
257 }
258
259 /**
260 * Inserts the specified object into this {@code LinkedList} at the
261 * specified location. The object is inserted before any previous element at
262 * the specified location. If the location is equal to the size of this
263 * {@code LinkedList}, the object is added at the end.
264 *
265 * @param location
266 * the index at which to insert.
267 * @param object
268 * the object to add.
269 * @throws IndexOutOfBoundsException
270 * if {@code location < 0 || >= size()}
271 */
272 @Override
273 public void add(int location, E object) {
274 if (0 <= location && location <= size) {
275 Link<E> link = voidLink;
276 if (location < (size / 2)) {
277 for (int i = 0; i <= location; i++) {
278 link = link.next;
279 }
280 } else {
281 for (int i = size; i > location; i--) {
282 link = link.previous;
283 }
284 }
285 Link<E> previous = link.previous;
286 Link<E> newLink = new Link<E>(object, previous, link);
287 previous.next = newLink;
288 link.previous = newLink;
289 size++;
290 modCount++;
291 } else {
292 throw new IndexOutOfBoundsException();
293 }
294 }
295
296 /**
297 * Adds the specified object at the end of this {@code LinkedList}.
298 *
299 * @param object
300 * the object to add.
301 * @return always true
302 */
303 @Override
304 public boolean add(E object) {
305 return addLastImpl(object);
306 }
307
308 private boolean addLastImpl(E object) {
309 Link<E> oldLast = voidLink.previous;
310 Link<E> newLink = new Link<E>(object, oldLast, voidLink);
311 voidLink.previous = newLink;
312 oldLast.next = newLink;
313 size++;
314 modCount++;
315 return true;
316 }
317
318 /**
319 * Inserts the objects in the specified collection at the specified location
320 * in this {@code LinkedList}. The objects are added in the order they are
321 * returned from the collection's iterator.
322 *
323 * @param location
324 * the index at which to insert.
325 * @param collection
326 * the collection of objects
327 * @return {@code true} if this {@code LinkedList} is modified,
328 * {@code false} otherwise.
329 * @throws ClassCastException
330 * if the class of an object is inappropriate for this list.
331 * @throws IllegalArgumentException
332 * if an object cannot be added to this list.
333 * @throws IndexOutOfBoundsException
334 * if {@code location < 0 || > size()}
335 */
336 @Override
337 public boolean addAll(int location, Collection<? extends E> collection) {
338 if (location < 0 || location > size) {
339 throw new IndexOutOfBoundsException();
340 }
341 int adding = collection.size();
342 if (adding == 0) {
343 return false;
344 }
345 Collection<? extends E> elements = (collection == this) ?
346 new ArrayList<E>(collection) : collection;
347
348 Link<E> previous = voidLink;
349 if (location < (size / 2)) {
350 for (int i = 0; i < location; i++) {
351 previous = previous.next;
352 }
353 } else {
354 for (int i = size; i >= location; i--) {
355 previous = previous.previous;
356 }
357 }
358 Link<E> next = previous.next;
359 for (E e : elements) {
360 Link<E> newLink = new Link<E>(e, previous, null);
361 previous.next = newLink;
362 previous = newLink;
363 }
364 previous.next = next;
365 next.previous = previous;
366 size += adding;
367 modCount++;
368 return true;
369 }
370
371 /**
372 * Adds the objects in the specified Collection to this {@code LinkedList}.
373 *
374 * @param collection
375 * the collection of objects.
376 * @return {@code true} if this {@code LinkedList} is modified,
377 * {@code false} otherwise.
378 */
379 @Override
380 public boolean addAll(Collection<? extends E> collection) {
381 int adding = collection.size();
382 if (adding == 0) {
383 return false;
384 }
385 Collection<? extends E> elements = (collection == this) ?
386 new ArrayList<E>(collection) : collection;
387
388 Link<E> previous = voidLink.previous;
389 for (E e : elements) {
390 Link<E> newLink = new Link<E>(e, previous, null);
391 previous.next = newLink;
392 previous = newLink;
393 }
394 previous.next = voidLink;
395 voidLink.previous = previous;
396 size += adding;
397 modCount++;
398 return true;
399 }
400
401 /**
402 * Adds the specified object at the beginning of this {@code LinkedList}.
403 *
404 * @param object
405 * the object to add.
406 */
407 public void addFirst(E object) {
408 addFirstImpl(object);
409 }
410
411 private boolean addFirstImpl(E object) {
412 Link<E> oldFirst = voidLink.next;
413 Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
414 voidLink.next = newLink;
415 oldFirst.previous = newLink;
416 size++;
417 modCount++;
418 return true;
419 }
420
421 /**
422 * Adds the specified object at the end of this {@code LinkedList}.
423 *
424 * @param object
425 * the object to add.
426 */
427 public void addLast(E object) {
428 addLastImpl(object);
429 }
430
431 /**
432 * Removes all elements from this {@code LinkedList}, leaving it empty.
433 *
434 * @see List#isEmpty
435 * @see #size
436 */
437 @Override
438 public void clear() {
439 if (size > 0) {
440 size = 0;
441 voidLink.next = voidLink;
442 voidLink.previous = voidLink;
443 modCount++;
444 }
445 }
446
447 /**
448 * Returns a new {@code LinkedList} with the same elements and size as this
449 * {@code LinkedList}.
450 *
451 * @return a shallow copy of this {@code LinkedList}.
452 * @see java.lang.Cloneable
453 */
454 @SuppressWarnings("unchecked")
455 @Override
456 public Object clone() {
457 try {
458 LinkedList<E> l = (LinkedList<E>) super.clone();
459 l.size = 0;
460 l.voidLink = new Link<E>(null, null, null);
461 l.voidLink.previous = l.voidLink;
462 l.voidLink.next = l.voidLink;
463 l.addAll(this);
464 return l;
465 } catch (CloneNotSupportedException e) {
466 return null;
467 }
468 }
469
470 /**
471 * Searches this {@code LinkedList} for the specified object.
472 *
473 * @param object
474 * the object to search for.
475 * @return {@code true} if {@code object} is an element of this
476 * {@code LinkedList}, {@code false} otherwise
477 */
478 @Override
479 public boolean contains(Object object) {
480 Link<E> link = voidLink.next;
481 if (object != null) {
482 while (link != voidLink) {
483 if (object.equals(link.data)) {
484 return true;
485 }
486 link = link.next;
487 }
488 } else {
489 while (link != voidLink) {
490 if (link.data == null) {
491 return true;
492 }
493 link = link.next;
494 }
495 }
496 return false;
497 }
498
499 @Override
500 public E get(int location) {
501 if (0 <= location && location < size) {
502 Link<E> link = voidLink;
503 if (location < (size / 2)) {
504 for (int i = 0; i <= location; i++) {
505 link = link.next;
506 }
507 } else {
508 for (int i = size; i > location; i--) {
509 link = link.previous;
510 }
511 }
512 return link.data;
513 }
514 throw new IndexOutOfBoundsException();
515 }
516
517 /**
518 * Returns the first element in this {@code LinkedList}.
519 *
520 * @return the first element.
521 * @throws NoSuchElementException
522 * if this {@code LinkedList} is empty.
523 */
524 public E getFirst() {
525 return getFirstImpl();
526 }
527
528 private E getFirstImpl() {
529 Link<E> first = voidLink.next;
530 if (first != voidLink) {
531 return first.data;
532 }
533 throw new NoSuchElementException();
534 }
535
536 /**
537 * Returns the last element in this {@code LinkedList}.
538 *
539 * @return the last element
540 * @throws NoSuchElementException
541 * if this {@code LinkedList} is empty
542 */
543 public E getLast() {
544 Link<E> last = voidLink.previous;
545 if (last != voidLink) {
546 return last.data;
547 }
548 throw new NoSuchElementException();
549 }
550
551 @Override
552 public int indexOf(Object object) {
553 int pos = 0;
554 Link<E> link = voidLink.next;
555 if (object != null) {
556 while (link != voidLink) {
557 if (object.equals(link.data)) {
558 return pos;
559 }
560 link = link.next;
561 pos++;
562 }
563 } else {
564 while (link != voidLink) {
565 if (link.data == null) {
566 return pos;
567 }
568 link = link.next;
569 pos++;
570 }
571 }
572 return -1;
573 }
574
575 /**
576 * Searches this {@code LinkedList} for the specified object and returns the
577 * index of the last occurrence.
578 *
579 * @param object
580 * the object to search for
581 * @return the index of the last occurrence of the object, or -1 if it was
582 * not found.
583 */
584 @Override
585 public int lastIndexOf(Object object) {
586 int pos = size;
587 Link<E> link = voidLink.previous;
588 if (object != null) {
589 while (link != voidLink) {
590 pos--;
591 if (object.equals(link.data)) {
592 return pos;
593 }
594 link = link.previous;
595 }
596 } else {
597 while (link != voidLink) {
598 pos--;
599 if (link.data == null) {
600 return pos;
601 }
602 link = link.previous;
603 }
604 }
605 return -1;
606 }
607
608 /**
609 * Returns a ListIterator on the elements of this {@code LinkedList}. The
610 * elements are iterated in the same order that they occur in the
611 * {@code LinkedList}. The iteration starts at the specified location.
612 *
613 * @param location
614 * the index at which to start the iteration
615 * @return a ListIterator on the elements of this {@code LinkedList}
616 * @throws IndexOutOfBoundsException
617 * if {@code location < 0 || >= size()}
618 * @see ListIterator
619 */
620 @Override
621 public ListIterator<E> listIterator(int location) {
622 return new LinkIterator<E>(this, location);
623 }
624
625 /**
626 * Removes the object at the specified location from this {@code LinkedList}.
627 *
628 * @param location
629 * the index of the object to remove
630 * @return the removed object
631 * @throws IndexOutOfBoundsException
632 * if {@code location < 0 || >= size()}
633 */
634 @Override
635 public E remove(int location) {
636 if (0 <= location && location < size) {
637 Link<E> link = voidLink;
638 if (location < (size / 2)) {
639 for (int i = 0; i <= location; i++) {
640 link = link.next;
641 }
642 } else {
643 for (int i = size; i > location; i--) {
644 link = link.previous;
645 }
646 }
647 Link<E> previous = link.previous;
648 Link<E> next = link.next;
649 previous.next = next;
650 next.previous = previous;
651 size--;
652 modCount++;
653 return link.data;
654 }
655 throw new IndexOutOfBoundsException();
656 }
657
658 @Override
659 public boolean remove(Object object) {
660 return removeFirstOccurrenceImpl(object);
661 }
662
663 /**
664 * Removes the first object from this {@code LinkedList}.
665 *
666 * @return the removed object.
667 * @throws NoSuchElementException
668 * if this {@code LinkedList} is empty.
669 */
670 public E removeFirst() {
671 return removeFirstImpl();
672 }
673
674 private E removeFirstImpl() {
675 Link<E> first = voidLink.next;
676 if (first != voidLink) {
677 Link<E> next = first.next;
678 voidLink.next = next;
679 next.previous = voidLink;
680 size--;
681 modCount++;
682 return first.data;
683 }
684 throw new NoSuchElementException();
685 }
686
687 /**
688 * Removes the last object from this {@code LinkedList}.
689 *
690 * @return the removed object.
691 * @throws NoSuchElementException
692 * if this {@code LinkedList} is empty.
693 */
694 public E removeLast() {
695 return removeLastImpl();
696 }
697
698 private E removeLastImpl() {
699 Link<E> last = voidLink.previous;
700 if (last != voidLink) {
701 Link<E> previous = last.previous;
702 voidLink.previous = previous;
703 previous.next = voidLink;
704 size--;
705 modCount++;
706 return last.data;
707 }
708 throw new NoSuchElementException();
709 }
710
711 /**
712 * {@inheritDoc}
713 *
714 * @see java.util.Deque#descendingIterator()
715 * @since 1.6
716 */
717 public Iterator<E> descendingIterator() {
718 return new ReverseLinkIterator<E>(this);
719 }
720
721 /**
722 * {@inheritDoc}
723 *
724 * @see java.util.Deque#offerFirst(java.lang.Object)
725 * @since 1.6
726 */
727 public boolean offerFirst(E e) {
728 return addFirstImpl(e);
729 }
730
731 /**
732 * {@inheritDoc}
733 *
734 * @see java.util.Deque#offerLast(java.lang.Object)
735 * @since 1.6
736 */
737 public boolean offerLast(E e) {
738 return addLastImpl(e);
739 }
740
741 /**
742 * {@inheritDoc}
743 *
744 * @see java.util.Deque#peekFirst()
745 * @since 1.6
746 */
747 public E peekFirst() {
748 return peekFirstImpl();
749 }
750
751 /**
752 * {@inheritDoc}
753 *
754 * @see java.util.Deque#peekLast()
755 * @since 1.6
756 */
757 public E peekLast() {
758 Link<E> last = voidLink.previous;
759 return (last == voidLink) ? null : last.data;
760 }
761
762 /**
763 * {@inheritDoc}
764 *
765 * @see java.util.Deque#pollFirst()
766 * @since 1.6
767 */
768 public E pollFirst() {
769 return (size == 0) ? null : removeFirstImpl();
770 }
771
772 /**
773 * {@inheritDoc}
774 *
775 * @see java.util.Deque#pollLast()
776 * @since 1.6
777 */
778 public E pollLast() {
779 return (size == 0) ? null : removeLastImpl();
780 }
781
782 /**
783 * {@inheritDoc}
784 *
785 * @see java.util.Deque#pop()
786 * @since 1.6
787 */
788 public E pop() {
789 return removeFirstImpl();
790 }
791
792 /**
793 * {@inheritDoc}
794 *
795 * @see java.util.Deque#push(java.lang.Object)
796 * @since 1.6
797 */
798 public void push(E e) {
799 addFirstImpl(e);
800 }
801
802 /**
803 * {@inheritDoc}
804 *
805 * @see java.util.Deque#removeFirstOccurrence(java.lang.Object)
806 * @since 1.6
807 */
808 public boolean removeFirstOccurrence(Object o) {
809 return removeFirstOccurrenceImpl(o);
810 }
811
812 /**
813 * {@inheritDoc}
814 *
815 * @see java.util.Deque#removeLastOccurrence(java.lang.Object)
816 * @since 1.6
817 */
818 public boolean removeLastOccurrence(Object o) {
819 Iterator<E> iter = new ReverseLinkIterator<E>(this);
820 return removeOneOccurrence(o, iter);
821 }
822
823 private boolean removeFirstOccurrenceImpl(Object o) {
824 Iterator<E> iter = new LinkIterator<E>(this, 0);
825 return removeOneOccurrence(o, iter);
826 }
827
828 private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
829 while (iter.hasNext()) {
830 E element = iter.next();
831 if (o == null ? element == null : o.equals(element)) {
832 iter.remove();
833 return true;
834 }
835 }
836 return false;
837 }
838
839 /**
840 * Replaces the element at the specified location in this {@code LinkedList}
841 * with the specified object.
842 *
843 * @param location
844 * the index at which to put the specified object.
845 * @param object
846 * the object to add.
847 * @return the previous element at the index.
848 * @throws ClassCastException
849 * if the class of an object is inappropriate for this list.
850 * @throws IllegalArgumentException
851 * if an object cannot be added to this list.
852 * @throws IndexOutOfBoundsException
853 * if {@code location < 0 || >= size()}
854 */
855 @Override
856 public E set(int location, E object) {
857 if (0 <= location && location < size) {
858 Link<E> link = voidLink;
859 if (location < (size / 2)) {
860 for (int i = 0; i <= location; i++) {
861 link = link.next;
862 }
863 } else {
864 for (int i = size; i > location; i--) {
865 link = link.previous;
866 }
867 }
868 E result = link.data;
869 link.data = object;
870 return result;
871 }
872 throw new IndexOutOfBoundsException();
873 }
874
875 /**
876 * Returns the number of elements in this {@code LinkedList}.
877 *
878 * @return the number of elements in this {@code LinkedList}.
879 */
880 @Override
881 public int size() {
882 return size;
883 }
884
885 public boolean offer(E o) {
886 return addLastImpl(o);
887 }
888
889 public E poll() {
890 return size == 0 ? null : removeFirst();
891 }
892
893 public E remove() {
894 return removeFirstImpl();
895 }
896
897 public E peek() {
898 return peekFirstImpl();
899 }
900
901 private E peekFirstImpl() {
902 Link<E> first = voidLink.next;
903 return first == voidLink ? null : first.data;
904 }
905
906 public E element() {
907 return getFirstImpl();
908 }
909
910 /**
911 * Returns a new array containing all elements contained in this
912 * {@code LinkedList}.
913 *
914 * @return an array of the elements from this {@code LinkedList}.
915 */
916 @Override
917 public Object[] toArray() {
918 int index = 0;
919 Object[] contents = new Object[size];
920 Link<E> link = voidLink.next;
921 while (link != voidLink) {
922 contents[index++] = link.data;
923 link = link.next;
924 }
925 return contents;
926 }
927
928 /**
929 * Returns an array containing all elements contained in this
930 * {@code LinkedList}. If the specified array is large enough to hold the
931 * elements, the specified array is used, otherwise an array of the same
932 * type is created. If the specified array is used and is larger than this
933 * {@code LinkedList}, the array element following the collection elements
934 * is set to null.
935 *
936 * @param contents
937 * the array.
938 * @return an array of the elements from this {@code LinkedList}.
939 * @throws ArrayStoreException
940 * if the type of an element in this {@code LinkedList} cannot
941 * be stored in the type of the specified array.
942 */
943 @Override
944 @SuppressWarnings("unchecked")
945 public <T> T[] toArray(T[] contents) {
946 int index = 0;
947 if (size > contents.length) {
948 Class<?> ct = contents.getClass().getComponentType();
949 contents = (T[]) Array.newInstance(ct, size);
950 }
951 Link<E> link = voidLink.next;
952 while (link != voidLink) {
953 contents[index++] = (T) link.data;
954 link = link.next;
955 }
956 if (index < contents.length) {
957 contents[index] = null;
958 }
959 return contents;
960 }
961
962 private void writeObject(ObjectOutputStream stream) throws IOException {
963 stream.defaultWriteObject();
964 stream.writeInt(size);
965 Iterator<E> it = iterator();
966 while (it.hasNext()) {
967 stream.writeObject(it.next());
968 }
969 }
970
971 @SuppressWarnings("unchecked")
972 private void readObject(ObjectInputStream stream) throws IOException,
973 ClassNotFoundException {
974 stream.defaultReadObject();
975 size = stream.readInt();
976 voidLink = new Link<E>(null, null, null);
977 Link<E> link = voidLink;
978 for (int i = size; --i >= 0;) {
979 Link<E> nextLink = new Link<E>((E) stream.readObject(), link, null);
980 link.next = nextLink;
981 link = nextLink;
982 }
983 link.next = voidLink;
984 voidLink.previous = link;
985 }
986 }
Save This Page