HsqlLinkedList


1   /* Copyright (c) 2001-2005, The HSQL Development Group
2    * All rights reserved.
3    *
4    * Redistribution and use in source and binary forms, with or without
5    * modification, are permitted provided that the following conditions are met:
6    *
7    * Redistributions of source code must retain the above copyright notice, this
8    * list of conditions and the following disclaimer.
9    *
10   * Redistributions in binary form must reproduce the above copyright notice,
11   * this list of conditions and the following disclaimer in the documentation
12   * and/or other materials provided with the distribution.
13   *
14   * Neither the name of the HSQL Development Group nor the names of its
15   * contributors may be used to endorse or promote products derived from this
16   * software without specific prior written permission.
17   *
18   * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19   * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20   * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21   * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
22   * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23   * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24   * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25   * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
26   * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27   * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29   */
30  
31  
32  package org.hsqldb.lib;
33  
34  /**
35   * Intended as an asynchronous alternative to HsqlArrayList.  Use HsqlArrayList if
36   * the list won't be initialized sequentially and if frequent references to
37   * specific element positions will be made.
38   *
39   * @author jcpeck@users
40   * @version 1.7.2
41   * @since 1.7.2
42   */
43  public class HsqlLinkedList extends BaseList implements HsqlList {
44  
45      /**
46       * A reference to the head of the list.  It is a dummy head (that is, the
47       * Node for index 0 is actually first.next).
48       */
49      private Node first;
50  
51      /** A reference to the tail of the list */
52      private Node last;
53  
54      /**
55       * Creates a new instance of HsqlLinkedList.
56       */
57      public HsqlLinkedList() {
58  
59          first        = new Node(null, null);
60          last         = first;
61          elementCount = 0;
62      }
63  
64      /**
65       * Inserts <code>element</code> at <code>index</code>.
66       * @throws IndexOutOfBoundsException if <code>index</code> &lt; 0 or is &gt;
67       * <code>size</code>.
68       */
69      public void add(int index, Object   element) {
70  
71          if (index == size()) {
72              add(element);    //Add to the end of this.
73          }
74  
75          //If index > size() an exception should be thrown with a slightly
76          //different message than the exception thrown by getInternal.
77          else if (index > size()) {
78              throw new IndexOutOfBoundsException  ("Index out of bounds: "
79                                                  + index + " > " + size());
80          } else {
81              Node current = getInternal(index);
82              Node newNext = new Node(current.data, current.next);
83  
84              current.data = element;
85              current.next = newNext;
86  
87              elementCount++;
88  
89              //If they inserted at the last valid index, then a new last element
90              //was created, therfore update the last pointer
91              if (last == current) {
92                  last = newNext;
93              }
94          }
95      }
96  
97      /**
98       * Appends <code>element</code> to the end of this list.
99       * @return true
100      */
101     public boolean add(Object   element) {
102 
103         last.next = new Node(element, null);
104         last      = last.next;
105 
106         elementCount++;
107 
108         return true;
109     }
110 
111     public void clear() {
112         first.next = null;
113     }
114 
115     /**
116      * Gets the element at given position
117      * @throws <code>IndexOutOfBoundsException</code> if index is not valid
118      * index within the list (0 &lt;= <code>index</code> &lt;
119      * <code>size</code>).
120      */
121     public Object   get(int index) {
122         return getInternal(index).data;
123     }
124 
125     /**
126      * Removes and returns the element at <code>index</code>.
127      * @throws <code>IndexOutOfBoundsException</code> if index is not valid
128      * index within the list (0 &lt;= <code>index</code> &lt;
129      * <code>size</code>).
130      */
131     public Object   remove(int index) {
132 
133         //Check that the index is less than size because the getInternal
134         //method is being called with index - 1 and its checks will therefore
135         //not be useful in this case.
136         if (index >= size()) {
137             throw new IndexOutOfBoundsException  ("Index out of bounds: "
138                                                 + index + " >= " + size());
139         }
140 
141         //Get the node that is previous to the node being removed
142         Node previousToRemove;
143 
144         if (index == 0) {
145             previousToRemove = first;
146         } else {
147             previousToRemove = getInternal(index - 1);
148         }
149 
150         //previousToRemove.next will never be null because of the check above
151         //that index < size.
152         Node toRemove = previousToRemove.next;
153 
154         previousToRemove.next = toRemove.next;
155 
156         elementCount--;
157 
158         //If they removed at the last valid index, then a the last element
159         //was removed, therfore update the last pointer
160         if (last == toRemove) {
161             last = previousToRemove;
162         }
163 
164         return toRemove.data;
165     }
166 
167     /**
168      * Replaces the current element at <code>index/code> with
169      * <code>element</code>.
170      * @return The current element at <code>index</code>.
171      */
172     public Object   set(int index, Object   element) {
173 
174         Node   setMe   = getInternal(index);
175         Object   oldData = setMe.data;
176 
177         setMe.data = element;
178 
179         return oldData;
180     }
181 
182     /**
183      * Accessor for the size of this linked list.  The size is the total number
184      * of elements in the list and is one greater than the largest index in the
185      * list.
186      * @return The size of this.
187      */
188     public final int size() {
189         return elementCount;
190     }
191 
192     /**
193      * Helper method that returns the Node at <code>index</code>.
194      * @param index The index of the Node to return.
195      * @return The Node at the given index.
196      * @throws <code>IndexOutOfBoundsException</code> if index is not valid
197      * index within the list (0 &lt;= <code>index</code> &lt;
198      * <code>size</code>).
199      */
200     protected final Node getInternal(int index) {
201 
202         //Check preconditions for the index variable
203         if (index >= size()) {
204             throw new IndexOutOfBoundsException  ("Index out of bounds: "
205                                                 + index + " >= " + size());
206         }
207 
208         if (index < 0) {
209             throw new IndexOutOfBoundsException  ("Index out of bounds: "
210                                                 + index + " < 0");
211         }
212 
213         if (index == 0) {
214             return first.next;
215         } else if (index == (size() - 1)) {
216             return last;
217         } else {
218             Node pointer = first.next;
219 
220             for (int i = 0; i < index; i++) {
221                 pointer = pointer.next;
222             }
223 
224             return pointer;
225         }
226     }
227 
228     /**
229      * Inner class that represents nodes within the linked list.  This should
230      * be a static inner class to avoid the uneccesary overhead of the
231      * containing class "this" pointer.
232      * jcpeck@users
233      * @version 05/24/2002
234      */
235     private static class Node {
236 
237         public Node   next;
238         public Object   data;
239 
240         public Node() {
241             next = null;
242             data = null;
243         }
244 
245         public Node(Object   data) {
246             this.next = null;
247             this.data = data;
248         }
249 
250         public Node(Object   data, Node next) {
251             this.next = next;
252             this.data = data;
253         }
254     }
255 }
256
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags