01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
package ds1.student.linked;
// ListDrawing. Practice drawing lists.
//
// This is a "written homework" assignment. You do NOT need to submit this file with solutions as part of this homework.
// You DO need to submit your answers to the questions posed below.
//
// Look for the TODO below, in the main method. Hand in your drawings of the lists requested.
public class ListDrawing {
private Node first;
private int N;
private static class Node {
final double item;
Node next;
Node(double item, Node next) {
this.item = item;
this.next = next;
}
}
public void insert(double item) {
if (first == null || first.item >= item) {
first = new Node(item, first);
} else {
Node x = first;
while (x.next != null && x.next.item < item) {
x = x.next;
}
x.next = new Node(item, x.next);
}
N++;
}
public void delete (int k) {
if (k < 0 || k >= N) throw new IllegalArgumentException ();
if(k == 0) first = first.next;
else {
Node prev = first;
for(int i = 1; i < k; i++) {
prev = prev.next;
}
prev.next = prev.next.next;
}
N--;
}
public static void main(String[] args) {
ListDrawing list1 = listOf(4, 7, 9, 11);
list1.insert(3);
ListDrawing list2 = listOf(4, 7, 9, 11);
list2.insert(8);
ListDrawing list3 = listOf(4, 7, 9, 11);
list3.insert(13);
ListDrawing list4 = listOf(4, 7, 9, 11);
list4.delete(0);
ListDrawing list5 = listOf(4, 7, 9, 11);
list5.insert(10);
list5.insert(12);
list5.delete(2);
// TODO: Draw each list declared above, i.e. list1, list2, list3, list4, list5, before the main program exits.
// NOTE: On an exam, you will need to be able to look at code that operates on linked structures and draw the result.
// You should try to understand how this code is manipulating the pointers in the list. You can (and should) use
// the debugger to stop the execution of the code and look at the memory that this code uses as it executes.
}
private static ListDrawing listOf(double... items) {
Node next = null;
for (int i = items.length - 1; i >= 0; i--) {
next = new Node(items[i], next);
}
ListDrawing list = new ListDrawing();
list.first = next;
list.N = items.length;
return list;
}
}
|