linked list

linked list和arraylist各有所长，arraylist适用于很多调用get方法的场合，不适用于很多insert等改变list的size的场合，因为当数据插入到arraylist的时候实际上系统会新分配一段内存给一个新的list，然后把原来的list的内容和新插入的内容一起放到新建的list里面，这样当数据很大的时候，是很耗费系统资源的，性能也差。linked list正好相反，由于linked list的链接是通过内存指针指向相邻的node的方式联系起来的，通过这种方式，insert和add变得非常得容易，然而linked list的不足之处也很明显，由于node彼此之间的联系是通过内存指向连接起来的，因为想查找一个给定的对象，需要从linked list的头或尾找起，一个一个得找，直到找到特定的对象为止，因此当数据很多的时候，get方法的效率就会很低。下面是我写的singly linked list和doubly linked list的代码:

  1package utilities;
  2
  3/** *//**
  4 * The List interface described below is the basis for learning Linear data
  5 * types. It is not a involved as the <code>java.util.List</code>. It will
  6 * not define any searching or iteration methods that would normally be a part
  7 * of the List interface.
  8 */
  9public interface List
 10{
 11    // ADD OPERATIONS
 12    /** *//**
 13     * Method to append an element to the end of a List. If the list is empty
 14     * the element will be added to the first position.
 15     * 
 16     * @param o - element to be added to the list
 17     */
 18    public boolean append(Object o);
 19    
 20    /** *//**
 21     * Method to add an element to the FIRST position in the list. If the list
 22     * is empty, the element will be added to the first position.
 23     * 
 24     * @param o - element to be added to the list
 25     */
 26    public boolean add(Object o);
 27    
 28    /** *//**
 29     * Method to add an element to a specific position in the list. If the
 30     * position is an index outside of the bounds of the list an exception is
 31     * raised.
 32     * 
 33     * @param o - element to be added to the list
 34     * @param position - index that the element should be placed at
 35     * @throws IndexOutOfBoundsException when the index is (position<0 ||
 36     *             position > size())
 37     */
 38    public boolean add(Object o, int position) throws IndexOutOfBoundsException;
 39    
 40    // REMOVE OPERATIONS
 41    /** *//**
 42     * Clears the list, all elements are lost
 43     */
 44    public void clear();
 45    
 46    /** *//**
 47     * Removes the <b>FIRST</b> element in the list and changes the index for
 48     * all the remaining elements by (-1).<br>
 49     * 
 50     * @return Object element at the first position of the list. If the list is
 51     *         empty, returns a <code>null</code> reference.
 52     */
 53    public Object remove();
 54    
 55    /** *//**
 56     * Removes the <b>LAST</b> element in the list.
 57     * 
 58     * @return Object element at the last postion of the list. If list is empty,
 59     *         returns a <code>null</code> reference.
 60     */
 61    public Object removeLast();
 62    
 63    /** *//**
 64     * Removes the element at the provided index, if the index is outside the
 65     * bounds of the the list an exception is thrown
 66     * 
 67     * @param position the position in the list of the element to be removed
 68     * @return Object element being removed from the list
 69     * @throws IndexOutOfBoundsException when the index is (position<0 ||
 70     *             position > size())
 71     */
 72    public Object remove(int position) throws IndexOutOfBoundsException;
 73    
 74    // UTILITY METHODS
 75    /** *//**
 76     * Gets a refernce to the first element in the list without disturbing the
 77     * list structure.
 78     * 
 79     * @return Object reference to the fist element in the list, if the list is
 80     *         empty, returns a <code>null</code> reference.
 81     */
 82    public Object get();
 83    
 84    /** *//**
 85     * Gets a reference to the last element in the list, without distrubing the
 86     * list structure.
 87     * 
 88     * @return Object reference to the last element in the list, if the list is
 89     *         empty, returns a <code>null</code> reference.
 90     */
 91    public Object getLast();
 92    
 93    /** *//**
 94     * Gets a reference to the element at the specified postion. If the List is
 95     * empty returns a <code>null</code> reference.
 96     * 
 97     * @param position the location within the list of the desired element
 98     * @return Object reference to the specified element
 99     * @throws IndexOutOfBoundsException when the index is (position<0 ||
100     *             position > size())
101     */
102    public Object get(int position) throws IndexOutOfBoundsException;
103    
104    /** *//**
105     * Checks the list and determines if the object exists in the list, if the
106     * object is present in the list, the method returns true.
107     * 
108     * @return <code>boolean</code> true if object is in list, otherwise
109     *         false.
110     */
111    public boolean contains(Object o);
112    
113    /** *//**
114     * Returns the index in this list of the first occurrence of the specified
115     * element, or -1 if the List does not contain this element.
116     * 
117     * @return <code>int</code>, the index in this list of the first
118     *         occurrence of the specified element, or -1 if the list does not
119     *         contain this element.
120     */
121    public int indexOf(Object o);
122    
123    /** *//**
124     * Gets the current number of elements in the list, if list is empty returns
125     * a 0 (zero).
126     * 
127     * @return <code>int</code>, an integer greater or equal to zero
128     */
129    public int size();
130    
131    /** *//**
132     * Returns the current status of the list.
133     * 
134     * @return <code>boolean</code> false if the list conatins any elements.
135     */
136    public boolean isEmpty();
137}

 1package utilities;
 2
 3import java.io.*;
 4
 5/** *//**
 6 * @author 
 7 * @version 1.0
 8 */
 9public class SLLNode implements Serializable
10{
11    /** *//**
12     * 
13     */
14    private static final long serialVersionUID = 1L;
15    private Object element;
16    private SLLNode next;
17    
18    /** *//**
19     * @param element
20     */
21    public SLLNode(Object element)
22    {
23        this.element = element;
24        this.next = null;
25    }
26    
27    /** *//**
28     * @return the element
29     */
30    public Object getElement()
31    {
32        return element;
33    }
34    
35    /** *//**
36     * @param element the element to set
37     */
38    public void setElement(Object element)
39    {
40        this.element = element;
41    }
42    
43    /** *//**
44     * @return the next
45     */
46    public SLLNode getNext()
47    {
48        return next;
49    }
50    
51    /** *//**
52     * @param next the next to set
53     */
54    public void setNext(SLLNode next)
55    {
56        this.next = next;
57    }
58}
59

  1package utilities;
  2
  3import java.io.*;
  4
  5/** *//**
  6 * @author 
  7 * @version 1.0
  8 */
  9public class SLL implements List, Serializable
 10{
 11    /** *//**
 12     * Attributes
 13     */
 14    private static final long serialVersionUID = 1L;
 15    private SLLNode head;
 16    private int size;
 17    
 18    /** *//**
 19     * Default Constructor
 20     */
 21    public SLL()
 22    {
 23        this.head = null;
 24        this.size = 0;
 25    }
 26    
 27    /**//*
 28     * (non-Javadoc)
 29     * 
 30     * @see utilities.List#add(java.lang.Object)
 31     */
 32    public boolean add(Object object)
 33    {
 34        if (this.size == 0)
 35        {
 36            this.head = new SLLNode(object);
 37            this.size++;
 38        }
 39        else
 40        {
 41            SLLNode added = new SLLNode(object);
 42            added.setNext(this.head);
 43            this.head = added;
 44            this.size++;
 45        }
 46        return true;
 47    }
 48    
 49    /**//*
 50     * (non-Javadoc)
 51     * 
 52     * @see utilities.List#add(java.lang.Object, int)
 53     */
 54    public boolean add(Object object, int position)
 55    {
 56        if ((position < 0 || position > this.size - 1) && this.size != 0)
 57        {
 58            throw new IndexOutOfBoundsException();
 59        }
 60        if (this.size == 0)
 61        {
 62            this.head = new SLLNode(object);
 63            this.size++;
 64        }
 65        else
 66        {
 67            SLLNode added = new SLLNode(object);
 68            if (position == 0)
 69            {
 70                added.setNext(this.head);
 71                this.head = added;
 72                this.size++;
 73            }
 74            else
 75            {
 76                SLLNode previous = getSLLNode(position - 1);
 77                SLLNode next = getSLLNode(position);
 78                previous.setNext(added);
 79                added.setNext(next);
 80                this.size++;
 81            }
 82        }
 83        return true;
 84    }
 85    
 86    /**//*
 87     * (non-Javadoc)
 88     * 
 89     * @see utilities.List#append(java.lang.Object)
 90     */
 91    public boolean append(Object object)
 92    {
 93        if (this.size == 0)
 94        {
 95            this.head = new SLLNode(object);
 96            this.size++;
 97        }
 98        else
 99        {
100            SLLNode added = new SLLNode(object);
101            SLLNode current = this.head;
102            while (current.getNext() != null)
103            {
104                current = current.getNext();
105            }
106            current.setNext(added);
107            this.size++;
108        }
109        return true;
110    }
111    
112    /**//*
113     * (non-Javadoc)
114     * 
115     * @see utilities.List#clear()
116     */
117    public void clear()
118    {
119        this.head = null;
120        this.size = 0;
121    }
122    
123    /**//*
124     * (non-Javadoc)
125     * 
126     * @see utilities.List#contains(java.lang.Object)
127     */
128    public boolean contains(Object object)
129    {
130        SLLNode current = this.head;
131        do
132        {
133            if (current.getElement().equals(object))
134            {
135                return true;
136            }
137            else
138            {
139                current = current.getNext();
140            }
141        }
142        while (current != null);
143        return false;
144    }
145    
146    /**//*
147     * (non-Javadoc)
148     * 
149     * @see utilities.List#get()
150     */
151    public Object get()
152    {
153        if (this.size == 0)
154        {
155            return null;
156        }
157        return this.head.getElement();
158    }
159    
160    /** *//**
161     * Method that will get the SLLNode at a given position
162     * 
163     * @param position the position of the SLLNode
164     * @return the SLLNode of that position
165     * @throws IndexOutOfBoundsException
166     */
167    private SLLNode getSLLNode(int position) throws IndexOutOfBoundsException
168    {
169        if ((position < 0 || position > this.size - 1) && this.size != 0)
170        {
171            throw new IndexOutOfBoundsException();
172        }
173        if (this.size == 0)
174        {
175            return null;
176        }
177        SLLNode current = this.head;
178        for (int i = 0; i < position; i++)
179        {
180            current = current.getNext();
181        }
182        return current;
183    }
184    
185    /**//*
186     * (non-Javadoc)
187     * 
188     * @see utilities.List#get(int)
189     */
190    public Object get(int position) throws IndexOutOfBoundsException
191    {
192        if ((position < 0 || position > this.size - 1) && this.size != 0)
193        {
194            throw new IndexOutOfBoundsException();
195        }
196        if (this.size == 0)
197        {
198            return null;
199        }
200        return getSLLNode(position).getElement();
201    }
202    
203    /**//*
204     * (non-Javadoc)
205     * 
206     * @see utilities.List#getLast()
207     */
208    public Object getLast()
209    {
210        if (this.size == 0)
211        {
212            return null;
213        }
214        SLLNode last = this.head;
215        while (last.getNext() != null)
216        {
217            last = last.getNext();
218        }
219        return last.getElement();
220    }
221    
222    /**//*
223     * (non-Javadoc)
224     * 
225     * @see utilities.List#indexOf(java.lang.Object)
226     */
227    public int indexOf(Object object)
228    {
229        if (this.size == 0)
230        {
231            return -1;
232        }
233        else
234        {
235            SLLNode current = this.head;
236            int i = 0;
237            do
238            {
239                if (current.getElement().equals(object))
240                {
241                    return i;
242                }
243                else
244                {
245                    current = current.getNext();
246                    i++;
247                }
248            }
249            while (current != null);
250            return i;
251        }
252    }
253    
254    /**//*
255     * (non-Javadoc)
256     * 
257     * @see utilities.List#isEmpty()
258     */
259    public boolean isEmpty()
260    {
261        if (this.size == 0)
262        {
263            return true;
264        }
265        else
266        {
267            return false;
268        }
269    }
270    
271    /**//*
272     * (non-Javadoc)
273     * 
274     * @see utilities.List#remove()
275     */
276    public Object remove()
277    {
278        if (this.size == 0)
279        {
280            return null;
281        }
282        else if (this.size == 1)
283        {
284            Object object = this.head.getElement();
285            this.head = null;
286            this.size--;
287            return object;
288        }
289        else
290        {
291            Object object = this.head.getElement();
292            this.head = this.head.getNext();
293            this.size--;
294            return object;
295        }
296    }
297    
298    /**//*
299     * (non-Javadoc)
300     * 
301     * @see utilities.List#remove(int)
302     */
303    public Object remove(int position) throws IndexOutOfBoundsException
304    {
305        if ((position < 0 || position > this.size - 1) && this.size != 0)
306        {
307            throw new IndexOutOfBoundsException();
308        }
309        if (this.size == 0)
310        {
311            return null;
312        }
313        else if (this.size == 1)
314        {
315            Object object = this.head.getElement();
316            this.head = null;
317            this.size--;
318            return object;
319        }
320        else
321        {
322            if (position == this.size - 1)
323            {
324                SLLNode last = getSLLNode(this.size - 2);
325                SLLNode deleted = last.getNext();
326                Object object = deleted.getElement();
327                last.setNext(null);
328                this.size--;
329                return object;
330            }
331            else if (position == 0)
332            {
333                Object object = this.head.getElement();
334                this.head = this.head.getNext();
335                this.size--;
336                return object;
337            }
338            else
339            {
340                SLLNode previous = getSLLNode(position - 1);
341                SLLNode current = previous.getNext();
342                SLLNode next = current.getNext();
343                previous.setNext(next);
344                this.size--;
345                return current.getElement();
346            }
347        }
348    }
349    
350    /**//*
351     * (non-Javadoc)
352     * 
353     * @see utilities.List#removeLast()
354     */
355    public Object removeLast()
356    {
357        if (this.size == 0)
358        {
359            return null;
360        }
361        else if (this.size == 1)
362        {
363            Object object = this.head.getElement();
364            this.head = null;
365            this.size--;
366            return object;
367        }
368        else
369        {
370            SLLNode last = getSLLNode(this.size - 2);
371            SLLNode deleted = last.getNext();
372            Object object = deleted.getElement();
373            last.setNext(null);
374            this.size--;
375            return object;
376        }
377    }
378    
379    /**//*
380     * (non-Javadoc)
381     * 
382     * @see utilities.List#size()
383     */
384    public int size()
385    {
386        return this.size;
387    }
388}
389

  1package utilities;
  2
  3import junit.framework.TestCase;
  4
  5/** *//**
  6 * @author 
  7 * @version 1.0
  8 */
  9public class SLLTest extends TestCase
 10{
 11    private SLL list;
 12    
 13    /** *//**
 14     * @throws java.lang.Exception
 15     */
 16    protected void setUp() throws Exception
 17    {
 18        super.setUp();
 19        list = new SLL();
 20        list.append("Have");
 21        list.append("a");
 22        list.append("good");
 23        list.append("day");
 24    }
 25    
 26    /** *//**
 27     * @throws java.lang.Exception
 28     */
 29    protected void tearDown() throws Exception
 30    {
 31        super.tearDown();
 32        list = null;
 33    }
 34    
 35    /** *//**
 36     * Test method for {@link utilities.SLL#add(java.lang.Object)}.
 37     */
 38    public void testAddObject()
 39    {
 40        list.add("Head,hey?");
 41        System.out.println("--. TEST ADD METHOD");
 42        String expected = "Head,hey?";
 43        String actual = (String)(list.get(0));
 44        assertEquals("Error",expected,actual);
 45    }
 46    
 47    /** *//**
 48     * Test method for {@link utilities.SLL#add(java.lang.Object, int)}.
 49     */
 50    public void testAddObjectInt()
 51    {
 52        list.add("Add it at the head",1);
 53        System.out.println("--. TEST ADD METHOD WITH POSITION");
 54        String expected = "Add it at the head";
 55        String actual = (String)(list.get(1));
 56        assertEquals("Error",expected,actual);
 57    }
 58    
 59    /** *//**
 60     * Test method for {@link utilities.SLL#append(java.lang.Object)}.
 61     */
 62    public void testAppend()
 63    {
 64        list.append("Tail,hey?");
 65        System.out.println("--. TEST APPEND METHOD");
 66        String expected = "Tail,hey?";
 67        String actual = (String)(list.get(list.size()-1));
 68        assertEquals("Error",expected,actual);
 69    }
 70    
 71    /** *//**
 72     * Test method for {@link utilities.SLL#clear()}.
 73     */
 74    public void testClear()
 75    {
 76        list.clear();
 77        System.out.println("--. TEST CLEAR METHOD");
 78        int expected = 0;
 79        int actual = list.size();
 80        assertEquals("Error",expected,actual);
 81    }
 82    
 83    /** *//**
 84     * Test method for {@link utilities.SLL#contains(java.lang.Object)}.
 85     */
 86    public void testContains()
 87    {
 88        System.out.println("--. TEST CONTAINS METHOD");
 89        boolean expected = true;
 90        boolean actual = list.contains("good");
 91        assertEquals("Error",expected,actual);
 92    }
 93    
 94    /** *//**
 95     * Test method for {@link utilities.SLL#get()}.
 96     */
 97    public void testGet()
 98    {
 99        System.out.println("--. TEST GET METHOD");
100        String expected = "Have";
101        String actual = (String)list.get();
102        assertEquals("Error",expected,actual);
103    }
104    
105    /** *//**
106     * Test method for {@link utilities.SLL#get(int)}.
107     */
108    public void testGetInt()
109    {
110        System.out.println("--. TEST GET(POSITION) METHOD");
111        String expected = "good";
112        String actual = (String)list.get(2);
113        assertEquals("Error",expected,actual);
114    }
115    
116    /** *//**
117     * Test method for {@link utilities.SLL#getLast()}.
118     */
119    public void testGetLast()
120    {
121        System.out.println("--. TEST GETLAST METHOD");
122        String expected = "day";
123        String actual = (String)list.getLast();
124        assertEquals("Error",expected,actual);
125    }
126    
127    /** *//**
128     * Test method for {@link utilities.SLL#indexOf(java.lang.Object)}.
129     */
130    public void testIndexOf()
131    {
132        System.out.println("--. TEST INDEXOF METHOD");
133        int expected = 0;
134        int actual = list.indexOf("Have");
135        assertEquals("Error",expected,actual);
136    }
137    
138    /** *//**
139     * Test method for {@link utilities.SLL#isEmpty()}.
140     */
141    public void testIsEmpty()
142    {
143        System.out.println("--. TEST ISEMPTY METHOD");
144        boolean expected = false;
145        boolean actual = list.isEmpty();
146        assertEquals("Error",expected,actual);
147    }
148    
149    /** *//**
150     * Test method for {@link utilities.SLL#remove()}.
151     */
152    public void testRemove()
153    {
154        System.out.println("--. TEST REMOVE METHOD");
155        String expected = "Have";
156        String actual = (String)list.remove();
157        assertEquals("Error",expected,actual);
158    }
159    
160    /** *//**
161     * Test method for {@link utilities.SLL#remove(int)}.
162     */
163    public void testRemoveInt()
164    {
165        System.out.println("--. TEST REMOVE(INT) METHOD");
166        String expected = "Have";
167        String actual = (String)list.remove(0);
168        assertEquals("Error",expected,actual);
169    }
170    
171    /** *//**
172     * Test method for {@link utilities.SLL#removeLast()}.
173     */
174    public void testRemoveLast()
175    {
176        System.out.println("--. TEST REMOVELAST METHOD");
177        String expected = "day";
178        String actual = (String)list.removeLast();
179        assertEquals("Error",expected,actual);
180    }
181    
182    /** *//**
183     * Test method for {@link utilities.SLL#size()}.
184     */
185    public void testSize()
186    {
187        System.out.println("--. TEST SIZE METHOD");
188        int expected = 4;
189        int actual = list.size();
190        assertEquals("Error",expected,actual);
191    }
192}
193

 1package utilities;
 2
 3import java.io.*;
 4
 5/** *//**
 6 * @author 
 7 * @version 1.0
 8 *
 9 */
10public class DLLNode implements Serializable
11{
12    /** *//**
13     * 
14     */
15    private static final long serialVersionUID = 1L;
16    /** *//**
17     * Attributes
18     */
19    private Object element;
20    private DLLNode previous;
21    private DLLNode next;
22    
23    /** *//**
24     * Constructor
25     * @param element the element to set
26     */
27    public DLLNode(Object element)
28    {
29        this.element = element;
30        this.previous = null;
31        this.next = null;
32    }
33    
34    /** *//**
35     * @return the element
36     */
37    public Object getElement()
38    {
39        return element;
40    }
41    
42    /** *//**
43     * @param element the element to set
44     */
45    public void setElement(Object element)
46    {
47        this.element = element;
48    }
49    
50    /** *//**
51     * @return the next
52     */
53    public DLLNode getNext()
54    {
55        return next;
56    }
57    
58    /** *//**
59     * @param next the next to set
60     */
61    public void setNext(DLLNode next)
62    {
63        this.next = next;
64    }
65    
66    /** *//**
67     * @return the previous
68     */
69    public DLLNode getPrevious()
70    {
71        return previous;
72    }
73    
74    /** *//**
75     * @param previous the previous to set
76     */
77    public void setPrevious(DLLNode previous)
78    {
79        this.previous = previous;
80    }
81}
82

  1package utilities;
  2
  3import java.io.*;
  4
  5/** *//**
  6 * @author 
  7 * @version 1.0
  8 */
  9public class DLL implements List, Serializable
 10{
 11    /** *//**
 12     * Attributes
 13     */
 14    private static final long serialVersionUID = 1L;
 15    private DLLNode head;
 16    private DLLNode tail;
 17    private int size;
 18    
 19    /** *//**
 20     * Default Constructor
 21     */
 22    public DLL()
 23    {
 24        this.head = null;
 25        this.tail = null;
 26        this.size = 0;
 27    }
 28    
 29    /**//*
 30     * (non-Javadoc)
 31     * 
 32     * @see utilities.List#add(java.lang.Object)
 33     */
 34    public boolean add(Object object)
 35    {
 36        if (this.size == 0)
 37        {
 38            this.head = new DLLNode(object);
 39            this.tail = new DLLNode(object);
 40            this.size++;
 41        }
 42        else if (this.size == 1)
 43        {
 44            DLLNode added = new DLLNode(object);
 45            added.setNext(this.tail);
 46            this.tail.setPrevious(added);
 47            this.head = added;
 48            this.size++;
 49        }
 50        else
 51        {
 52            DLLNode added = new DLLNode(object);
 53            added.setNext(this.head);
 54            this.head.setPrevious(added);
 55            this.head = added;
 56            this.size++;
 57        }
 58        return true;
 59    }
 60    
 61    /**//*
 62     * (non-Javadoc)
 63     * 
 64     * @see utilities.List#add(java.lang.Object, int)
 65     */
 66    public boolean add(Object object, int position)
 67            throws IndexOutOfBoundsException
 68    {
 69        if ((position < 0 || position > this.size - 1) && this.size != 0)
 70        {
 71            throw new IndexOutOfBoundsException();
 72        }
 73        if (this.size == 0)
 74        {
 75            this.head = new DLLNode(object);
 76            this.tail = new DLLNode(object);
 77            this.size++;
 78        }
 79        else if (this.size == 1)
 80        {
 81            DLLNode added = new DLLNode(object);
 82            added.setNext(this.tail);
 83            this.tail.setPrevious(added);
 84            this.head = added;
 85            this.size++;
 86        }
 87        else
 88        {
 89            DLLNode added = new DLLNode(object);
 90            if (position == 0)
 91            {
 92                added.setNext(this.head);
 93                this.head.setPrevious(added);
 94                this.head = added;
 95                this.size++;
 96            }
 97            else
 98            {
 99                DLLNode previous = getDLLNode(position - 1);
100                DLLNode next = getDLLNode(position);
101                added.setPrevious(previous);
102                added.setNext(next);
103                previous.setNext(added);
104                next.setPrevious(added);
105                this.size++;
106            }
107        }
108        return true;
109    }
110    
111    /**//*
112     * (non-Javadoc)
113     * 
114     * @see utilities.List#append(java.lang.Object)
115     */
116    public boolean append(Object object)
117    {
118        if (this.size == 0)
119        {
120            this.head = new DLLNode(object);
121            this.tail = new DLLNode(object);
122            this.size++;
123        }
124        else if (this.size == 1)
125        {
126            DLLNode added = new DLLNode(object);
127            added.setPrevious(this.head);
128            this.head.setNext(added);
129            this.tail = added;
130            this.size++;
131        }
132        else
133        {
134            DLLNode appended = new DLLNode(object);
135            appended.setPrevious(this.tail);
136            this.tail.setNext(appended);
137            this.tail = appended;
138            this.size++;
139        }
140        return true;
141    }
142    
143    /**//*
144     * (non-Javadoc)
145     * 
146     * @see utilities.List#clear()
147     */
148    public void clear()
149    {
150        this.head = null;
151        this.tail = null;
152        this.size = 0;
153    }
154    
155    /**//*
156     * (non-Javadoc)
157     * 
158     * @see utilities.List#contains(java.lang.Object)
159     */
160    public boolean contains(Object object)
161    {
162        DLLNode current = this.head;
163        do
164        {
165            if (current.getElement().equals(object))
166            {
167                return true;
168            }
169            else
170            {
171                current = current.getNext();
172            }
173        }
174        while (current != null);
175        return false;
176    }
177    
178    /**//*
179     * (non-Javadoc)
180     * 
181     * @see utilities.List#get()
182     */
183    public Object get()
184    {
185        if (this.size == 0)
186        {
187            return null;
188        }
189        return this.head.getElement();
190    }
191    
192    /** *//**
193     * Method that will get the DLLNode at a given position
194     * 
195     * @param position the position of the DLLNode
196     * @return the DLLNode of that position
197     * @throws IndexOutOfBoundsException
198     */
199    private DLLNode getDLLNode(int position) throws IndexOutOfBoundsException
200    {
201        if ((position < 0 || position > this.size - 1) && this.size != 0)
202        {
203            throw new IndexOutOfBoundsException();
204        }
205        if (this.size == 0)
206        {
207            return null;
208        }
209        DLLNode current;
210        if (position - 0 < this.size - position)
211        {
212            current = this.head;
213            for (int i = 0; i < position; i++)
214            {
215                current = current.getNext();
216            }
217        }
218        else
219        {
220            current = this.tail;
221            for (int i = this.size - 1; i > position; i--)
222            {
223                current = current.getPrevious();
224            }
225        }
226        return current;
227    }
228    
229    /**//*
230     * (non-Javadoc)
231     * 
232     * @see utilities.List#get(int)
233     */
234    public Object get(int position) throws IndexOutOfBoundsException
235    {
236        if ((position < 0 || position > this.size - 1) && this.size != 0)
237        {
238            throw new IndexOutOfBoundsException();
239        }
240        if (this.size == 0)
241        {
242            return null;
243        }
244        return getDLLNode(position).getElement();
245    }
246    
247    /**//*
248     * (non-Javadoc)
249     * 
250     * @see utilities.List#getLast()
251     */
252    public Object getLast()
253    {
254        if (this.size == 0)
255        {
256            return null;
257        }
258        return this.tail.getElement();
259    }
260    
261    /**//*
262     * (non-Javadoc)
263     * 
264     * @see utilities.List#indexOf(java.lang.Object)
265     */
266    public int indexOf(Object object)
267    {
268        if (this.size == 0)
269        {
270            return -1;
271        }
272        else
273        {
274            DLLNode current = this.head;
275            int i = 0;
276            do
277            {
278                if (current.getElement().equals(object))
279                {
280                    return i;
281                }
282                else
283                {
284                    current = current.getNext();
285                    i++;
286                }
287            }
288            while (current != null);
289            return i;
290        }
291    }
292    
293    /**//*
294     * (non-Javadoc)
295     * 
296     * @see utilities.List#isEmpty()
297     */
298    public boolean isEmpty()
299    {
300        if (this.size == 0)
301        {
302            return true;
303        }
304        else
305        {
306            return false;
307        }
308    }
309    
310    /**//*
311     * (non-Javadoc)
312     * 
313     * @see utilities.List#remove()
314     */
315    public Object remove()
316    {
317        if (this.size == 0)
318        {
319            return null;
320        }
321        else if (this.size == 1)
322        {
323            Object object = this.head.getElement();
324            this.head = null;
325            this.tail = null;
326            this.size--;
327            return object;
328        }
329        else if (this.size == 2)
330        {
331            Object object = this.head.getElement();
332            this.tail.setPrevious(null);
333            this.head.setNext(null);
334            this.head.setElement(this.tail.getElement());
335            return object;
336        }
337        else
338        {
339            Object object = this.head.getElement();
340            this.head = this.head.getNext();
341            this.head.setPrevious(null);
342            this.size--;
343            return object;
344        }
345    }
346    
347    /**//*
348     * (non-Javadoc)
349     * 
350     * @see utilities.List#remove(int)
351     */
352    public Object remove(int position) throws IndexOutOfBoundsException
353    {
354        if ((position < 0 || position > this.size - 1) && this.size != 0)
355        {
356            throw new IndexOutOfBoundsException();
357        }
358        if (this.size == 0)
359        {
360            return null;
361        }
362        else if (this.size == 1)
363        {
364            Object object = this.head.getElement();
365            this.head = null;
366            this.tail = null;
367            this.size--;
368            return object;
369        }
370        else if (this.size == 2)
371        {
372            if (position == 0)
373            {
374                Object object = this.head.getElement();
375                this.tail.setPrevious(null);
376                this.head.setNext(null);
377                this.head.setElement(this.tail.getElement());
378                this.size--;
379                return object;
380            }
381            else
382            {
383                Object object = this.tail.getElement();
384                this.head.setNext(null);
385                this.tail.setPrevious(null);
386                this.tail.setElement(this.head.getElement());
387                this.size--;
388                return object;
389            }
390        }
391        else
392        {
393            if (position == this.size - 1)
394            {
395                Object object = this.tail.getElement();
396                this.tail = this.tail.getPrevious();
397                this.tail.setNext(null);
398                this.size--;
399                return object;
400            }
401            else if (position == 0)
402            {
403                Object object = this.head.getElement();
404                this.head = this.head.getNext();
405                this.head.setPrevious(null);
406                this.size--;
407                return object;
408            }
409            else
410            {
411                DLLNode current = getDLLNode(position);
412                DLLNode previous = current.getPrevious();
413                DLLNode next = current.getNext();
414                previous.setNext(next);
415                next.setPrevious(previous);
416                this.size--;
417                return current.getElement();
418            }
419        }
420    }
421    
422    /**//*
423     * (non-Javadoc)
424     * 
425     * @see utilities.List#removeLast()
426     */
427    public Object removeLast()
428    {
429        if (this.size == 0)
430        {
431            return null;
432        }
433        else if (this.size == 1)
434        {
435            Object object = this.tail.getElement();
436            this.head = null;
437            this.tail = null;
438            this.size--;
439            return object;
440        }
441        else if (this.size == 2)
442        {
443            Object object = this.tail.getElement();
444            this.head.setNext(null);
445            this.tail.setPrevious(null);
446            this.tail.setElement(this.head.getElement());
447            this.size--;
448            return object;
449        }
450        else
451        {
452            Object object = this.tail.getElement();
453            this.tail = this.tail.getPrevious();
454            this.tail.setNext(null);
455            this.size--;
456            return object;
457        }
458    }
459    
460    /**//*
461     * (non-Javadoc)
462     * 
463     * @see utilities.List#size()
464     */
465    public int size()
466    {
467        return this.size;
468    }
469}
470

  1package utilities;
  2
  3import junit.framework.TestCase;
  4
  5/** *//**
  6 * @author 
  7 * @version 1.0
  8 */
  9public class DLLTest extends TestCase
 10{
 11    private DLL list;
 12    
 13    /** *//**
 14     * @throws java.lang.Exception
 15     */
 16    protected void setUp() throws Exception
 17    {
 18        super.setUp();
 19        list = new DLL();
 20        list.append("Have");
 21        list.append("a");
 22        list.append("good");
 23        list.append("day");
 24    }
 25    
 26    /** *//**
 27     * @throws java.lang.Exception
 28     */
 29    protected void tearDown() throws Exception
 30    {
 31        super.tearDown();
 32        list = null;
 33    }
 34    
 35    /** *//**
 36     * Test method for {@link utilities.SLL#add(java.lang.Object)}.
 37     */
 38    public void testAddObject()
 39    {
 40        list.add("Head,hey?");
 41        System.out.println("--. TEST ADD METHOD");
 42        String expected = "Head,hey?";
 43        String actual = (String)(list.get(0));
 44        assertEquals("Error",expected,actual);
 45    }
 46    
 47    /** *//**
 48     * Test method for {@link utilities.SLL#add(java.lang.Object, int)}.
 49     */
 50    public void testAddObjectInt()
 51    {
 52        list.add("Add it at the head",1);
 53        System.out.println("--. TEST ADD METHOD WITH POSITION");
 54        String expected = "Add it at the head";
 55        String actual = (String)(list.get(1));
 56        assertEquals("Error",expected,actual);
 57    }
 58    
 59    /** *//**
 60     * Test method for {@link utilities.SLL#append(java.lang.Object)}.
 61     */
 62    public void testAppend()
 63    {
 64        list.append("Tail,hey?");
 65        System.out.println("--. TEST APPEND METHOD");
 66        String expected = "Tail,hey?";
 67        String actual = (String)(list.get(list.size()-1));
 68        assertEquals("Error",expected,actual);
 69    }
 70    
 71    /** *//**
 72     * Test method for {@link utilities.SLL#clear()}.
 73     */
 74    public void testClear()
 75    {
 76        list.clear();
 77        System.out.println("--. TEST CLEAR METHOD");
 78        int expected = 0;
 79        int actual = list.size();
 80        assertEquals("Error",expected,actual);
 81    }
 82    
 83    /** *//**
 84     * Test method for {@link utilities.SLL#contains(java.lang.Object)}.
 85     */
 86    public void testContains()
 87    {
 88        System.out.println("--. TEST CONTAINS METHOD");
 89        boolean expected = true;
 90        boolean actual = list.contains("good");
 91        assertEquals("Error",expected,actual);
 92    }
 93    
 94    /** *//**
 95     * Test method for {@link utilities.SLL#get()}.
 96     */
 97    public void testGet()
 98    {
 99        System.out.println("--. TEST GET METHOD");
100        String expected = "Have";
101        String actual = (String)list.get();
102        assertEquals("Error",expected,actual);
103    }
104    
105    /** *//**
106     * Test method for {@link utilities.SLL#get(int)}.
107     */
108    public void testGetInt()
109    {
110        System.out.println("--. TEST GET(POSITION) METHOD");
111        String expected = "good";
112        String actual = (String)list.get(2);
113        assertEquals("Error",expected,actual);
114    }
115    
116    /** *//**
117     * Test method for {@link utilities.SLL#getLast()}.
118     */
119    public void testGetLast()
120    {
121        System.out.println("--. TEST GETLAST METHOD");
122        String expected = "day";
123        String actual = (String)list.getLast();
124        assertEquals("Error",expected,actual);
125    }
126    
127    /** *//**
128     * Test method for {@link utilities.SLL#indexOf(java.lang.Object)}.
129     */
130    public void testIndexOf()
131    {
132        System.out.println("--. TEST INDEXOF METHOD");
133        int expected = 0;
134        int actual = list.indexOf("Have");
135        assertEquals("Error",expected,actual);
136    }
137    
138    /** *//**
139     * Test method for {@link utilities.SLL#isEmpty()}.
140     */
141    public void testIsEmpty()
142    {
143        System.out.println("--. TEST ISEMPTY METHOD");
144        boolean expected = false;
145        boolean actual = list.isEmpty();
146        assertEquals("Error",expected,actual);
147    }
148    
149    /** *//**
150     * Test method for {@link utilities.SLL#remove()}.
151     */
152    public void testRemove()
153    {
154        System.out.println("--. TEST REMOVE METHOD");
155        String expected = "Have";
156        String actual = (String)list.remove();
157        assertEquals("Error",expected,actual);
158    }
159    
160    /** *//**
161     * Test method for {@link utilities.SLL#remove(int)}.
162     */
163    public void testRemoveInt()
164    {
165        System.out.println("--. TEST REMOVE(INT) METHOD");
166        String expected = "Have";
167        String actual = (String)list.remove(0);
168        assertEquals("Error",expected,actual);
169    }
170    
171    /** *//**
172     * Test method for {@link utilities.SLL#removeLast()}.
173     */
174    public void testRemoveLast()
175    {
176        System.out.println("--. TEST REMOVELAST METHOD");
177        String expected = "day";
178        String actual = (String)list.removeLast();
179        assertEquals("Error",expected,actual);
180    }
181    
182    /** *//**
183     * Test method for {@link utilities.SLL#size()}.
184     */
185    public void testSize()
186    {
187        System.out.println("--. TEST SIZE METHOD");
188        int expected = 4;
189        int actual = list.size();
190        assertEquals("Error",expected,actual);
191    }
192}
193