TLinkedList


1   ///////////////////////////////////////////////////////////////////////////////
2   // Copyright (c) 2001, Eric D. Friedman All Rights Reserved.
3   //
4   // This library is free software; you can redistribute it and/or
5   // modify it under the terms of the GNU Lesser General Public
6   // License as published by the Free Software Foundation; either
7   // version 2.1 of the License, or (at your option) any later version.
8   //
9   // This library is distributed in the hope that it will be useful,
10  // but WITHOUT ANY WARRANTY; without even the implied warranty of
11  // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  // GNU General Public License for more details.
13  //
14  // You should have received a copy of the GNU Lesser General Public
15  // License along with this program; if not, write to the Free Software
16  // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
17  ///////////////////////////////////////////////////////////////////////////////
18  
19  
20  package gnu.trove;
21  
22  import java.io.*;
23  import java.util.AbstractSequentialList  ;
24  import java.util.ListIterator  ;
25  import java.util.NoSuchElementException  ;
26  
27  /**
28   * A LinkedList implementation which holds instances of type
29   * <tt>TLinkable</tt>.
30   *
31   * <p>Using this implementation allows you to get java.util.LinkedList
32   * behavior (a doubly linked list, with Iterators that support insert
33   * and delete operations) without incurring the overhead of creating
34   * <tt>Node</tt> wrapper objects for every element in your list.</p>
35   *
36   * <p>The requirement to achieve this time/space gain is that the
37   * Objects stored in the List implement the <tt>TLinkable</tt>
38   * interface.</p>
39   *
40   * <p>The limitations are that you cannot put the same object into
41   * more than one list or more than once in the same list.  You must
42   * also ensure that you only remove objects that are actually in the
43   * list.  That is, if you have an object A and lists l1 and l2, you
44   * must ensure that you invoke List.remove(A) on the correct list.  It
45   * is also forbidden to invoke List.remove() with an unaffiliated
46   * TLinkable (one that belongs to no list): this will destroy the list
47   * you invoke it on.</p>
48   *
49   * <p>
50   * Created: Sat Nov 10 15:25:10 2001
51   * </p>
52   *
53   * @author Eric D. Friedman
54   * @version $Id: TLinkedList.java,v 1.7 2006/11/15 21:11:21 robeden Exp $
55   * @see gnu.trove.TLinkable
56   */
57  
58  public class TLinkedList<T extends TLinkable> extends AbstractSequentialList  <T>
59      implements Externalizable {
60  
61      static final long serialVersionUID = 1L;
62  
63  
64      /** the head of the list */
65      protected T _head;
66      /** the tail of the list */
67      protected T _tail;
68      /** the number of elements in the list */
69      protected int _size = 0;
70      
71      /**
72       * Creates a new <code>TLinkedList</code> instance.
73       *
74       */
75      public TLinkedList() {
76          super();
77      }
78  
79      /**
80       * Returns an iterator positioned at <tt>index</tt>.  Assuming
81       * that the list has a value at that index, calling next() will
82       * retrieve and advance the iterator.  Assuming that there is a
83       * value before <tt>index</tt> in the list, calling previous()
84       * will retrieve it (the value at index - 1) and move the iterator
85       * to that position.  So, iterating from front to back starts at
86       * 0; iterating from back to front starts at <tt>size()</tt>.
87       *
88       * @param index an <code>int</code> value
89       * @return a <code>ListIterator</code> value
90       */
91      public ListIterator  <T> listIterator(int index) {
92          return new IteratorImpl(index);
93      }
94  
95      /**
96       * Returns the number of elements in the list.
97       *
98       * @return an <code>int</code> value
99       */
100     public int size() {
101         return _size;
102     }
103 
104     /**
105      * Inserts <tt>linkable</tt> at index <tt>index</tt> in the list.
106      * All values > index are shifted over one position to accomodate
107      * the new addition.
108      *
109      * @param index an <code>int</code> value
110      * @param linkable an object of type TLinkable
111      */
112     public void add(int index, T linkable) {
113         if (index < 0 || index > size()) {
114             throw new IndexOutOfBoundsException  ("index:" + index);
115         }
116         insert(index,linkable);
117     }
118 
119     /**
120      * Appends <tt>linkable</tt> to the end of the list.
121      *
122      * @param linkable an object of type TLinkable
123      * @return always true
124      */
125     public boolean add(T linkable) {
126         insert(_size, linkable);
127         return true;
128     }
129 
130     /**
131      * Inserts <tt>linkable</tt> at the head of the list.
132      *
133      * @param linkable an object of type TLinkable
134      */
135     public void addFirst(T linkable) {
136         insert(0, linkable);
137     }
138 
139     /**
140      * Adds <tt>linkable</tt> to the end of the list.
141      *
142      * @param linkable an object of type TLinkable
143      */
144     public void addLast(T linkable) {
145         insert(size(), linkable);
146     }
147 
148     /**
149      * Empties the list.
150      *
151      */
152     public void clear() {
153         if (null != _head) {
154             for (TLinkable link = _head.getNext();
155                  link != null;
156                  link = link.getNext()) {
157                 TLinkable prev = link.getPrevious();
158                 prev.setNext(null);
159                 link.setPrevious(null);
160             }
161             _head = _tail = null;
162         }
163         _size = 0;
164     }
165 
166     /**
167      * Copies the list's contents into a native array.  This will be a
168      * shallow copy: the Tlinkable instances in the Object[] array
169      * have links to one another: changing those will put this list
170      * into an unpredictable state.  Holding a reference to one
171      * element in the list will prevent the others from being garbage
172      * collected unless you clear the next/previous links.  <b>Caveat
173      * programmer!</b>
174      *
175      * @return an <code>Object[]</code> value
176      */
177     public Object  [] toArray() {
178         Object  [] o = new Object  [_size];
179         int i = 0;
180         for (TLinkable link = _head; link != null; link = link.getNext()) {
181             o[i++] = link;
182         }
183         return o;
184     }
185 
186     /**
187      * Copies the list to a native array, destroying the next/previous
188      * links as the copy is made.  This list will be emptied after the
189      * copy (as if clear() had been invoked).  The Object[] array
190      * returned will contain TLinkables that do <b>not</b> hold
191      * references to one another and so are less likely to be the
192      * cause of memory leaks.
193      *
194      * @return an <code>Object[]</code> value
195      */
196     public Object  [] toUnlinkedArray() {
197         Object  [] o = new Object  [_size];
198         int i = 0;
199         for (T link = _head, tmp = null; link != null; i++) {
200             o[i] = link;
201             tmp = link;
202             link = (T) link.getNext();
203             tmp.setNext(null); // clear the links
204             tmp.setPrevious(null);
205         }
206         _size = 0;              // clear the list
207         _head = _tail = null;
208         return o;
209     }
210 
211     /**
212      * A linear search for <tt>o</tt> in the list.
213      *
214      * @param o an <code>Object</code> value
215      * @return a <code>boolean</code> value
216      */
217     public boolean contains(Object   o) {
218         for (TLinkable link = _head; link != null; link = link.getNext()) {
219             if (o.equals(link)) {
220                 return true;
221             }
222         }
223         return false;
224     }
225 
226 
227     /**
228      * {@inheritDoc}
229      */
230     @Override  
231     public T get(int index) {
232         // Short circuit for easy cases
233         if (index == 0) return _head;
234         if (index == _size - 1) return _tail;
235 
236         // Blow out for bogus values
237         if (index < 0 || index >= _size ) {
238             throw new IndexOutOfBoundsException  ("Index: " + index + ", Size: " + _size);
239         }
240 
241         // Determine if it's better to get there from the front or the back
242         if (index > (_size >> 1)) {
243             int position = _size - 1;
244             T node = _tail;
245 
246             while ( position > index ) {
247                 node = ( T ) node.getPrevious();
248                 position--;
249             }
250 
251             return node;
252         }
253         else {
254             int position = 0;
255             T node = _head;
256 
257             while( position < index ) {
258                 node = ( T ) node.getNext();
259                 position++;
260             }
261 
262             return node;
263         }
264     }
265 
266 
267     /**
268      * Returns the head of the list
269      *
270      * @return an <code>Object</code> value
271      */
272     public T getFirst() {
273         return _head;
274     }
275 
276     /**
277      * Returns the tail of the list.
278      *
279      * @return an <code>Object</code> value
280      */
281     public T getLast() {
282         return _tail;
283     }
284 
285     /**
286      * Remove and return the first element in the list.
287      *
288      * @return an <code>Object</code> value
289      */
290     public T removeFirst() {
291         T o = _head;
292         T n = (T) o.getNext();
293         o.setNext(null);
294 
295         if (null != n) {
296             n.setPrevious(null);
297         }
298 
299         _head = n;
300         if (--_size == 0) {
301             _tail = null;
302         }
303         return o;
304     }
305 
306     /**
307      * Remove and return the last element in the list.
308      *
309      * @return an <code>Object</code> value
310      */
311     public T removeLast() {
312         T o = _tail;
313         T prev = (T) o.getPrevious();
314         o.setPrevious(null);
315 
316         if (null != prev) {
317             prev.setNext(null);
318         }
319         _tail = prev;
320         if (--_size == 0) {
321             _head = null;
322         }
323         return o;
324     }
325 
326     /**
327      * Implementation of index-based list insertions.
328      *
329      * @param index an <code>int</code> value
330      * @param linkable an object of type TLinkable
331      */
332     protected void insert(int index, T linkable) {
333         T newLink = linkable;
334 
335         if (_size == 0) {
336             _head = _tail = newLink; // first insertion
337         } else if (index == 0) {
338             newLink.setNext(_head); // insert at front
339             _head.setPrevious(newLink);
340             _head = newLink;
341         } else if (index == _size) { // insert at back
342             _tail.setNext(newLink);
343             newLink.setPrevious(_tail);
344             _tail = newLink;
345         } else {
346             T node = get(index);
347 
348             T before = (T) node.getPrevious();
349             if (before != null) before.setNext(linkable);
350 
351             linkable.setPrevious(before);
352             linkable.setNext(node);
353             node.setPrevious(linkable);
354         }
355         _size++;
356     }
357 
358     /**
359      * Removes the specified element from the list.  Note that
360      * it is the caller's responsibility to ensure that the
361      * element does, in fact, belong to this list and not another
362      * instance of TLinkedList.  
363      *
364      * @param o a TLinkable element already inserted in this list.
365      * @return true if the element was a TLinkable and removed
366      */
367     public boolean remove(Object   o) {
368         if (o instanceof TLinkable) {
369             T p, n;
370             TLinkable link = (TLinkable)o;
371 
372             p = (T) link.getPrevious();
373             n = (T) link.getNext();
374 
375             if (n == null && p == null) { // emptying the list
376                 _head = _tail = null;
377             } else if (n == null) { // this is the tail
378                 // make previous the new tail
379                 link.setPrevious(null);
380                 p.setNext(null);
381                 _tail = p;
382             } else if (p == null) { // this is the head
383                 // make next the new head
384                 link.setNext(null);
385                 n.setPrevious(null);
386                 _head = n;
387             } else {            // somewhere in the middle
388                 p.setNext(n);
389                 n.setPrevious(p);
390                 link.setNext(null);
391                 link.setPrevious(null);
392             }
393 
394             _size--;            // reduce size of list
395             return true;
396         } else {
397             return false;
398         }
399     }
400 
401     /**
402      * Inserts newElement into the list immediately before current.
403      * All elements to the right of and including current are shifted
404      * over.
405      *
406      * @param current a <code>TLinkable</code> value currently in the list.
407      * @param newElement a <code>TLinkable</code> value to be added to
408      * the list.
409      */
410     public void addBefore(T current, T newElement) {
411         if (current == _head) {
412             addFirst(newElement);
413         } else if (current == null) {
414             addLast(newElement);
415         } else {
416             TLinkable p = current.getPrevious();
417             newElement.setNext(current);
418             p.setNext(newElement);
419             newElement.setPrevious(p);
420             current.setPrevious(newElement);
421             _size++;
422         }
423     }
424 
425 
426     public void writeExternal( ObjectOutput out ) throws IOException {
427         // VERSION
428         out.writeByte(0);
429 
430         // NUMBER OF ENTRIES
431         out.writeInt(_size);
432 
433         // HEAD
434         out.writeObject(_head);
435 
436         // TAIL
437         out.writeObject(_head);
438     }
439 
440     public void readExternal( ObjectInput in )
441         throws IOException, ClassNotFoundException   {
442 
443         // VERSION
444         in.readByte();
445 
446         // NUMBER OF ENTRIED
447         _size = in.readInt();
448 
449         // HEAD
450         _head = (T) in.readObject();
451 
452         // TAIL
453         _tail = (T) in.readObject();
454     }
455 
456 
457     /**
458      * A ListIterator that supports additions and deletions.
459      *
460      */
461     protected final class IteratorImpl implements ListIterator  <T> {
462         private int _nextIndex = 0;
463         private T _next;
464         private T _lastReturned;
465 
466         /**
467          * Creates a new <code>Iterator</code> instance positioned at
468          * <tt>index</tt>.
469          *
470          * @param position an <code>int</code> value
471          */
472         IteratorImpl(int position) {
473             if (position < 0 || position > _size) {
474                 throw new IndexOutOfBoundsException  ();
475             }
476 
477             _nextIndex = position;
478             if (position == 0) {
479                 _next = _head;
480             } else if (position == _size) {
481                 _next = null;
482             } else if (position < (_size >> 1)) {
483                 int pos = 0;
484                 for (_next = _head; pos < position; pos++) {
485                     _next = (T) _next.getNext();
486                 }
487             } else {
488                 int pos = _size - 1;
489                 for (_next = _tail; pos > position; pos--) {
490                     _next = (T) _next.getPrevious();
491                 }
492             }
493         }
494         
495         /**
496          * Insert <tt>linkable</tt> at the current position of the iterator.
497          * Calling next() after add() will return the added object.
498          *
499          * @param linkable an object of type TLinkable
500          */
501         public final void add(T linkable) {
502             _lastReturned = null;
503             _nextIndex++;
504 
505             if (_size == 0) {
506                 TLinkedList.this.add(linkable);
507             } else {
508                 TLinkedList.this.addBefore(_next, linkable);
509             }
510         }
511 
512         /**
513          * True if a call to next() will return an object.
514          *
515          * @return a <code>boolean</code> value
516          */
517         public final boolean hasNext() {
518             return _nextIndex != _size;
519         }
520 
521         /**
522          * True if a call to previous() will return a value.
523          *
524          * @return a <code>boolean</code> value
525          */
526         public final boolean hasPrevious() {
527             return _nextIndex != 0;
528         }
529 
530         /**
531          * Returns the value at the Iterator's index and advances the
532          * iterator.
533          *
534          * @return an <code>Object</code> value
535          * @exception NoSuchElementException if there is no next element
536          */
537         public final T next() {
538             if (_nextIndex == _size) {
539                 throw new NoSuchElementException  ();
540             }
541 
542             _lastReturned = _next;
543             _next = (T) _next.getNext();
544             _nextIndex++;
545             return _lastReturned;
546         }
547 
548         /**
549          * returns the index of the next node in the list (the
550          * one that would be returned by a call to next()).
551          *
552          * @return an <code>int</code> value
553          */
554         public final int nextIndex() {
555             return _nextIndex;
556         }
557 
558         /**
559          * Returns the value before the Iterator's index and moves the
560          * iterator back one index.
561          *
562          * @return an <code>Object</code> value
563          * @exception NoSuchElementException if there is no previous element.
564          */
565         public final T previous() {
566             if (_nextIndex == 0) {
567                 throw new NoSuchElementException  ();
568             }
569 
570             if (_nextIndex == _size) {
571                 _lastReturned = _next = _tail;
572             } else {
573                 _lastReturned = _next = (T) _next.getPrevious();
574             }
575 
576             _nextIndex--;
577             return _lastReturned;
578         }
579 
580         /**
581          * Returns the previous element's index.
582          *
583          * @return an <code>int</code> value
584          */
585         public final int previousIndex() {
586             return _nextIndex - 1;
587         }
588 
589         /**
590          * Removes the current element in the list and shrinks its
591          * size accordingly.
592          *
593          * @exception IllegalStateException neither next nor previous
594          * have been invoked, or remove or add have been invoked after
595          * the last invocation of next or previous.
596          */
597         public final void remove() {
598             if (_lastReturned == null) {
599                 throw new IllegalStateException  ("must invoke next or previous before invoking remove");
600             }
601 
602             if (_lastReturned != _next) {
603                 _nextIndex--;
604             }
605             _next = (T) _lastReturned.getNext();
606             TLinkedList.this.remove(_lastReturned);
607             _lastReturned = null;
608         }
609 
610         /**
611          * Replaces the current element in the list with
612          * <tt>linkable</tt>
613          *
614          * @param linkable an object of type TLinkable
615          */
616         public final void set(T linkable) {
617             if (_lastReturned == null) {
618                 throw new IllegalStateException  ();
619             }
620             T l = linkable;
621 
622             // need to check both, since this could be the only
623             // element in the list.
624             if (_lastReturned == _head) {
625                 _head = l;
626             }
627 
628             if (_lastReturned == _tail) {
629                 _tail = l;
630             }
631 
632             swap(_lastReturned, l);
633             _lastReturned = l;
634         }
635 
636         /**
637          * Replace from with to in the list.
638          *
639          * @param from a <code>TLinkable</code> value
640          * @param to a <code>TLinkable</code> value
641          */
642         private void swap(T from, T to) {
643             T p = (T) from.getPrevious();
644             T n = (T) from.getNext();
645 
646             if (null != p) {
647                 to.setPrevious(p);
648                 p.setNext(to);
649             }
650             if (null != n) {
651                 to.setNext(n);
652                 n.setPrevious(to);
653             }
654             from.setNext(null);
655             from.setPrevious(null);
656         }
657     }
658 } // TLinkedList
659
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags