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