Lecture - Imperative Programming HT23, XIV

class Node(name: String, number: String, next: Node)

Deleting from a linked list; find the previous node prev(n), and change the pointer on that node to the next node next(n). If there’s no previous node, this requires a special case. One way around this is to have the linked list start with a dummy header node.

def delete(name: String) : Boolean = {
	val n = find(name);
	if (n.next != null) {
		n.next = n.next.next
		true;
	}
	false;
}

Defining a class inside another class means that it won’t be possible to compare instances of the sub-class because they will technically be different types. Scala has a way to get around this called “companion objects”.
Linked list operations, appending to the end requires traversing the whole list. This can be fixed with a “tailed” linked list, which keeps an extra reference to the last entry of the list.
Doubly linked list, has a pointer to the previous element too – improves the implementation of the delete method. Allows navigation in both directions.
Circular linked list, the end of the lists points back to the beginning of the list.