# Software Technology: Build your own Recursive Lists

Assumed Knowledge
Learning Outcomes
• Understand the internal operation of recursively defined lists
• Be able to create standard list operations for a recursivly defined list
• Understand the time costs of various list operations

# STEP 1 - COMPOSITION

Consider the following class Point:

1
2
3
4
5
6
7
public class Point {
private 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 {
private Point start, end;
public Line(Point p1, Point p2) {
start = p1;
end = p2;
}
}


Pay attention to the following statement very carefully!

Each instance of class Line holds references to two instances of class Point.

(Informally, we say, each Line contains two Point objects)

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);


There are 5 references and 3 instances.

References (and types):

1. line: Line
2. line.start: Point
3. line.end: Point
4. p: Point
5. q: Point

Instances (and types):

1. instance to which line refers: Line
2. instance to which p and line.start refer: Point
3. instance to which q and line.end refer: Point

One can also create anonymous objects thereby reducing the number of references to keep track of.

1
Line line = new Line(new Point(10, 40), new Point(70, 60));


## Adding methods to the mix

Consider a slightly modified class definition of Point.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Point {
public int x, y;

public Point(int _x, int _y) {
x = _x;
y = _y;
}

public double distanceFromOrigin() {
return Math.sqrt(x*x + y*y);
}

public int compareTo(Point other) { //compare based on distance from origin
double d1 = this.distanceFromOrigin();
double d2 = other.distanceFromOrigin();
if(d1 > d2)
return 1;
if(d1 < d2)
return -1;
return 0;
}
}


We can then update the class Line to get the point on the line that is further from the origin, as,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Line {
public Point start, end;

public Line(Point p1, Point p2) {
start = p1;
end = p2;
}

public Point getPointFurtherFromOrigin() {
/*
* left for you as an exercise
* return p1 or p2 based on whichever is further from the origin
* return p1 if they are both equidistant from the origin
*/
}
}


# Homework - 1

Draw the memory diagram for the objects created inside the main method in the following code. Also, state the number of instances and references in the diagram.

1
2
3
4
5
6
7
8
9
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
class Date {
public int day, month, year;

public Date(int d, int m, int y) {
data = d;
month = m;
year = y;
}
}

class Time {
public int hour, minute, second;

public Time(int h, int m, int s) {
hour = h;
minute = m;
second = s;
}
}

class DateTime {
public Date date;
public Time time;

public Date(Date d, Time t) {
date = d;
time = t;
}
}

public class Client {
public static void main(String[] args) {
Date d1 = new Date(26, 5, 2020);
Time t1 = new Time(19, 54, 0);
DateTime dt1 = new DateTime(d1, t1);
}
}


Draw the memory diagram for the objects created inside the main method in the following code. Also, state the number of instances and references in the diagram.

1
2
3
4
5
6
7
8
9
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
class Date {
public int day, month, year;

public Date(int d, int m, int y) {
data = d;
month = m;
year = y;
}
}

class Time {
public int hour, minute, second;

public Time(int h, int m, int s) {
hour = h;
minute = m;
second = s;
}
}

class DateTime {
public Date date;
public Time time;

public Date(Date d, Time t) {
date = d;
time = t;
}
}

class QuizAttempt {
public DateTime start, end;
public int marksObtained;

public QuizAttempt(DateTime s, DateTime e, int m) {
start = s;
end = e;
marksObtained = m;
}
}

public class Client {
public static void main(String[] args) {
Date d1 = new Date(26, 5, 2020);
Time t1 = new Time(19, 54, 0);
DateTime dt1 = new DateTime(d1, t1);
Date d2 = new Date(27, 5, 2020);
Time t2 = new Time(01, 13, 40);
DateTime dt2 = new DateTime(d2, t2);
QuizAttempt attempt = new QuizAttempt(dt1, dt2, 40);
}
}


For the same code as task 2, write down statements that store the following values in variable of the correct type.

• The date on which the attempt began.
• The time at which the attempt ended.
• The minute at which the attempt began.
• The hour at which the attempt ended.
• The marks obtained in the attempt.
• Assuming the existence of the following method in class DateTime, the number of seconds taken for the attempt

1
2
3
4
5
6
public int getSecondsTo(DateTime other) {
//returns number of seconds between calling object
//and parameter object. returned value is positive if
//parameter object is after calling object in
//the chronological sense.
}


# The Node class

Now, consider the following class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Node {
private int data;
private Node next;

public int getData() {
return data;
}

public Node getNext() {
return next;
}

public void setData(int d) {
data = d;
}

public void setNext(Node n) {
next = n;
}

public Node(int d, Node n) {
data = d;
next = n;
}
}


Every Node object holds a reference to another Node object.

1
Node a = new Node(10, null);


1
Node b = new Node(20, a);


1
Node head = new Node(20, new Node(10, null));


Here, we created an anonymous Node object - new Node(10, null) - and passed it as a parameter to the constructor of head.

1


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.getData()); //30
System.out.println(n1.getNext().getData()); //90
System.out.println(n1.getNext().getNext().getData()); //10
System.out.println(n1.getNext().getNext().getNext().getData()); //70
System.out.println(n1.getNext().getNext().getNext().getNext().getData()); //20


If we create a Node reference temp initialized to n1, we can re-reference it to the Node after it using temp = temp.getNext(). 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.getNext(); //temp refers to node after temp or n1 which is n2
temp = temp.getNext(); //temp refers to node after temp or n2 which is n3
temp = temp.getNext(); //temp refers to n4
temp = temp.getNext(); //temp refers to n5
temp = temp.getNext(); //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.getData();
temp = temp.getNext();
}


## 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, q);


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), q);


# Homework - 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
Node a = new Node(20, null);
Node b = new Node(70, a);
Node c = new Node(10, a);
Node d = new Node(90, c);


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.setNext(d);


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.setNext(d.getNext());


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.setNext(d.getNext().getNext());


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.getNext();
}


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;
}


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.getData() >= 20) {
result = result * 10 + 1;
}
else {
result = result * 10;
}
current = current.getNext();
}


For the class Node, what is the value of result after the following code executes?

1
2
3
4
5
6
7
8
9
10
11
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.setNext(d);
a.setData	(
1000*d.getData() +
100*d.getNext().getData() +
10*d.getNext().getNext().getData() +
1*d.getNext().getNext().getNext().getData()
);


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. Also, state the number of instances and references in the diagram.

1
2
3
TreeNode t1 = new TreeNode(20, null, null);
TreeNode t2 = new TreeNode(-10, null, null);
TreeNode t3 = new TreeNode(70, t1, t2);


Now that we have taken a look at the Node class, we can construct a class that has a single Node object as instance variable.

1
2
3
}


As we saw in the last section, this node holds a reference to another node. That node could be null or could be a valid instance. A sample client:

1
2
3
4
5
6
7
8
9
10
11
12
public class Client {
public static void main(String[] args) {
Node p = new Node(10, null);

Node q = new Node(40, null);
Node r = new Node(20, q);
}
}

• list1 has a single instance variable, head, that refers to p, which in turn, refers to null.

• list2 has a single instance variable, head, that refers to r, which in turn refers to q, which in turn, refers to null.

list2.head -> r -> q -> null

The idea is that if we start at head, we can visit every node in the chain until we hit null.

#### For the rest of the document, we’ll change the visibility of head to private.

1
2
3
4
5
6
7
8
9
10
11

public void display() {
Node current = head; //create temporary reference to update
while(current != null) {
System.out.println(current.getData()); //use current for ... whatever
current = current.getNext(); //move it to the next node
}
}
}


The same logic can be used to add up all the items in the list, as,

1
2
3
4
5
6
7
8
9
10
public int sum() {
Node current = head; //create temporary reference to update
int result = 0;
while(current != null) {
result = result + current.getData();
current = current.getNext(); //move it to the next node
}
return result;
}


### Size of the list

We can add a method to determine size of the list, as,

1
2
3
4
5
6
7
8
9
10
public int size() {
Node current = head; //create temporary reference to update
int count = 0;
while(current != null) {
count = count + 1;
current = current.getNext(); //move it to the next node
}
return count;
}


### Checking if list is empty

If the list is empty, head is null

1
2
3
public boolean isEmpty() {
return head == null; //if head is null, return true, else return false
}


## Adding an item at the front

1
2
3
4
Node temp = new Node(item, head);
}


Note that if the list is empty, head is null, and so the newly added node has null as next node, which is correct.

If the list is not empty, temp has the current head as the next node, and then head is updated to refer to the added node.

## Removing the first item in the list

We also want to return the item removed.

If head is null, nothing can be removed, so we return null.

If head is not null, we store the item in a variable, update head to refer to the node after the current head and return the item removed

1
2
3
4
5
6
7
8
public Integer removeFirst() { //Integer so as to return null as error code
return null;
}
return result;
}


# Homework

Add an instance method to class MyLinkedList that returns true if the list is empty, false otherwise.

Add an instance method to class MyLinkedList that returns the first item in the list, if any, null otherwise. Based on this (null is returned if list is empty), think about the return type of the method before anything else.

Add an instance method to class MyLinkedList that returns the sum of all items in the list. Return 0 if the list is empty.

Add an instance method to class MyLinkedList that returns the sum of all positive items in the list. Return 0 if the list is empty or none of the items are positive.

Add an instance method to class MyLinkedList that returns true if all the items of the list are even numbers, false otherwise. Return true if the list is empty.

# Important methods in custom linkedlist

This section will assumes the following definition of MyLinkedList class;

1
2
3
4
5
6
7
8
9
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

//create a node that has head as the next node
Node node = new Node(item, head);

}

public int size() {
while(current != null) {
count++;
current = current.getNext();
}
return count;
}

public boolean itemExistsAt(int idx) {
return idx >= 0 && idx < size();
}

public String toString() {
String result = "List: ";
while(current != null) {
result = result + current.getData() + " ";
current = current.getNext();
}
return result+"\n";
}
}


## Getting an item at a specific index (if any)

1
2
3
4
5
/**
* @param idx: index of the node whose value should be returned
* @return: data value in the node if node exists, null otherwise
*/
public Integer get(int idx)


Steps involved:

1. check if an item exists at the given index using itemExistsAt(int)
1. if not, return null
2. if it does, go to the item and return its value.

Now “going” to the item requires us to start at head and move forward using getNext(), one at a time. How many times should we move forward by one?

Lets say, the list is head -> 10 -> 70 -> 20 -> 90 -> null.

idx = 0 => move 0 times idx = 1 => move 1 time idx = 2 => move 2 times …

In general, we need to move forward idx times.

1
2
3
4
for(int i=0; i < idx; i++) {
current = current.getNext();
}


When the loop terminates, current holds a reference to the Node object whose value needs to be returned.

1
return current.getData();


### Putting it together, get(int) is defined as:

1
2
3
4
5
6
7
8
9
10
11
12
public Integer get(int idx) {
if(itemExistsAt(idx) == false) {
return null;
}

//guaranteed that item DOES exist at index idx
for(int i=0; i < idx; i++) {
current = current.getNext();
}
return current.getData();
}


## Removing (and returning) an item at a specific index (if any)

1
2
3
4
5
/**
* @param idx: index of the node which should be removed
* @return: data value in the node if node existed and is now removed, null otherwise
*/
public Integer remove(int idx)


In the same manner as get(int), we will first check if an item exists at the given index. If it doesn’t, we return null.

1
2
3
if(itemExistsAt(idx) == false) {
return null;
}


If it exists, there are two sub-cases.

#### Case 1: removing item at index 0 (head is updated)

1
2
3
4
5
if(idx == 0) {
return itemRemoved;
}


#### Case 2: removing item at index 1 or beyond (head is not updated)

We need a reference to the node BEFORE the node to be removed. That is, the item at index idx - 1.

1
2
3
4
for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.getNext();
}


Then we make a backup copy of the value of the node to be removed.

1
2
3
Node nodeToRemove = current.getNext();
int itemRemoved = nodeToRemove.getData();
}


Finally, we make the node before the node to be removed refer (using next) to the node after the node to be removed, and return the value of the node removed.

1
2
current.setNext(nodeToRemove.getNext());
return itemRemoved;


### Putting it together, remove(int) is defined as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Integer remove(int idx) {
if(itemExistsAt(idx) == false) {
return null;
}

if(idx == 0) {
return itemRemoved;
}

for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.getNext();
}

Node nodeToRemove = current.getNext();
int itemRemoved = nodeToRemove.getData();

current.setNext(nodeToRemove.getNext());
return itemRemoved;
}


## Inserting an item at a given index

1
2
3
4
5
6
/**
* @param idx: index at which node should be inserted
* @param value: data value of the node to be inserted
* @return: true if node can be inserted at given index, false otherwise
*/
public boolean insert(int idx, int value)


In the same manner as get(int) and remove(int), we will first check if the item can be inserted at the given index.

If the list currently contains 4 items (at indices 0 through 3), a new node can be inserted at index 0 (before the first item) through 4 (after the last item).

Thus, the following condition checks if the item cannot be inserted and the method can return false.

1
2
3
if(idx < 0 || idx > size()) {
return false;
}


Now there are two sub-cases.

#### Case 1: inserting item at index 0 (head is updated)

1
2
3
4
5
Node node = new Node(value, null);
if(idx == 0) {
}


#### Case 2: inserting item at index 1 or beyond (head is not updated)

We get a reference to the item before where the item needs to be inserted.

1
2
3
4
for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.getNext();
}


In the diagrams, we illustrate the process when inserting value 50 between 10 and 70.

Finally, we insert the new node after it.

1
2
3
4
5
Node itemAfter = current.getNext(); //itemAfter will be null if node added to end of list
current.setNext(node);
node.setNext(itemAfter); //node.next will ne null if node added to end of list

return true;


### Putting it together, insert(int, int) is defined as:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean insert(int idx, int value) {
if(idx < 0 || idx > size()) {
return false;
}

Node node = new Node(value, null);
if(idx == 0) {
}

for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.getNext();
}

Node itemAfter = current.getNext(); //itemAfter will be null if node added to end of list
current.setNext(node);
node.setNext(itemAfter); //node.next will ne null if node added to end of list

return true;
}


# Homework - 3

Add an instance method to class MyLinkedList that reverses the list represented by the calling object. If the state of the list before calling the method is head -> 10 -> 70 -> 20 -> 90 -> null, its state, after the method executes, should be head -> 90 -> 20 -> 70 -> 10 -> null.