| GNU Classpath (0.95) | |
| Frames | No Frames |
1: /* LinkedList.java -- Linked list implementation of the List interface 2: Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: 39: package java.util; 40: import java.io.IOException; 41: import java.io.ObjectInputStream; 42: import java.io.ObjectOutputStream; 43: import java.io.Serializable; 44: import java.lang.reflect.Array; 45: 46: /** 47: * Linked list implementation of the List interface. In addition to the 48: * methods of the List interface, this class provides access to the first 49: * and last list elements in O(1) time for easy stack, queue, or double-ended 50: * queue (deque) creation. The list is doubly-linked, with traversal to a 51: * given index starting from the end closest to the element.<p> 52: * 53: * LinkedList is not synchronized, so if you need multi-threaded access, 54: * consider using:<br> 55: * <code>List l = Collections.synchronizedList(new LinkedList(...));</code> 56: * <p> 57: * 58: * The iterators are <i>fail-fast</i>, meaning that any structural 59: * modification, except for <code>remove()</code> called on the iterator 60: * itself, cause the iterator to throw a 61: * {@link ConcurrentModificationException} rather than exhibit 62: * non-deterministic behavior. 63: * 64: * @author Original author unknown 65: * @author Bryce McKinlay 66: * @author Eric Blake (ebb9@email.byu.edu) 67: * @author Tom Tromey (tromey@redhat.com) 68: * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 69: * @see List 70: * @see ArrayList 71: * @see Vector 72: * @see Collections#synchronizedList(List) 73: * @since 1.2 74: * @status Complete to 1.6 75: */ 76: public class LinkedList<T> extends AbstractSequentialList<T> 77: implements List<T>, Deque<T>, Cloneable, Serializable 78: { 79: /** 80: * Compatible with JDK 1.2. 81: */ 82: private static final long serialVersionUID = 876323262645176354L; 83: 84: /** 85: * The first element in the list. 86: */ 87: transient Entry<T> first; 88: 89: /** 90: * The last element in the list. 91: */ 92: transient Entry<T> last; 93: 94: /** 95: * The current length of the list. 96: */ 97: transient int size = 0; 98: 99: /** 100: * Class to represent an entry in the list. Holds a single element. 101: */ 102: private static final class Entry<T> 103: { 104: /** The element in the list. */ 105: T data; 106: 107: /** The next list entry, null if this is last. */ 108: Entry<T> next; 109: 110: /** The previous list entry, null if this is first. */ 111: Entry<T> previous; 112: 113: /** 114: * Construct an entry. 115: * @param data the list element 116: */ 117: Entry(T data) 118: { 119: this.data = data; 120: } 121: } // class Entry 122: 123: /** 124: * Obtain the Entry at a given position in a list. This method of course 125: * takes linear time, but it is intelligent enough to take the shorter of the 126: * paths to get to the Entry required. This implies that the first or last 127: * entry in the list is obtained in constant time, which is a very desirable 128: * property. 129: * For speed and flexibility, range checking is not done in this method: 130: * Incorrect values will be returned if (n < 0) or (n >= size). 131: * 132: * @param n the number of the entry to get 133: * @return the entry at position n 134: */ 135: // Package visible for use in nested classes. 136: Entry<T> getEntry(int n) 137: { 138: Entry<T> e; 139: if (n < size / 2) 140: { 141: e = first; 142: // n less than size/2, iterate from start 143: while (n-- > 0) 144: e = e.next; 145: } 146: else 147: { 148: e = last; 149: // n greater than size/2, iterate from end 150: while (++n < size) 151: e = e.previous; 152: } 153: return e; 154: } 155: 156: /** 157: * Remove an entry from the list. This will adjust size and deal with 158: * `first' and `last' appropriatly. 159: * 160: * @param e the entry to remove 161: */ 162: // Package visible for use in nested classes. 163: void removeEntry(Entry<T> e) 164: { 165: modCount++; 166: size--; 167: if (size == 0) 168: first = last = null; 169: else 170: { 171: if (e == first) 172: { 173: first = e.next; 174: e.next.previous = null; 175: } 176: else if (e == last) 177: { 178: last = e.previous; 179: e.previous.next = null; 180: } 181: else 182: { 183: e.next.previous = e.previous; 184: e.previous.next = e.next; 185: } 186: } 187: } 188: 189: /** 190: * Checks that the index is in the range of possible elements (inclusive). 191: * 192: * @param index the index to check 193: * @throws IndexOutOfBoundsException if index < 0 || index > size 194: */ 195: private void checkBoundsInclusive(int index) 196: { 197: if (index < 0 || index > size) 198: throw new IndexOutOfBoundsException("Index: " + index + ", Size:" 199: + size); 200: } 201: 202: /** 203: * Checks that the index is in the range of existing elements (exclusive). 204: * 205: * @param index the index to check 206: * @throws IndexOutOfBoundsException if index < 0 || index >= size 207: */ 208: private void checkBoundsExclusive(int index) 209: { 210: if (index < 0 || index >= size) 211: throw new IndexOutOfBoundsException("Index: " + index + ", Size:" 212: + size); 213: } 214: 215: /** 216: * Create an empty linked list. 217: */ 218: public LinkedList() 219: { 220: } 221: 222: /** 223: * Create a linked list containing the elements, in order, of a given 224: * collection. 225: * 226: * @param c the collection to populate this list from 227: * @throws NullPointerException if c is null 228: */ 229: public LinkedList(Collection<? extends T> c) 230: { 231: addAll(c); 232: } 233: 234: /** 235: * Returns the first element in the list. 236: * 237: * @return the first list element 238: * @throws NoSuchElementException if the list is empty 239: */ 240: public T getFirst() 241: { 242: if (size == 0) 243: throw new NoSuchElementException(); 244: return first.data; 245: } 246: 247: /** 248: * Returns the last element in the list. 249: * 250: * @return the last list element 251: * @throws NoSuchElementException if the list is empty 252: */ 253: public T getLast() 254: { 255: if (size == 0) 256: throw new NoSuchElementException(); 257: return last.data; 258: } 259: 260: /** 261: * Remove and return the first element in the list. 262: * 263: * @return the former first element in the list 264: * @throws NoSuchElementException if the list is empty 265: */ 266: public T removeFirst() 267: { 268: if (size == 0) 269: throw new NoSuchElementException(); 270: modCount++; 271: size--; 272: T r = first.data; 273: 274: if (first.next != null) 275: first.next.previous = null; 276: else 277: last = null; 278: 279: first = first.next; 280: 281: return r; 282: } 283: 284: /** 285: * Remove and return the last element in the list. 286: * 287: * @return the former last element in the list 288: * @throws NoSuchElementException if the list is empty 289: */ 290: public T removeLast() 291: { 292: if (size == 0) 293: throw new NoSuchElementException(); 294: modCount++; 295: size--; 296: T r = last.data; 297: 298: if (last.previous != null) 299: last.previous.next = null; 300: else 301: first = null; 302: 303: last = last.previous; 304: 305: return r; 306: } 307: 308: /** 309: * Insert an element at the first of the list. 310: * 311: * @param o the element to insert 312: */ 313: public void addFirst(T o) 314: { 315: Entry<T> e = new Entry(o); 316: 317: modCount++; 318: if (size == 0) 319: first = last = e; 320: else 321: { 322: e.next = first; 323: first.previous = e; 324: first = e; 325: } 326: size++; 327: } 328: 329: /** 330: * Insert an element at the last of the list. 331: * 332: * @param o the element to insert 333: */ 334: public void addLast(T o) 335: { 336: addLastEntry(new Entry<T>(o)); 337: } 338: 339: /** 340: * Inserts an element at the end of the list. 341: * 342: * @param e the entry to add 343: */ 344: private void addLastEntry(Entry<T> e) 345: { 346: modCount++; 347: if (size == 0) 348: first = last = e; 349: else 350: { 351: e.previous = last; 352: last.next = e; 353: last = e; 354: } 355: size++; 356: } 357: 358: /** 359: * Returns true if the list contains the given object. Comparison is done by 360: * <code>o == null ? e = null : o.equals(e)</code>. 361: * 362: * @param o the element to look for 363: * @return true if it is found 364: */ 365: public boolean contains(Object o) 366: { 367: Entry<T> e = first; 368: while (e != null) 369: { 370: if (equals(o, e.data)) 371: return true; 372: e = e.next; 373: } 374: return false; 375: } 376: 377: /** 378: * Returns the size of the list. 379: * 380: * @return the list size 381: */ 382: public int size() 383: { 384: return size; 385: } 386: 387: /** 388: * Adds an element to the end of the list. 389: * 390: * @param o the entry to add 391: * @return true, as it always succeeds 392: */ 393: public boolean add(T o) 394: { 395: addLastEntry(new Entry<T>(o)); 396: return true; 397: } 398: 399: /** 400: * Removes the entry at the lowest index in the list that matches the given 401: * object, comparing by <code>o == null ? e = null : o.equals(e)</code>. 402: * 403: * @param o the object to remove 404: * @return true if an instance of the object was removed 405: */ 406: public boolean remove(Object o) 407: { 408: Entry<T> e = first; 409: while (e != null) 410: { 411: if (equals(o, e.data)) 412: { 413: removeEntry(e); 414: return true; 415: } 416: e = e.next; 417: } 418: return false; 419: } 420: 421: /** 422: * Append the elements of the collection in iteration order to the end of 423: * this list. If this list is modified externally (for example, if this 424: * list is the collection), behavior is unspecified. 425: * 426: * @param c the collection to append 427: * @return true if the list was modified 428: * @throws NullPointerException if c is null 429: */ 430: public boolean addAll(Collection<? extends T> c) 431: { 432: return addAll(size, c); 433: } 434: 435: /** 436: * Insert the elements of the collection in iteration order at the given 437: * index of this list. If this list is modified externally (for example, 438: * if this list is the collection), behavior is unspecified. 439: * 440: * @param c the collection to append 441: * @return true if the list was modified 442: * @throws NullPointerException if c is null 443: * @throws IndexOutOfBoundsException if index < 0 || index > size() 444: */ 445: public boolean addAll(int index, Collection<? extends T> c) 446: { 447: checkBoundsInclusive(index); 448: int csize = c.size(); 449: 450: if (csize == 0) 451: return false; 452: 453: Iterator<? extends T> itr = c.iterator(); 454: 455: // Get the entries just before and after index. If index is at the start 456: // of the list, BEFORE is null. If index is at the end of the list, AFTER 457: // is null. If the list is empty, both are null. 458: Entry<T> after = null; 459: Entry<T> before = null; 460: if (index != size) 461: { 462: after = getEntry(index); 463: before = after.previous; 464: } 465: else 466: before = last; 467: 468: // Create the first new entry. We do not yet set the link from `before' 469: // to the first entry, in order to deal with the case where (c == this). 470: // [Actually, we don't have to handle this case to fufill the 471: // contract for addAll(), but Sun's implementation appears to.] 472: Entry<T> e = new Entry<T>(itr.next()); 473: e.previous = before; 474: Entry<T> prev = e; 475: Entry<T> firstNew = e; 476: 477: // Create and link all the remaining entries. 478: for (int pos = 1; pos < csize; pos++) 479: { 480: e = new Entry<T>(itr.next()); 481: e.previous = prev; 482: prev.next = e; 483: prev = e; 484: } 485: 486: // Link the new chain of entries into the list. 487: modCount++; 488: size += csize; 489: prev.next = after; 490: if (after != null) 491: after.previous = e; 492: else 493: last = e; 494: 495: if (before != null) 496: before.next = firstNew; 497: else 498: first = firstNew; 499: return true; 500: } 501: 502: /** 503: * Remove all elements from this list. 504: */ 505: public void clear() 506: { 507: if (size > 0) 508: { 509: modCount++; 510: first = null; 511: last = null; 512: size = 0; 513: } 514: } 515: 516: /** 517: * Return the element at index. 518: * 519: * @param index the place to look 520: * @return the element at index 521: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 522: */ 523: public T get(int index) 524: { 525: checkBoundsExclusive(index); 526: return getEntry(index).data; 527: } 528: 529: /** 530: * Replace the element at the given location in the list. 531: * 532: * @param index which index to change 533: * @param o the new element 534: * @return the prior element 535: * @throws IndexOutOfBoundsException if index < 0 || index >= size() 536: */ 537: public T set(int index, T o) 538: { 539: checkBoundsExclusive(index); 540: Entry<T> e = getEntry(index); 541: T old = e.data; 542: e.data = o; 543: return old; 544: } 545: 546: /** 547: * Inserts an element in the given position in the list. 548: * 549: * @param index where to insert the element 550: * @param o the element to insert 551: * @throws IndexOutOfBoundsException if index < 0 || index > size() 552: */ 553: public void add(int index, T o) 554: { 555: checkBoundsInclusive(index); 556: Entry<T> e = new Entry<T>(o); 557: 558: if (index < size) 559: { 560: modCount++; 561: Entry<T> after = getEntry(index); 562: e.next = after; 563: e.previous = after.previous; 564: if (after.previous == null) 565: first = e; 566: else 567: after.previous.next = e; 568: after.previous = e; 569: size++; 570: } 571: else 572: addLastEntry(e); 573: } 574: 575: /** 576: * Removes the element at the given position from the list. 577: * 578: * @param index the location of the element to remove 579: * @return the removed element 580: * @throws IndexOutOfBoundsException if index < 0 || index > size() 581: */ 582: public T remove(int index) 583: { 584: checkBoundsExclusive(index); 585: Entry<T> e = getEntry(index); 586: removeEntry(e); 587: return e.data; 588: } 589: 590: /** 591: * Returns the first index where the element is located in the list, or -1. 592: * 593: * @param o the element to look for 594: * @return its position, or -1 if not found 595: */ 596: public int indexOf(Object o) 597: { 598: int index = 0; 599: Entry<T> e = first; 600: while (e != null) 601: { 602: if (equals(o, e.data)) 603: return index; 604: index++; 605: e = e.next; 606: } 607: return -1; 608: } 609: 610: /** 611: * Returns the last index where the element is located in the list, or -1. 612: * 613: * @param o the element to look for 614: * @return its position, or -1 if not found 615: */ 616: public int lastIndexOf(Object o) 617: { 618: int index = size - 1; 619: Entry<T> e = last; 620: while (e != null) 621: { 622: if (equals(o, e.data)) 623: return index; 624: index--; 625: e = e.previous; 626: } 627: return -1; 628: } 629: 630: /** 631: * Obtain a ListIterator over this list, starting at a given index. The 632: * ListIterator returned by this method supports the add, remove and set 633: * methods. 634: * 635: * @param index the index of the element to be returned by the first call to 636: * next(), or size() to be initially positioned at the end of the list 637: * @throws IndexOutOfBoundsException if index < 0 || index > size() 638: */ 639: public ListIterator<T> listIterator(int index) 640: { 641: checkBoundsInclusive(index); 642: return new LinkedListItr<T>(index); 643: } 644: 645: /** 646: * Create a shallow copy of this LinkedList (the elements are not cloned). 647: * 648: * @return an object of the same class as this object, containing the 649: * same elements in the same order 650: */ 651: public Object clone() 652: { 653: LinkedList<T> copy = null; 654: try 655: { 656: copy = (LinkedList<T>) super.clone(); 657: } 658: catch (CloneNotSupportedException ex) 659: { 660: } 661: copy.clear(); 662: copy.addAll(this); 663: return copy; 664: } 665: 666: /** 667: * Returns an array which contains the elements of the list in order. 668: * 669: * @return an array containing the list elements 670: */ 671: public Object[] toArray() 672: { 673: Object[] array = new Object[size]; 674: Entry<T> e = first; 675: for (int i = 0; i < size; i++) 676: { 677: array[i] = e.data; 678: e = e.next; 679: } 680: return array; 681: } 682: 683: /** 684: * Returns an Array whose component type is the runtime component type of 685: * the passed-in Array. The returned Array is populated with all of the 686: * elements in this LinkedList. If the passed-in Array is not large enough 687: * to store all of the elements in this List, a new Array will be created 688: * and returned; if the passed-in Array is <i>larger</i> than the size 689: * of this List, then size() index will be set to null. 690: * 691: * @param a the passed-in Array 692: * @return an array representation of this list 693: * @throws ArrayStoreException if the runtime type of a does not allow 694: * an element in this list 695: * @throws NullPointerException if a is null 696: */ 697: public <S> S[] toArray(S[] a) 698: { 699: if (a.length < size) 700: a = (S[]) Array.newInstance(a.getClass().getComponentType(), size); 701: else if (a.length > size) 702: a[size] = null; 703: Entry<T> e = first; 704: for (int i = 0; i < size; i++) 705: { 706: a[i] = (S) e.data; 707: e = e.next; 708: } 709: return a; 710: } 711: 712: /** 713: * Adds the specified element to the end of the list. 714: * 715: * @param value the value to add. 716: * @return true. 717: * @since 1.5 718: */ 719: public boolean offer(T value) 720: { 721: return add(value); 722: } 723: 724: /** 725: * Returns the first element of the list without removing 726: * it. 727: * 728: * @return the first element of the list. 729: * @throws NoSuchElementException if the list is empty. 730: * @since 1.5 731: */ 732: public T element() 733: { 734: return getFirst(); 735: } 736: 737: /** 738: * Returns the first element of the list without removing 739: * it. 740: * 741: * @return the first element of the list, or <code>null</code> 742: * if the list is empty. 743: * @since 1.5 744: */ 745: public T peek() 746: { 747: if (size == 0) 748: return null; 749: return getFirst(); 750: } 751: 752: /** 753: * Removes and returns the first element of the list. 754: * 755: * @return the first element of the list, or <code>null</code> 756: * if the list is empty. 757: * @since 1.5 758: */ 759: public T poll() 760: { 761: if (size == 0) 762: return null; 763: return removeFirst(); 764: } 765: 766: /** 767: * Removes and returns the first element of the list. 768: * 769: * @return the first element of the list. 770: * @throws NoSuchElementException if the list is empty. 771: * @since 1.5 772: */ 773: public T remove() 774: { 775: return removeFirst(); 776: } 777: 778: /** 779: * Serializes this object to the given stream. 780: * 781: * @param s the stream to write to 782: * @throws IOException if the underlying stream fails 783: * @serialData the size of the list (int), followed by all the elements 784: * (Object) in proper order 785: */ 786: private void writeObject(ObjectOutputStream s) throws IOException 787: { 788: s.defaultWriteObject(); 789: s.writeInt(size); 790: Entry<T> e = first; 791: while (e != null) 792: { 793: s.writeObject(e.data); 794: e = e.next; 795: } 796: } 797: 798: /** 799: * Deserializes this object from the given stream. 800: * 801: * @param s the stream to read from 802: * @throws ClassNotFoundException if the underlying stream fails 803: * @throws IOException if the underlying stream fails 804: * @serialData the size of the list (int), followed by all the elements 805: * (Object) in proper order 806: */ 807: private void readObject(ObjectInputStream s) 808: throws IOException, ClassNotFoundException 809: { 810: s.defaultReadObject(); 811: int i = s.readInt(); 812: while (--i >= 0) 813: addLastEntry(new Entry<T>((T) s.readObject())); 814: } 815: 816: /** 817: * A ListIterator over the list. This class keeps track of its 818: * position in the list and the two list entries it is between. 819: * 820: * @author Original author unknown 821: * @author Eric Blake (ebb9@email.byu.edu) 822: */ 823: private final class LinkedListItr<I> 824: implements ListIterator<I> 825: { 826: /** Number of modifications we know about. */ 827: private int knownMod = modCount; 828: 829: /** Entry that will be returned by next(). */ 830: private Entry<I> next; 831: 832: /** Entry that will be returned by previous(). */ 833: private Entry<I> previous; 834: 835: /** Entry that will be affected by remove() or set(). */ 836: private Entry<I> lastReturned; 837: 838: /** Index of `next'. */ 839: private int position; 840: 841: /** 842: * Initialize the iterator. 843: * 844: * @param index the initial index 845: */ 846: LinkedListItr(int index) 847: { 848: if (index == size) 849: { 850: next = null; 851: previous = (Entry<I>) last; 852: } 853: else 854: { 855: next = (Entry<I>) getEntry(index); 856: previous = next.previous; 857: } 858: position = index; 859: } 860: 861: /** 862: * Checks for iterator consistency. 863: * 864: * @throws ConcurrentModificationException if the list was modified 865: */ 866: private void checkMod() 867: { 868: if (knownMod != modCount) 869: throw new ConcurrentModificationException(); 870: } 871: 872: /** 873: * Returns the index of the next element. 874: * 875: * @return the next index 876: */ 877: public int nextIndex() 878: { 879: return position; 880: } 881: 882: /** 883: * Returns the index of the previous element. 884: * 885: * @return the previous index 886: */ 887: public int previousIndex() 888: { 889: return position - 1; 890: } 891: 892: /** 893: * Returns true if more elements exist via next. 894: * 895: * @return true if next will succeed 896: */ 897: public boolean hasNext() 898: { 899: return (next != null); 900: } 901: 902: /** 903: * Returns true if more elements exist via previous. 904: * 905: * @return true if previous will succeed 906: */ 907: public boolean hasPrevious() 908: { 909: return (previous != null); 910: } 911: 912: /** 913: * Returns the next element. 914: * 915: * @return the next element 916: * @throws ConcurrentModificationException if the list was modified 917: * @throws NoSuchElementException if there is no next 918: */ 919: public I next() 920: { 921: checkMod(); 922: if (next == null) 923: throw new NoSuchElementException(); 924: position++; 925: lastReturned = previous = next; 926: next = lastReturned.next; 927: return lastReturned.data; 928: } 929: 930: /** 931: * Returns the previous element. 932: * 933: * @return the previous element 934: * @throws ConcurrentModificationException if the list was modified 935: * @throws NoSuchElementException if there is no previous 936: */ 937: public I previous() 938: { 939: checkMod(); 940: if (previous == null) 941: throw new NoSuchElementException(); 942: position--; 943: lastReturned = next = previous; 944: previous = lastReturned.previous; 945: return lastReturned.data; 946: } 947: 948: /** 949: * Remove the most recently returned element from the list.