001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.util;
019:
020: import java.io.IOException;
021: import java.io.ObjectInputStream;
022: import java.io.ObjectOutputStream;
023: import java.io.Serializable;
024: import java.lang.reflect.Array;
025:
026: /**
027: * LinkedList is an implementation of List, backed by a linked list. All
028: * optional operations are supported, adding, removing and replacing. The
029: * elements can be any objects.
030: *
031: * @since 1.2
032: */
033: public class LinkedList<E> extends AbstractSequentialList<E> implements
034: List<E>, Queue<E>, Cloneable, Serializable {
035:
036: private static final long serialVersionUID = 876323262645176354L;
037:
038: transient int size = 0;
039:
040: transient Link<E> voidLink;
041:
042: private static final class Link<ET> {
043: ET data;
044:
045: Link<ET> previous, next;
046:
047: Link(ET o, Link<ET> p, Link<ET> n) {
048: data = o;
049: previous = p;
050: next = n;
051: }
052: }
053:
054: private static final class LinkIterator<ET> implements
055: ListIterator<ET> {
056: int pos, expectedModCount;
057:
058: final LinkedList<ET> list;
059:
060: Link<ET> link, lastLink;
061:
062: LinkIterator(LinkedList<ET> object, int location) {
063: list = object;
064: expectedModCount = list.modCount;
065: if (0 <= location && location <= list.size) {
066: // pos ends up as -1 if list is empty, it ranges from -1 to
067: // list.size - 1
068: // if link == voidLink then pos must == -1
069: link = list.voidLink;
070: if (location < list.size / 2) {
071: for (pos = -1; pos + 1 < location; pos++) {
072: link = link.next;
073: }
074: } else {
075: for (pos = list.size; pos >= location; pos--) {
076: link = link.previous;
077: }
078: }
079: } else {
080: throw new IndexOutOfBoundsException();
081: }
082: }
083:
084: public void add(ET object) {
085: if (expectedModCount == list.modCount) {
086: Link<ET> next = link.next;
087: Link<ET> newLink = new Link<ET>(object, link, next);
088: link.next = newLink;
089: next.previous = newLink;
090: link = newLink;
091: lastLink = null;
092: pos++;
093: expectedModCount++;
094: list.size++;
095: list.modCount++;
096: } else {
097: throw new ConcurrentModificationException();
098: }
099: }
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: } else {
159: throw new IllegalStateException();
160: }
161: } else {
162: throw new ConcurrentModificationException();
163: }
164: }
165:
166: public void set(ET object) {
167: if (expectedModCount == list.modCount) {
168: if (lastLink != null) {
169: lastLink.data = object;
170: } else {
171: throw new IllegalStateException();
172: }
173: } else {
174: throw new ConcurrentModificationException();
175: }
176: }
177: }
178:
179: /**
180: * Constructs a new empty instance of LinkedList.
181: *
182: */
183: public LinkedList() {
184: voidLink = new Link<E>(null, null, null);
185: voidLink.previous = voidLink;
186: voidLink.next = voidLink;
187: }
188:
189: /**
190: * Constructs a new instance of <code>LinkedList</code> that holds all of
191: * the elements contained in the supplied <code>collection</code>
192: * argument. The order of the elements in this new <code>LinkedList</code>
193: * will be determined by the iteration order of <code>collection</code>.
194: *
195: * @param collection
196: * the collection of elements to add
197: */
198: public LinkedList(Collection<? extends E> collection) {
199: this ();
200: addAll(collection);
201: }
202:
203: /**
204: * Inserts the specified object into this LinkedList at the specified
205: * location. The object is inserted before any previous element at the
206: * specified location. If the location is equal to the size of this
207: * LinkedList, the object is added at the end.
208: *
209: * @param location
210: * the index at which to insert
211: * @param object
212: * the object to add
213: *
214: * @exception IndexOutOfBoundsException
215: * when <code>location < 0 || >= size()</code>
216: */
217: @Override
218: public void add(int location, E object) {
219: if (0 <= location && location <= size) {
220: Link<E> link = voidLink;
221: if (location < (size / 2)) {
222: for (int i = 0; i <= location; i++) {
223: link = link.next;
224: }
225: } else {
226: for (int i = size; i > location; i--) {
227: link = link.previous;
228: }
229: }
230: Link<E> previous = link.previous;
231: Link<E> newLink = new Link<E>(object, previous, link);
232: previous.next = newLink;
233: link.previous = newLink;
234: size++;
235: modCount++;
236: } else {
237: throw new IndexOutOfBoundsException();
238: }
239: }
240:
241: /**
242: * Adds the specified object at the end of this LinkedList.
243: *
244: * @param object
245: * the object to add
246: * @return true
247: */
248: @Override
249: public boolean add(E object) {
250: // Cannot call addLast() as subclasses can override
251: Link<E> oldLast = voidLink.previous;
252: Link<E> newLink = new Link<E>(object, oldLast, voidLink);
253: voidLink.previous = newLink;
254: oldLast.next = newLink;
255: size++;
256: modCount++;
257: return true;
258: }
259:
260: /**
261: * Inserts the objects in the specified Collection at the specified location
262: * in this LinkedList. The objects are added in the order they are returned
263: * from the <code>Collection</code> iterator.
264: *
265: * @param location
266: * the index at which to insert
267: * @param collection
268: * the Collection of objects
269: * @return true if this LinkedList is modified, false otherwise
270: *
271: * @exception IndexOutOfBoundsException
272: * when <code>location < 0 || > size()</code>
273: */
274: @Override
275: public boolean addAll(int location,
276: Collection<? extends E> collection) {
277: if (location < 0 || location > size) {
278: throw new IndexOutOfBoundsException();
279: }
280: int adding = collection.size();
281: if (adding == 0) {
282: return false;
283: }
284: Link<E> previous = voidLink;
285: if (location < (size / 2)) {
286: for (int i = 0; i < location; i++) {
287: previous = previous.next;
288: }
289: } else {
290: for (int i = size; i >= location; i--) {
291: previous = previous.previous;
292: }
293: }
294: Link<E> next = previous.next;
295: for (E e : collection) {
296: Link<E> newLink = new Link<E>(e, previous, null);
297: previous.next = newLink;
298: previous = newLink;
299: }
300: previous.next = next;
301: next.previous = previous;
302: size += adding;
303: modCount++;
304: return true;
305: }
306:
307: /**
308: * Adds the objects in the specified Collection to this LinkedList.
309: *
310: * @param collection
311: * the Collection of objects
312: * @return true if this LinkedList is modified, false otherwise
313: */
314: @Override
315: public boolean addAll(Collection<? extends E> collection) {
316: int adding = collection.size();
317: if (adding == 0) {
318: return false;
319: }
320: Link<E> previous = voidLink.previous;
321: for (E e : collection) {
322: Link<E> newLink = new Link<E>(e, previous, null);
323: previous.next = newLink;
324: previous = newLink;
325: }
326: previous.next = voidLink;
327: voidLink.previous = previous;
328: size += adding;
329: modCount++;
330: return true;
331: }
332:
333: /**
334: * Adds the specified object at the beginning of this LinkedList.
335: *
336: * @param object
337: * the object to add
338: */
339: public void addFirst(E object) {
340: Link<E> oldFirst = voidLink.next;
341: Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
342: voidLink.next = newLink;
343: oldFirst.previous = newLink;
344: size++;
345: modCount++;
346: }
347:
348: /**
349: * Adds the specified object at the end of this LinkedList.
350: *
351: * @param object
352: * the object to add
353: */
354: public void addLast(E object) {
355: Link<E> oldLast = voidLink.previous;
356: Link<E> newLink = new Link<E>(object, oldLast, voidLink);
357: voidLink.previous = newLink;
358: oldLast.next = newLink;
359: size++;
360: modCount++;
361: }
362:
363: /**
364: * Removes all elements from this LinkedList, leaving it empty.
365: *
366: * @see List#isEmpty
367: * @see #size
368: */
369: @Override
370: public void clear() {
371: if (size > 0) {
372: size = 0;
373: voidLink.next = voidLink;
374: voidLink.previous = voidLink;
375: modCount++;
376: }
377: }
378:
379: /**
380: * Answers a new LinkedList with the same elements and size as this
381: * LinkedList.
382: *
383: * @return a shallow copy of this LinkedList
384: *
385: * @see java.lang.Cloneable
386: */
387: @SuppressWarnings("unchecked")
388: @Override
389: public Object clone() {
390: try {
391: LinkedList<E> l = (LinkedList<E>) super .clone();
392: l.size = 0;
393: l.voidLink = new Link<E>(null, null, null);
394: l.voidLink.previous = l.voidLink;
395: l.voidLink.next = l.voidLink;
396: l.addAll(this );
397: return l;
398: } catch (CloneNotSupportedException e) {
399: return null;
400: }
401: }
402:
403: /**
404: * Searches this LinkedList for the specified object.
405: *
406: * @param object
407: * the object to search for
408: * @return true if <code>object</code> is an element of this LinkedList,
409: * false otherwise
410: */
411: @Override
412: public boolean contains(Object object) {
413: Link<E> link = voidLink.next;
414: if (object != null) {
415: while (link != voidLink) {
416: if (object.equals(link.data)) {
417: return true;
418: }
419: link = link.next;
420: }
421: } else {
422: while (link != voidLink) {
423: if (link.data == null) {
424: return true;
425: }
426: link = link.next;
427: }
428: }
429: return false;
430: }
431:
432: @Override
433: public E get(int location) {
434: if (0 <= location && location < size) {
435: Link<E> link = voidLink;
436: if (location < (size / 2)) {
437: for (int i = 0; i <= location; i++) {
438: link = link.next;
439: }
440: } else {
441: for (int i = size; i > location; i--) {
442: link = link.previous;
443: }
444: }
445: return link.data;
446: }
447: throw new IndexOutOfBoundsException();
448: }
449:
450: /**
451: * Answers the first element in this LinkedList.
452: *
453: * @return the first element
454: *
455: * @exception NoSuchElementException
456: * when this LinkedList is empty
457: */
458: public E getFirst() {
459: Link<E> first = voidLink.next;
460: if (first != voidLink) {
461: return first.data;
462: }
463: throw new NoSuchElementException();
464: }
465:
466: /**
467: * Answers the last element in this LinkedList.
468: *
469: * @return the last element
470: *
471: * @exception NoSuchElementException
472: * when this LinkedList is empty
473: */
474: public E getLast() {
475: Link<E> last = voidLink.previous;
476: if (last != voidLink) {
477: return last.data;
478: }
479: throw new NoSuchElementException();
480: }
481:
482: /**
483: * Searches this LinkedList for the specified object and returns the index
484: * of the first occurrence.
485: *
486: * @param object
487: * the object to search for
488: * @return the index of the first occurrence of the object
489: */
490: @Override
491: public int indexOf(Object object) {
492: int pos = 0;
493: Link<E> link = voidLink.next;
494: if (object != null) {
495: while (link != voidLink) {
496: if (object.equals(link.data)) {
497: return pos;
498: }
499: link = link.next;
500: pos++;
501: }
502: } else {
503: while (link != voidLink) {
504: if (link.data == null) {
505: return pos;
506: }
507: link = link.next;
508: pos++;
509: }
510: }
511: return -1;
512: }
513:
514: /**
515: * Searches this LinkedList for the specified object and returns the index
516: * of the last occurrence.
517: *
518: * @param object
519: * the object to search for
520: * @return the index of the last occurrence of the object
521: */
522: @Override
523: public int lastIndexOf(Object object) {
524: int pos = size;
525: Link<E> link = voidLink.previous;
526: if (object != null) {
527: while (link != voidLink) {
528: pos--;
529: if (object.equals(link.data)) {
530: return pos;
531: }
532: link = link.previous;
533: }
534: } else {
535: while (link != voidLink) {
536: pos--;
537: if (link.data == null) {
538: return pos;
539: }
540: link = link.previous;
541: }
542: }
543: return -1;
544: }
545:
546: /**
547: * Answers a ListIterator on the elements of this LinkedList. The elements
548: * are iterated in the same order that they occur in the LinkedList. The
549: * iteration starts at the specified location.
550: *
551: * @param location
552: * the index at which to start the iteration
553: * @return a ListIterator on the elements of this LinkedList
554: *
555: * @exception IndexOutOfBoundsException
556: * when <code>location < 0 || >= size()</code>
557: *
558: * @see ListIterator
559: */
560: @Override
561: public ListIterator<E> listIterator(int location) {
562: return new LinkIterator<E>(this , location);
563: }
564:
565: /**
566: * Removes the object at the specified location from this LinkedList.
567: *
568: * @param location
569: * the index of the object to remove
570: * @return the removed object
571: *
572: * @exception IndexOutOfBoundsException
573: * when <code>location < 0 || >= size()</code>
574: */
575: @Override
576: public E remove(int location) {
577: if (0 <= location && location < size) {
578: Link<E> link = voidLink;
579: if (location < (size / 2)) {
580: for (int i = 0; i <= location; i++) {
581: link = link.next;
582: }
583: } else {
584: for (int i = size; i > location; i--) {
585: link = link.previous;
586: }
587: }
588: Link<E> previous = link.previous;
589: Link<E> next = link.next;
590: previous.next = next;
591: next.previous = previous;
592: size--;
593: modCount++;
594: return link.data;
595: }
596: throw new IndexOutOfBoundsException();
597: }
598:
599: @Override
600: public boolean remove(Object object) {
601: Link<E> link = voidLink.next;
602: if (object != null) {
603: while (link != voidLink && !object.equals(link.data)) {
604: link = link.next;
605: }
606: } else {
607: while (link != voidLink && link.data != null) {
608: link = link.next;
609: }
610: }
611: if (link == voidLink) {
612: return false;
613: }
614: Link<E> next = link.next;
615: Link<E> previous = link.previous;
616: previous.next = next;
617: next.previous = previous;
618: size--;
619: modCount++;
620: return true;
621: }
622:
623: /**
624: * Removes the first object from this LinkedList.
625: *
626: * @return the removed object
627: *
628: * @exception NoSuchElementException
629: * when this LinkedList is empty
630: */
631: public E removeFirst() {
632: Link<E> first = voidLink.next;
633: if (first != voidLink) {
634: Link<E> next = first.next;
635: voidLink.next = next;
636: next.previous = voidLink;
637: size--;
638: modCount++;
639: return first.data;
640: }
641: throw new NoSuchElementException();
642: }
643:
644: /**
645: * Removes the last object from this LinkedList.
646: *
647: * @return the removed object
648: *
649: * @exception NoSuchElementException
650: * when this LinkedList is empty
651: */
652: public E removeLast() {
653: Link<E> last = voidLink.previous;
654: if (last != voidLink) {
655: Link<E> previous = last.previous;
656: voidLink.previous = previous;
657: previous.next = voidLink;
658: size--;
659: modCount++;
660: return last.data;
661: }
662: throw new NoSuchElementException();
663: }
664:
665: /**
666: * Replaces the element at the specified location in this LinkedList with
667: * the specified object.
668: *
669: * @param location
670: * the index at which to put the specified object
671: * @param object
672: * the object to add
673: * @return the previous element at the index
674: *
675: * @exception IndexOutOfBoundsException
676: * when <code>location < 0 || >= size()</code>
677: */
678: @Override
679: public E set(int location, E object) {
680: if (0 <= location && location < size) {
681: Link<E> link = voidLink;
682: if (location < (size / 2)) {
683: for (int i = 0; i <= location; i++) {
684: link = link.next;
685: }
686: } else {
687: for (int i = size; i > location; i--) {
688: link = link.previous;
689: }
690: }
691: E result = link.data;
692: link.data = object;
693: return result;
694: }
695: throw new IndexOutOfBoundsException();
696: }
697:
698: /**
699: * Answers the number of elements in this LinkedList.
700: *
701: * @return the number of elements in this LinkedList
702: */
703: @Override
704: public int size() {
705: return size;
706: }
707:
708: public boolean offer(E o) {
709: add(o);
710: return true;
711: }
712:
713: public E poll() {
714: return size == 0 ? null : removeFirst();
715: }
716:
717: public E remove() {
718: return removeFirst();
719: }
720:
721: public E peek() {
722: Link<E> first = voidLink.next;
723: return first == voidLink ? null : first.data;
724: }
725:
726: public E element() {
727: return getFirst();
728: }
729:
730: /**
731: * Answers a new array containing all elements contained in this LinkedList.
732: *
733: * @return an array of the elements from this LinkedList
734: */
735: @Override
736: public Object[] toArray() {
737: int index = 0;
738: Object[] contents = new Object[size];
739: Link<E> link = voidLink.next;
740: while (link != voidLink) {
741: contents[index++] = link.data;
742: link = link.next;
743: }
744: return contents;
745: }
746:
747: /**
748: * Answers an array containing all elements contained in this LinkedList. If
749: * the specified array is large enough to hold the elements, the specified
750: * array is used, otherwise an array of the same type is created. If the
751: * specified array is used and is larger than this LinkedList, the array
752: * element following the collection elements is set to null.
753: *
754: * @param contents
755: * the array
756: * @return an array of the elements from this LinkedList
757: *
758: * @exception ArrayStoreException
759: * when the type of an element in this LinkedList cannot be
760: * stored in the type of the specified array
761: */
762: @Override
763: @SuppressWarnings("unchecked")
764: public <T> T[] toArray(T[] contents) {
765: int index = 0;
766: if (size > contents.length) {
767: Class<?> ct = contents.getClass().getComponentType();
768: contents = (T[]) Array.newInstance(ct, size);
769: }
770: Link<E> link = voidLink.next;
771: while (link != voidLink) {
772: contents[index++] = (T) link.data;
773: link = link.next;
774: }
775: if (index < contents.length) {
776: contents[index] = null;
777: }
778: return contents;
779: }
780:
781: private void writeObject(ObjectOutputStream stream)
782: throws IOException {
783: stream.defaultWriteObject();
784: stream.writeInt(size);
785: Iterator<E> it = iterator();
786: while (it.hasNext()) {
787: stream.writeObject(it.next());
788: }
789: }
790:
791: @SuppressWarnings("unchecked")
792: private void readObject(ObjectInputStream stream)
793: throws IOException, ClassNotFoundException {
794: stream.defaultReadObject();
795: size = stream.readInt();
796: voidLink = new Link<E>(null, null, null);
797: Link<E> link = voidLink;
798: for (int i = size; --i >= 0;) {
799: Link<E> nextLink = new Link<E>((E) stream.readObject(),
800: link, null);
801: link.next = nextLink;
802: link = nextLink;
803: }
804: link.next = voidLink;
805: voidLink.previous = link;
806: }
807: }
|