- Transition to Processing
- Primitive Operations
- Algorithms
- Variables
- Debugging in Processing
- Conditions
- Loops
- Functions
- Scope
- Compound Data
- Reference Semantics
- Refactoring
- Program Design
- Transition to Java
- Debugging in Java
- Unit Testing
- Classes - Writing your own Types
- Classes - Copying objects
- Classes - Functions inside objects
- Classes - Composition
- Classes - Array of objects
- Classes - Class holding array(s)
- Recursion - What goes on during a function call
- Recursion
- Recursion with String data
- Tail-optimized recursion
- Recursion with arrays
- Lists
- Iteration
- Custom-built ArrayList
- Recursive data structures - 1
- Recursive data structures - 2
- Searching

- Logic and Proofs
- Relations
- Mathematical Functions
- Matrices
- Binary Numbers
- Trigonomtry
- Finite State Machines
- Turing Machines
- Counting - Inclusion/Exclusion
- Graph Algorithms

- Algorithm Efficiency
- Algorithm Correctness
- Trees
- Heaps, Stack, and Queues
- Maps and Hashtables
- Graphs and Graph Algorithms
- Advanced Trees and Computability

- Command line control
- Transition to C
- Pointers
- Memory Allocation
- IO
- Number representations
- Assembly Programming
- Structs and Unions
- How memory works
- Virtual Memory

- Version Control with Git
- Inheritance and Overloading
- Generics
- Exceptions
- Lambda Expressions
- Design Patterns
- Concepts of Concurrency
- Concurrency: Object Locks
- Modern Concurrency

- System Models
- Naming and Distributed File Systems
- Synchronisation and Concurrency
- Fault Tolerance and Security
- Clusters and Grids
- Virtualisation
- Data Centers
- Mobile Computing

- Transition to Scala
- Functional Programming
- Syntax Analysis
- Name Analysis
- Type Analysis
- Transformation and Compilation
- Control Abstraction
- Implementing Data Abstraction
- Language Runtimes

- Transition to Coq
- Proof by Induction, Structured Data
- Polymorphism and Higher-Order Functions
- More Basic Tactics
- Logical Reasoning in Proof Assistants
- Inductive Propositions
- Maps
- An Imperative Programming Language
- Program Equivalence
- Hoare Logic
- Small-Step Operational Semantics
- Simply-typed Lambda Calculus

- 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

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

public class MyLinkedList {
public Node head;
}

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) {
MyLinkedList list1 = new MyLinkedList();
Node p = new Node(10, null);
list1.head = p;
MyLinkedList list2 = new MyLinkedList();
Node q = new Node(40, null);
Node r = new Node(20, q);
list2.head = r;
}
}

`list1`

has a single instance variable,`head`

, that refers to`p`

, which in turn, refers to`null`

.list1.head -> p -> 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`

.

1
2
3
4
5
6
7
8
9
10
11

public class MyLinkedList {
public Node head;
public void display() {
Node current = head; //create temporary reference to update
while(current != null) {
System.out.println(current.data); //use current for ... whatever
current = current.next; //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

//in class MyLinkedList
public int sum() {
Node current = head; //create temporary reference to update
int result = 0;
while(current != null) {
result = result + current.data;
current = current.next; //move it to the next node
}
return result;
}

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

1
2
3
4
5
6
7
8
9
10

//in class MyLinkedList
public int size() {
Node current = head; //create temporary reference to update
int count = 0;
while(current != null) {
count = count + 1;
current = current.next; //move it to the next node
}
return count;
}

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
}

1
2
3
4

public void addToFront(int item) {
Node temp = new Node(item, head);
head = temp;
}

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.

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
if(head == null) {
return null;
}
int result = head.data;
head = head.next; //update head
return result;
}

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.

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

public class MyLinkedList {
public Node head;
public void addToFront(int item) {
//create a node that has head as the next node
Node node = new Node(item, head);
//update head to new node
head = node;
}
public int size() {
Node current = head;
while(current != null) {
count++;
current = current.next;
}
return count;
}
public boolean itemExistsAt(int idx) {
return idx >= 0 && idx < size();
}
public String toString() {
Node current = head;
String result = "List: ";
while(current != null) {
result = result + current.data + " ";
current = current.next;
}
return result+"\n";
}
}

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:

- check if an item exists at the given index using
`itemExistsAt(int)`

- if not, return
`null`

- if it does, go to the item and return its value.

- if not, return

Now *“going”* to the item requires us to start at `head`

and move forward using `next`

, 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

Node current = head;
for(int i=0; i < idx; i++) {
current = current.next;
}

When the loop terminates, `current`

holds a reference to the `Node`

object whose value needs to be returned.

1

return current.data;

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
Node current = head;
for(int i=0; i < idx; i++) {
current = current.next;
}
return current.data;
}

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.

`head`

is updated)1
2
3
4
5

if(idx == 0) {
int itemRemoved = head.data;
head = head.next;
return itemRemoved;
}

`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

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

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

1
2
3

Node nodeToRemove = current.next;
int itemRemoved = nodeToRemove.data;
}

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.next = nodeToRemove.next;
return itemRemoved;

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) {
int itemRemoved = head.data;
head = head.next;
return itemRemoved;
}
Node current = head;
for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.next;
}
Node nodeToRemove = current.next;
int itemRemoved = nodeToRemove.data;
current.next = nodeToRemove.next;
return itemRemoved;
}

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.

`head`

is updated)1
2
3
4
5

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

`head`

is not updated)We get a reference to the item **before** where the item needs to be inserted.

1
2
3
4

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

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.next; //itemAfter will be null if node added to end of list
current.next = node;
node.next = itemAfter; //node.next will be null if node added to end of list
return true;

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) {
node.next = head;
head = node;
}
Node current = head;
for(int i=0; i < idx - 1; i++) { //moved forward idx-1 times
current = current.next;
}
Node itemAfter = current.next; //itemAfter will be null if node added to end of list
current.next = node;
node.next = itemAfter; //node.next will be null if node added to end of list
return true;
}

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`

.