The Node class
Consider the following class Point:
1
2
3
4
5
6
7
public class Point {
public int x, y;
public Point(int _x, int _y) {
x = _x;
y = _y;
}
}
Next, consider classs Line:
1
2
3
4
5
6
7
public class Line {
public Point start, end;
public Line(Point p1, Point p2) {
start = p1;
end = p2;
}
}
If I create an object of Line as:
1
2
3
Point p = new Point(10, 40);
Point q = new Point(70, 60);
Line line = new Line(p, q);
One can also create anonymous objects thereby reducing the number of objects and variables to keep track of.
1
Line line = new Line(new Point(10, 40), new Point(70, 60));
The Node class
Now, consider the following class:
1
2
3
4
5
6
7
8
9
public class Node {
public int data;
public Node next;
public Node(int d, Node n) {
data = d;
next = n;
}
}
Every Node object holds a reference to another Node object.
Here, we created an anonymous Node object - new Node(10, null) - and passed it as a parameter to the constructor of head.
Linking nodes
We can link any number of nodes as we want.
1
2
3
4
5
Node n5 = new Node(20, null);
Node n4 = new Node(70, n5);
Node n3 = new Node(10, n4);
Node n2 = new Node(90, n3);
Node n1 = new Node(30, n2);
Simplified representaton:
We can get all the values just using n1.
1
2
3
4
5
System.out.println(n1.data); //30
System.out.println(n1.next.data); //90
System.out.println(n1.next.next.data); //10
System.out.println(n1.next.next.next.data); //70
System.out.println(n1.next.next.next.next.data); //20
If we create a Node reference temp initialized to n1, we can re-reference it to the Node after it using temp = temp.next. Thereby, repeating the operation over and over.
1
2
3
4
5
6
Node temp = n1; //temp refers to same instance as n1
temp = temp.next; //temp refers to node after temp or n1 which is n2
temp = temp.next; //temp refers to node after temp or n2 which is n3
temp = temp.next; //temp refers to n4
temp = temp.next; //temp refers to n5
temp = temp.next; //temp is now null - STOP
Abstracting into a loop to add all the values:
1
2
3
4
5
6
Node temp = n1;
int total = 0;
while(temp != null) {
total = total + temp.data;
temp = temp.next;
}
Nodes can hold other objects too
In the previous example, we saw a node holding integer data, but it can hold any kind of data. For starters, take a look at RNode holding Rectangle object.
For the classes defined in,
Consider the following code,
1
2
3
4
Rectangle r1 = new Rectangle(2.5, 1.5);
Rectangle r2 = new Rectangle(4.2, 3.6);
RNode q = new RNode(r2, null);
RNode p = new RNode(r1, p);
We can create anonymous objects to reduce variable count.
1
2
RNode q = new RNode(new Rectangle(4.2, 3.6), null);
RNode p = new RNode(new Rectangle(2.5, 1.5), p);
Homework exercises
Task 1
For the class Node, draw the memory diagram to illustrate objects after the last statement of the following code executes.
1
2
3
4
Node a = new Node(20, null);
Node b = new Node(70, a);
Node c = new Node(10, a);
Node d = new Node(90, c);
Task 2
For the class Node, draw the memory diagram to illustrate objects after the last statement of the following code executes.
1
2
3
4
5
Node a = new Node(20, null);
Node b = new Node(70, a);
Node c = new Node(10, b);
Node d = new Node(90, c);
a.next = d;
Task 3
For the class Node, draw the memory diagram to illustrate objects after the last statement of the following code executes.
1
2
3
4
5
Node a = new Node(20, null);
Node b = new Node(70, a);
Node c = new Node(10, b);
Node d = new Node(90, c);
a.next = d.next;
Task 4
For the class Node, draw the memory diagram to illustrate objects after the last statement of the following code executes.
1
2
3
4
5
Node a = new Node(20, null);
Node b = new Node(70, a);
Node c = new Node(10, b);
Node d = new Node(90, c);
a.next = d.next.next;
Task 5
For the class Node, the following code attempts to store the sum of all items in the chain of nodes into a varaible total. However, it has a a bug. Briefly explain what is the problem with the code, and correct it.
1
2
3
4
5
6
7
8
9
10
Node a = new Node(20, null);
Node b = new Node(70, a);
Node c = new Node(10, b);
Node d = new Node(90, c);
int total = 0;
Node current = d;
while(current != null) {
total = total + current;
current = current.next;
}
Task 6
For the class Node, the following code attempts to store the number of nodes in the chain into a variable size. However, it has a a bug. Briefly explain what is the problem with the code, and correct it.
1
2
3
4
5
6
7
8
9
Node a = new Node(20, null);
Node b = new Node(70, a);
Node c = new Node(10, b);
Node d = new Node(90, c);
int size = 0;
Node current = d;
while(current != null) {
size = size + 1;
}
Task 7
For the class Node, what is the value of result after the following code is executed?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node a = new Node(20, null);
Node b = new Node(70, a);
Node c = new Node(10, b);
Node d = new Node(90, c);
int result = 0;
Node current = d;
while(current != null) {
if(current.data >= 20) {
result = result * 10 + 1;
}
else {
result = result * 10;
}
current = current.next;
}
Task 8
For the class Node, what is the value of result after the following code executes?
1
2
3
4
5
6
7
8
9
Node a = new Node(9, null);
Node b = new Node(2, a);
Node c = new Node(7, b);
Node d = new Node(1, c);
a.next = d;
a.data = 1000*d.data +
100*d.next.data +
10*d.next.next.data +
1*d.next.next.next.data;
Task 9
Consider the following class definition for TreeNode:
1
2
3
4
5
6
7
8
9
public class TreeNode {
public int data;
public TreeNode left, right;
public TreeNode(int d, TreeNode l, TreeNode r) {
data = d;
left = l;
right = r;
}
}
Draw the memory diagram to illustrate objects after the last statement of the following code executes.
1
2
3
TreeNode t1 = new TreeNode(20, null, null);
TreeNode t2 = new TreeNode(-10, null, null);
TreeNode t3 = new TreeNode(70, t1, t2);