|
1
7
8 package java.util;
9
10
73
74 public class LinkedList<E>
75 extends AbstractSequentialList  <E>
76 implements List <E>, Queue <E>, Cloneable , java.io.Serializable
77 {
78 private transient Entry<E> header = new Entry<E>(null, null, null);
79 private transient int size = 0;
80
81
84 public LinkedList() {
85 header.next = header.previous = header;
86 }
87
88
96 public LinkedList(Collection <? extends E> c) {
97 this();
98 addAll(c);
99 }
100
101
107 public E getFirst() {
108 if (size==0)
109 throw new NoSuchElementException ();
110
111 return header.next.element;
112 }
113
114
120 public E getLast() {
121 if (size==0)
122 throw new NoSuchElementException ();
123
124 return header.previous.element;
125 }
126
127
133 public E removeFirst() {
134 return remove(header.next);
135 }
136
137
143 public E removeLast() {
144 return remove(header.previous);
145 }
146
147
152 public void addFirst(E o) {
153 addBefore(o, header.next);
154 }
155
156
162 public void addLast(E o) {
163 addBefore(o, header);
164 }
165
166
175 public boolean contains(Object o) {
176 return indexOf(o) != -1;
177 }
178
179
184 public int size() {
185 return size;
186 }
187
188
195 public boolean add(E o) {
196 addBefore(o, header);
197 return true;
198 }
199
200
210 public boolean remove(Object o) {
211 if (o==null) {
212 for (Entry<E> e = header.next; e != header; e = e.next) {
213 if (e.element==null) {
214 remove(e);
215 return true;
216 }
217 }
218 } else {
219 for (Entry<E> e = header.next; e != header; e = e.next) {
220 if (o.equals(e.element)) {
221 remove(e);
222 return true;
223 }
224 }
225 }
226 return false;
227 }
228
229
241 public boolean addAll(Collection <? extends E> c) {
242 return addAll(size, c);
243 }
244
245
261 public boolean addAll(int index, Collection <? extends E> c) {
262 if (index < 0 || index > size)
263 throw new IndexOutOfBoundsException ("Index: "+index+
264 ", Size: "+size);
265 Object [] a = c.toArray();
266 int numNew = a.length;
267 if (numNew==0)
268 return false;
269 modCount++;
270
271 Entry<E> successor = (index==size ? header : entry(index));
272 Entry<E> predecessor = successor.previous;
273 for (int i=0; i<numNew; i++) {
274 Entry<E> e = new Entry<E>((E)a[i], successor, predecessor);
275 predecessor.next = e;
276 predecessor = e;
277 }
278 successor.previous = predecessor;
279
280 size += numNew;
281 return true;
282 }
283
284
287 public void clear() {
288 Entry<E> e = header.next;
289 while (e != header) {
290 Entry<E> next = e.next;
291 e.next = e.previous = null;
292 e.element = null;
293 e = next;
294 }
295 header.next = header.previous = header;
296 size = 0;
297 modCount++;
298 }
299
300
301
303
312 public E get(int index) {
313 return entry(index).element;
314 }
315
316
326 public E set(int index, E element) {
327 Entry<E> e = entry(index);
328 E oldVal = e.element;
329 e.element = element;
330 return oldVal;
331 }
332
333
344 public void add(int index, E element) {
345 addBefore(element, (index==size ? header : entry(index)));
346 }
347
348
359 public E remove(int index) {
360 return remove(entry(index));
361 }
362
363
366 private Entry<E> entry(int index) {
367 if (index < 0 || index >= size)
368 throw new IndexOutOfBoundsException ("Index: "+index+
369 ", Size: "+size);
370 Entry<E> e = header;
371 if (index < (size >> 1)) {
372 for (int i = 0; i <= index; i++)
373 e = e.next;
374 } else {
375 for (int i = size; i > index; i--)
376 e = e.previous;
377 }
378 return e;
379 }
380
381
382
384
396 public int indexOf(Object o) {
397 int index = 0;
398 if (o==null) {
399 for (Entry e = header.next; e != header; e = e.next) {
400 if (e.element==null)
401 return index;
402 index++;
403 }
404 } else {
405 for (Entry e = header.next; e != header; e = e.next) {
406 if (o.equals(e.element))
407 return index;
408 index++;
409 }
410 }
411 return -1;
412 }
413
414
426 public int lastIndexOf(Object o) {
427 int index = size;
428 if (o==null) {
429 for (Entry e = header.previous; e != header; e = e.previous) {
430 index--;
431 if (e.element==null)
432 return index;
433 }
434 } else {
435 for (Entry e = header.previous; e != header; e = e.previous) {
436 index--;
437 if (o.equals(e.element))
438 return index;
439 }
440 }
441 return -1;
442 }
443
444
446
451 public E peek() {
452 if (size==0)
453 return null;
454 return getFirst();
455 }
456
457
463 public E element() {
464 return getFirst();
465 }
466
467
472 public E poll() {
473 if (size==0)
474 return null;
475 return removeFirst();
476 }
477
478
484 public E remove() {
485 return removeFirst();
486 }
487
488
496 public boolean offer(E o) {
497 return add(o);
498 }
499
500
522 public ListIterator <E> listIterator(int index) {
523 return new ListItr(index);
524 }
525
526 private class ListItr implements ListIterator <E> {
527 private Entry<E> lastReturned = header;
528 private Entry<E> next;
529 private int nextIndex;
530 private int expectedModCount = modCount;
531
532 ListItr(int index) {
533 if (index < 0 || index > size)
534 throw new IndexOutOfBoundsException ("Index: "+index+
535 ", Size: "+size);
536 if (index < (size >> 1)) {
537 next = header.next;
538 for (nextIndex=0; nextIndex<index; nextIndex++)
539 next = next.next;
540 } else {
541 next = header;
542 for (nextIndex=size; nextIndex>index; nextIndex--)
543 next = next.previous;
544 }
545 }
546
547 public boolean hasNext() {
548 return nextIndex != size;
549 }
550
551 public E next() {
552 checkForComodification();
553 if (nextIndex == size)
554 throw new NoSuchElementException ();
555
556 lastReturned = next;
557 next = next.next;
558 nextIndex++;
559 return lastReturned.element;
560 }
561
562 public boolean hasPrevious() {
563 return nextIndex != 0;
564 }
565
566 public E previous() {
567 if (nextIndex == 0)
568 throw new NoSuchElementException ();
569
570 lastReturned = next = next.previous;
571 nextIndex--;
572 checkForComodification();
573 return lastReturned.element;
574 }
575
576 public int nextIndex() {
577 return nextIndex;
578 }
579
580 public int previousIndex() {
581 return nextIndex-1;
582 }
583
584 public void remove() {
585 checkForComodification();
586 Entry<E> lastNext = lastReturned.next;
587 try {
588 LinkedList.this.remove(lastReturned);
589 } catch (NoSuchElementException e) {
590 throw new IllegalStateException ();
591 }
592 if (next==lastReturned)
593 next = lastNext;
594 else
595 nextIndex--;
596 lastReturned = header;
597 expectedModCount++;
598 }
599
600 public void set(E o) {
601 if (lastReturned == header)
602 throw new IllegalStateException ();
603 checkForComodification();
604 lastReturned.element = o;
605 }
606
607 public void add(E o) {
608 checkForComodification();
609 lastReturned = header;
610 addBefore(o, next);
611 nextIndex++;
612 expectedModCount++;
613 }
614
615 final void checkForComodification() {
616 if (modCount != expectedModCount)
617 throw new ConcurrentModificationException ();
618 }
619 }
620
621 private static class Entry<E> {
622 E element;
623 Entry<E> next;
624 Entry<E> previous;
625
626 Entry(E element, Entry<E> next, Entry<E> previous) {
627 this.element = element;
628 this.next = next;
629 this.previous = previous;
630 }
631 }
632
633 private Entry<E> addBefore(E o, Entry<E> e) {
634 Entry<E> newEntry = new Entry<E>(o, e, e.previous);
635 newEntry.previous.next = newEntry;
636 newEntry.next.previous = newEntry;
637 size++;
638 modCount++;
639 return newEntry;
640 }
641
642 private E remove(Entry<E> e) {
643 if (e == header)
644 throw new NoSuchElementException ();
645
646 E result = e.element;
647 e.previous.next = e.next;
648 e.next.previous = e.previous;
649 e.next = e.previous = null;
650 e.element = null;
651 size--;
652 modCount++;
653 return result;
654 }
655
656
662 public Object clone() {
663 LinkedList <E> clone = null;
664 try {
665 clone = (LinkedList <E>) super.clone();
666 } catch (CloneNotSupportedException e) {
667 throw new InternalError ();
668 }
669
670 clone.header = new Entry<E>(null, null, null);
672 clone.header.next = clone.header.previous = clone.header;
673 clone.size = 0;
674 clone.modCount = 0;
675
676 for (Entry<E> e = header.next; e != header; e = e.next)
678 clone.add(e.element);
679
680 return clone;
681 }
682
683
690 public Object [] toArray() {
691 Object [] result = new Object [size];
692 int i = 0;
693 for (Entry<E> e = header.next; e != header; e = e.next)
694 result[i++] = e.element;
695 return result;
696 }
697
698
720 public <T> T[] toArray(T[] a) {
721 if (a.length < size)
722 a = (T[])java.lang.reflect.Array.newInstance(
723 a.getClass().getComponentType(), size);
724 int i = 0;
725 Object [] result = a;
726 for (Entry<E> e = header.next; e != header; e = e.next)
727 result[i++] = e.element;
728
729 if (a.length > size)
730 a[size] = null;
731
732 return a;
733 }
734
735 private static final long serialVersionUID = 876323262645176354L;
736
737
745 private void writeObject(java.io.ObjectOutputStream s)
746 throws java.io.IOException {
747 s.defaultWriteObject();
749
750 s.writeInt(size);
752
753 for (Entry e = header.next; e != header; e = e.next)
755 s.writeObject(e.element);
756 }
757
758
762 private void readObject(java.io.ObjectInputStream s)
763 throws java.io.IOException , ClassNotFoundException {
764 s.defaultReadObject();
766
767 int size = s.readInt();
769
770 header = new Entry<E>(null, null, null);
772 header.next = header.previous = header;
773
774 for (int i=0; i<size; i++)
776 addBefore((E)s.readObject(), header);
777 }
778 }
779 |
Popular Tags |
Java API By Example, From Geeks To Geeks.