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 }