LinkedListTest.java.html

  1  import java.util.NoSuchElementException;
  2  
  3  /**
  4     This program tests the doubly linked list implementation.
  5  */
  6  public class LinkedListTest
  7  {
  8     public static void main(String[] args)
  9     {
 10        LinkedList lst = new LinkedList();
 11        check("", lst, "Constructing empty list");
 12        lst.addLast("A"); 
 13        check("A", lst, "Adding last to empty list");
 14        lst.addLast("B"); 
 15        check("AB", lst, "Adding last to non-empty list");
 16  
 17        lst = new LinkedList();
 18        lst.addFirst("A"); 
 19        check("A", lst, "Adding first to empty list");
 20        lst.addFirst("B"); 
 21        check("BA", lst, "Adding first to non-empty list");
 22  
 23        assertEquals("B", lst.removeFirst());
 24        check("A", lst, "Removing first, yielding non-empty list");
 25        assertEquals("A", lst.removeFirst());
 26        check("", lst, "Removing first, yielding empty list");
 27  
 28        lst = new LinkedList();
 29        lst.addLast("A"); 
 30        lst.addLast("B"); 
 31        check("AB", lst, "");
 32  
 33        assertEquals("B", lst.removeLast());
 34        check("A", lst, "Removing last, yielding non-empty list");
 35        assertEquals("A", lst.removeLast());
 36        check("", lst, "Removing last, yielding empty list");
 37  
 38        lst = new LinkedList();
 39        lst.addLast("A"); 
 40        lst.addLast("B"); 
 41        lst.addLast("C"); 
 42        check("ABC", lst, "");      
 43  
 44        ListIterator iter = lst.listIterator();
 45        assertEquals("A", iter.next());
 46        iter.set("D");
 47        check("DBC", lst, "Set element after next");
 48        assertEquals("D", iter.previous());
 49        iter.set("E");
 50        check("EBC", lst, "Set first element after previous");
 51        assertEquals("E", iter.next());
 52        assertEquals("B", iter.next());
 53        assertEquals("B", iter.previous());
 54        iter.set("F");
 55        check("EFC", lst, "Set second element after previous");      
 56        assertEquals("F", iter.next());
 57        assertEquals("C", iter.next());
 58        assertEquals("C", iter.previous());
 59        iter.set("G");
 60        check("EFG", lst, "Set last element after previous");      
 61  
 62        lst = new LinkedList();
 63        lst.addLast("A"); 
 64        lst.addLast("B"); 
 65        lst.addLast("C"); 
 66        lst.addLast("D"); 
 67        lst.addLast("E"); 
 68        check("ABCDE", lst, "");      
 69        iter = lst.listIterator();
 70        assertEquals("A", iter.next());
 71        iter.remove();
 72        check("BCDE", lst, "Remove first element after next");
 73        assertEquals("B", iter.next());
 74        assertEquals("C", iter.next());
 75        iter.remove();
 76        check("BDE", lst, "Remove middle element after next");
 77        assertEquals("D", iter.next());
 78        assertEquals("E", iter.next());
 79        iter.remove();
 80        check("BD", lst, "Remove last element after next");
 81        
 82        lst = new LinkedList();
 83        lst.addLast("A"); 
 84        lst.addLast("B"); 
 85        lst.addLast("C"); 
 86        lst.addLast("D"); 
 87        lst.addLast("E"); 
 88        check("ABCDE", lst, "");      
 89        iter = lst.listIterator();
 90        assertEquals("A", iter.next());
 91        assertEquals("B", iter.next());
 92        assertEquals("C", iter.next());
 93        assertEquals("D", iter.next());
 94        assertEquals("E", iter.next());
 95        assertEquals("E", iter.previous());
 96        iter.remove();
 97        check("ABCD", lst, "Remove last element after previous");
 98        assertEquals("D", iter.previous());
 99        assertEquals("C", iter.previous());
100        iter.remove();
101        check("ABD", lst, "Remove middle element after previous");
102        assertEquals("B", iter.previous());
103        assertEquals("A", iter.previous());
104        iter.remove();
105        check("BD", lst, "Remove first element after previous");
106  
107        lst = new LinkedList();
108        lst.addLast("B"); 
109        lst.addLast("C"); 
110        check("BC", lst, "");      
111        iter = lst.listIterator();
112        iter.add("A");
113        check("ABC", lst, "Add first element");
114        assertEquals("B", iter.next());
115        iter.add("D");
116        check("ABDC", lst, "Add middle element");
117        assertEquals("C", iter.next());
118        iter.add("E");
119        check("ABDCE", lst, "Add last element");      
120     }
121  
122     /**
123        Checks whether two objects are equal and throws an exception if not.
124        @param expected the expected value
125        @param actual the actual value
126     */
127     public static void assertEquals(Object expected, Object actual)
128     {
129        if (expected == null && actual != null ||
130           !expected.equals(actual))
131        {
132           throw new AssertionError("Expected " + expected + " but found " + actual);
133        }
134     }
135  
136     /**
137        Checks whether a linked list has the expected contents, and throws
138        an exception if not.
139        @param expected the letters that are expected in each node
140        @param actual the linked list
141        @param what a string explaining what has been tested. It is 
142        included in the message that is displayed when the test passes.
143     */
144     public static void check(String expected, LinkedList actual, String what)
145     {
146        int n = expected.length();
147        if (n > 0)
148        {
149           // Check first and last reference       
150           assertEquals(expected.substring(0, 1), actual.getFirst());
151           assertEquals(expected.substring(n - 1), actual.getLast());
152  
153           // Check next references
154           ListIterator iter = actual.listIterator();
155           for (int i = 0; i < n; i++)
156           {
157              assertEquals(true, iter.hasNext());
158              assertEquals(expected.substring(i, i + 1), iter.next());
159           }
160           assertEquals(false, iter.hasNext());
161  
162           // Check previous references
163           for (int i = n - 1 ; i >= 0; i--)
164           {
165              assertEquals(true, iter.hasPrevious());
166              assertEquals(expected.substring(i, i + 1), iter.previous());
167           }
168           assertEquals(false, iter.hasPrevious());
169        }
170        else
171        {
172           // Check that first and last are null
173           try
174           {
175              actual.getFirst();
176              throw new IllegalStateException("first not null");
177           }
178           catch (NoSuchElementException ex) 
179           {
180           }
181  
182           try
183           {
184              actual.getLast();
185              throw new IllegalStateException("last not null");
186           }
187           catch (NoSuchElementException ex)
188           {
189           }                
190        }
191        if (what.length() > 0)
192        {
193           System.out.println("Passed \"" + what + "\"."); 
194        }
195     }
196  }