Skip to content

Commit 466541b

Browse files
SitroneSitrone
committed
begin project 2
1 parent 77b102f commit 466541b

10 files changed

Lines changed: 1047 additions & 3 deletions

File tree

‎UCB CS61B/Homework and Projects/project/pj2/list/DList.java‎

Lines changed: 322 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,322 @@
1+
/* DList.java */
2+
3+
package com.cs61b.project2.list;
4+
5+
/**
6+
* A DList is a mutable doubly-linked list ADT. Its implementation is
7+
* circularly-linked and employs a sentinel node at the head of the list.
8+
*
9+
* DO NOT CHANGE ANY METHOD PROTOTYPES IN THIS FILE.
10+
**/
11+
12+
public class DList extends List {
13+
14+
/**
15+
* (inherited) size is the number of items in the list.
16+
* head references the sentinel node.
17+
* Note that the sentinel node does not store an item, and is not included
18+
* in the count stored by the "size" field.
19+
*
20+
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATION.
21+
**/
22+
23+
protected DListNode head;
24+
25+
/* DList invariants:
26+
* 1) head != null.
27+
* 2) For every DListNode x in a DList, x.next != null.
28+
* 3) For every DListNode x in a DList, x.prev != null.
29+
* 4) For every DListNode x in a DList, if x.next == y, then y.prev == x.
30+
* 5) For every DListNode x in a DList, if x.prev == y, then y.next == x.
31+
* 6) For every DList l, l.head.myList = null. (Note that l.head is the
32+
* sentinel.)
33+
* 7) For every DListNode x in a DList l EXCEPT l.head (the sentinel),
34+
* x.myList = l.
35+
* 8) size is the number of DListNodes, NOT COUNTING the sentinel,
36+
* that can be accessed from the sentinel (head) by a sequence of
37+
* "next" references.
38+
**/
39+
40+
/**
41+
* newNode() calls the DListNode constructor. Use this method to allocate
42+
* new DListNodes rather than calling the DListNode constructor directly.
43+
* That way, only this method need be overridden if a subclass of DList
44+
* wants to use a different kind of node.
45+
*
46+
* @param item the item to store in the node.
47+
* @param list the list that owns this node. (null for sentinels.)
48+
* @param prev the node previous to this node.
49+
* @param next the node following this node.
50+
**/
51+
protected DListNode newNode(Object item, DList list, DListNode prev, DListNode next)
52+
{
53+
return new DListNode(item, list, prev, next);
54+
}
55+
56+
/**
57+
* DList() constructs for an empty DList.
58+
**/
59+
public DList()
60+
{
61+
// Your solution here. Similar to Homework 4, but now you need to
62+
// specify
63+
// the `list' field (second parameter) as well.
64+
head = newNode(Integer.MIN_VALUE, null, null, null);
65+
head.next = head;
66+
head.prev = head;
67+
size = 0;
68+
}
69+
70+
/**
71+
* insertFront() inserts an item at the front of this DList.
72+
*
73+
* @param item is the item to be inserted.
74+
*
75+
* Performance: runs in O(1) time.
76+
**/
77+
public void insertFront(Object item)
78+
{
79+
// Your solution here. Similar to Homework 4, but now you need to
80+
// specify
81+
// the `list' field (second parameter) as well.
82+
DListNode front = newNode(item, this, head, head.next);
83+
head.next.prev = front;
84+
head.next = front;
85+
size++;
86+
}
87+
88+
/**
89+
* insertBack() inserts an item at the back of this DList.
90+
*
91+
* @param item is the item to be inserted.
92+
*
93+
* Performance: runs in O(1) time.
94+
**/
95+
public void insertBack(Object item)
96+
{
97+
// Your solution here. Similar to Homework 4, but now you need to
98+
// specify
99+
// the `list' field (second parameter) as well.
100+
DListNode back = newNode(item, this, head.prev, head);
101+
head.prev.next = back;
102+
head.prev = back;
103+
size++;
104+
}
105+
106+
/**
107+
* front() returns the node at the front of this DList. If the DList is
108+
* empty, return an "invalid" node--a node with the property that any
109+
* attempt to use it will cause an exception. (The sentinel is "invalid".)
110+
*
111+
* DO NOT CHANGE THIS METHOD.
112+
*
113+
* @return a ListNode at the front of this DList.
114+
*
115+
* Performance: runs in O(1) time.
116+
*/
117+
public ListNode front()
118+
{
119+
return head.next;
120+
}
121+
122+
/**
123+
* back() returns the node at the back of this DList. If the DList is
124+
* empty, return an "invalid" node--a node with the property that any
125+
* attempt to use it will cause an exception. (The sentinel is "invalid".)
126+
*
127+
* DO NOT CHANGE THIS METHOD.
128+
*
129+
* @return a ListNode at the back of this DList.
130+
*
131+
* Performance: runs in O(1) time.
132+
*/
133+
public ListNode back()
134+
{
135+
return head.prev;
136+
}
137+
138+
/**
139+
* toString() returns a String representation of this DList.
140+
*
141+
* DO NOT CHANGE THIS METHOD.
142+
*
143+
* @return a String representation of this DList.
144+
*
145+
* Performance: runs in O(n) time, where n is the length of the list.
146+
*/
147+
public String toString()
148+
{
149+
String result = "[ ";
150+
DListNode current = head.next;
151+
while (current != head)
152+
{
153+
result = result + current.item + " ";
154+
current = current.next;
155+
}
156+
return result + "]";
157+
}
158+
159+
public void remove(DListNode node)
160+
{
161+
node.prev.next = node.next;
162+
node.next.prev = node.prev;
163+
node.prev = null;
164+
node.next = null;
165+
size--;
166+
}
167+
168+
public DListNode find(Object item) throws InvalidNodeException
169+
{
170+
DListNode cur = head.next;
171+
while(cur != null)
172+
{
173+
if(cur.item() == item)
174+
{
175+
return cur;
176+
}
177+
cur = cur.next;
178+
}
179+
return null;
180+
}
181+
182+
private static void testInvalidNode(ListNode p)
183+
{
184+
System.out.println("p.isValidNode() should be false: " + p.isValidNode());
185+
try
186+
{
187+
p.item();
188+
System.out.println("p.item() should throw an exception, but didn't.");
189+
}
190+
catch (InvalidNodeException lbe)
191+
{
192+
System.out.println("p.item() should throw an exception, and did.");
193+
}
194+
try
195+
{
196+
p.setItem(new Integer(0));
197+
System.out.println("p.setItem() should throw an exception, but didn't.");
198+
}
199+
catch (InvalidNodeException lbe)
200+
{
201+
System.out.println("p.setItem() should throw an exception, and did.");
202+
}
203+
try
204+
{
205+
p.next();
206+
System.out.println("p.next() should throw an exception, but didn't.");
207+
}
208+
catch (InvalidNodeException lbe)
209+
{
210+
System.out.println("p.next() should throw an exception, and did.");
211+
}
212+
try
213+
{
214+
p.prev();
215+
System.out.println("p.prev() should throw an exception, but didn't.");
216+
}
217+
catch (InvalidNodeException lbe)
218+
{
219+
System.out.println("p.prev() should throw an exception, and did.");
220+
}
221+
try
222+
{
223+
p.insertBefore(new Integer(1));
224+
System.out.println("p.insertBefore() should throw an exception, but " + "didn't.");
225+
}
226+
catch (InvalidNodeException lbe)
227+
{
228+
System.out.println("p.insertBefore() should throw an exception, and did.");
229+
}
230+
try
231+
{
232+
p.insertAfter(new Integer(1));
233+
System.out.println("p.insertAfter() should throw an exception, but " + "didn't.");
234+
}
235+
catch (InvalidNodeException lbe)
236+
{
237+
System.out.println("p.insertAfter() should throw an exception, and did.");
238+
}
239+
try
240+
{
241+
p.remove();
242+
System.out.println("p.remove() should throw an exception, but didn't.");
243+
}
244+
catch (InvalidNodeException lbe)
245+
{
246+
System.out.println("p.remove() should throw an exception, and did.");
247+
}
248+
}
249+
250+
private static void testEmpty()
251+
{
252+
List l = new DList();
253+
System.out.println("An empty list should be [ ]: " + l);
254+
System.out.println("l.isEmpty() should be true: " + l.isEmpty());
255+
System.out.println("l.length() should be 0: " + l.length());
256+
System.out.println("Finding front node p of l.");
257+
ListNode p = l.front();
258+
testInvalidNode(p);
259+
System.out.println("Finding back node p of l.");
260+
p = l.back();
261+
testInvalidNode(p);
262+
l.insertFront(new Integer(10));
263+
System.out.println("l after insertFront(10) should be [ 10 ]: " + l);
264+
}
265+
266+
public static void main(String[] argv)
267+
{
268+
testEmpty();
269+
List l = new DList();
270+
l.insertFront(new Integer(3));
271+
l.insertFront(new Integer(2));
272+
l.insertFront(new Integer(1));
273+
System.out.println("l is a list of 3 elements: " + l);
274+
try
275+
{
276+
ListNode n;
277+
int i = 1;
278+
for (n = l.front(); n.isValidNode(); n = n.next())
279+
{
280+
System.out.println("n.item() should be " + i + ": " + n.item());
281+
n.setItem(new Integer(((Integer) n.item()).intValue() * 2));
282+
System.out.println("n.item() should be " + 2 * i + ": " + n.item());
283+
i++;
284+
}
285+
System.out.println("After doubling all elements of l: " + l);
286+
testInvalidNode(n);
287+
288+
i = 6;
289+
for (n = l.back(); n.isValidNode(); n = n.prev())
290+
{
291+
System.out.println("n.item() should be " + i + ": " + n.item());
292+
n.setItem(new Integer(((Integer) n.item()).intValue() * 2));
293+
System.out.println("n.item() should be " + 2 * i + ": " + n.item());
294+
i = i - 2;
295+
}
296+
System.out.println("After doubling all elements of l again: " + l);
297+
testInvalidNode(n);
298+
299+
n = l.front().next();
300+
System.out.println("Removing middle element (8) of l: " + n.item());
301+
n.remove();
302+
System.out.println("l is now: " + l);
303+
testInvalidNode(n);
304+
n = l.back();
305+
System.out.println("Removing end element (12) of l: " + n.item());
306+
n.remove();
307+
System.out.println("l is now: " + l);
308+
testInvalidNode(n);
309+
310+
n = l.front();
311+
System.out.println("Removing first element (4) of l: " + n.item());
312+
n.remove();
313+
System.out.println("l is now: " + l);
314+
testInvalidNode(n);
315+
}
316+
catch (InvalidNodeException lbe)
317+
{
318+
System.err.println("Caught InvalidNodeException that should not happen.");
319+
System.err.println("Aborting the testing code.");
320+
}
321+
}
322+
}

0 commit comments

Comments
 (0)