# Lecture - Imperative Programming HT23, XIV

> Source: https://ollybritton.com/notes/uni/prelims/ht23/ip/lectures/xiv/ · Updated: 2023-02-17 · Tags: uni, lecture

### Notes
```scala
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.

```scala
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.

### Links
- [Notes - Imperative Programming HT23, Linked lists](https://ollybritton.com/notes/uni/prelims/ht23/ip/notes/linked-lists/)

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt