Collection
**Collection** is a group of items that we want to treat as conceptual unit. Collections can be
homogeneous when all items in the collection must be of the same type, or heterogeneous when items can be of different types. For example, lists are heterogeneous in Python.
linear collection
grocery lists, queue
hierarchical collection
upside down tree, something similiar to this file
graph collection
Each data item can have many predecessors and many successors
Unordered collection
self explanatory
Free Space List: a linked list that acts as resource and recycle of nodes for data structures (linked list, stack, queue, BST)
Linked-list insertion and deletion from the beginning
For WA2, you need to understand a singly linked list.
A linked list is a chain of nodes:
head
↓
[A | •] → [B | •] → [C | None]
Each node stores:
[data | next]
datais the value inside the node.nextrefers to the next node.headrefers to the first node.Nonemeans there is no next node.
Your notes require insertion and deletion by position or value, and the revision papers test inserting at the fourth position and deleting the first node containing a target value. 8.DataStructures.pdfPDF WA2 Revision Paper 1 soln.pdfPDF WA2 Revision Paper 2 soln.pdfPDF
1. The basic classes
class Node:
def __init__(self, data):
self.data = data
self.next = None
Creating one node:
node1 = Node("A")
produces:
node1
↓
[A | None]
A linked-list class stores the head:
class LinkedList:
def __init__(self):
self.head = None
Initially:
self.head → None
This means the linked list is empty.
2. Four variables you must understand
| Variable | Meaning |
|---|---|
self.head | First node in the list |
curr | The node we are currently looking at |
prev | The node immediately before curr |
new_node | A node we want to insert |
Example:
head → [A] → [B] → [C] → None
↑ ↑
prev curr
Here:
prev.data = "A"
curr.data = "B"
curr.next refers to C
3. The central idea
Insertion
Insertion means:
Change the arrows so the new node becomes part of the chain.
Before:
[A] → [B] → [C]
Insert X after B:
[A] → [B] → [X] → [C]
Deletion
Deletion means:
Change an arrow so that it skips the node being deleted.
Before:
[A] → [B] → [C]
Delete B:
[A] ─────→ [C]
The most important difference is:
Insertion: add an arrow through the new node
Deletion: bypass an existing node
Part A: Insertion
4. Insert at the front
Before:
head → [B] → [C] → None
new_node → [A] → None
We want:
head → [A] → [B] → [C] → None
Code
new_node.next = self.head
self.head = new_node
Line 1
new_node.next = self.head
self.head currently refers to B.
Therefore:
A.next = B
Now:
new_node → [A] → [B] → [C] → None
But head still points to B.
Line 2
self.head = new_node
Now head points to A:
head → [A] → [B] → [C] → None
Complete method
def insert_front(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
Usage:
my_list.insert_front("A")
Memory sentence
Connect the new node to the old head, then make it the new head.
5. Insert after a particular node
Before:
[A] → [B] → [C] → None
↑
curr
We want to insert X after B.
[A] → [B] → [X] → [C] → None
Code
new_node.next = curr.next
curr.next = new_node
Line 1
new_node.next = curr.next
curr points to B.
curr.next points to C.
Therefore:
X.next = C
Line 2
curr.next = new_node
This means:
B.next = X
Final list:
[A] → [B] → [X] → [C] → None
Why must the lines be in this order?
Correct:
new_node.next = curr.next
curr.next = new_node
First, make X remember where C is.
Then connect B to X.
If you replaced B.next too early, you could lose the reference to C.
Memory sentence
New points forward first; previous node points to new second.
6. Insert at a given position
We will number positions starting from 1:
Position 1 2 3 4
head → [A] → [B] → [C] → [D] → None
Suppose we want to insert X at position 4:
Position 1 2 3 4 5
head → [A] → [B] → [C] → [X] → [D] → None
To insert at position 4, we must stop at position 3.
Why?
Because position 3 is the node before the insertion position.
[C].next must change from D to X
Moving to the predecessor
curr = self.head
for count in range(position - 2):
curr = curr.next
For position 4:
position - 2 = 2
Start at position 1 and move twice:
A → B → C
Now curr points to C.
Then insert:
new_node.next = curr.next
curr.next = new_node
This is the same pointer pattern used in your revision paper’s fourth-position insertion solution. WA2 Revision Paper 2 soln.pdfPDF
Complete method
def insert_at_position(self, data, position):
if position < 1:
print("Invalid position")
return
new_node = Node(data)
# Special case: insert at the front
if position == 1:
new_node.next = self.head
self.head = new_node
return
# Move to the node before the insertion position
curr = self.head
for count in range(position - 2):
if curr is None:
print("Invalid position")
return
curr = curr.next
# If curr is None, the position is beyond the list
if curr is None:
print("Invalid position")
return
new_node.next = curr.next
curr.next = new_nodeExample
Starting list:
head → [A] → [B] → [C] → None
Call:
my_list.insert_at_position("X", 3)
The method stops at position 2, which is B.
Then:
new_node.next = curr.next
means:
X.next = C
and:
curr.next = new_node
means:
B.next = X
Final list:
head → [A] → [B] → [X] → [C] → None
7. Insert after a given value
Suppose:
head → [A] → [B] → [C] → None
We want to insert X after the node containing B.
First, search for B.
curr = self.head
while curr is not None and curr.data != target:
curr = curr.next
When the loop ends:
currpoints to the target node, orcurrisNoneif the target was not found.
Complete method
def insert_after_value(self, target, data):
curr = self.head
# Search for the target
while curr is not None and curr.data != target:
curr = curr.next
if curr is None:
print("Target not found")
return
new_node = Node(data)
new_node.next = curr.next
curr.next = new_nodeUsage:
my_list.insert_after_value("B", "X")
Result:
[A] → [B] → [X] → [C] → None
8. Insert in alphabetical or numerical order
Your past paper describes a spellbook stored in alphabetical order. The question itself tests deletion, but you should understand how sorted insertion works. WA2 Revision Paper 1 soln.pdfPDF
Suppose:
Apple → Mango → Pear
We want to insert Banana.
It belongs between Apple and Mango.
Code
def insert_sorted(self, data):
new_node = Node(data)
# Insert at the front if the list is empty
# or the new value comes before the first value
if self.head is None or data < self.head.data:
new_node.next = self.head
self.head = new_node
return
curr = self.head
# Stop when the next value is greater than the new value
while curr.next is not None and curr.next.data < data:
curr = curr.next
new_node.next = curr.next
curr.next = new_nodeResult:
Apple → Banana → Mango → Pear
Do not memorise this before you understand ordinary insertion. The two crucial pointer lines are still:
new_node.next = curr.next
curr.next = new_node
Part B: Deletion
9. Delete the first node
Before:
head → [A] → [B] → [C] → None
To delete A, move head forward:
self.head = self.head.next
self.head.next refers to B.
After:
head → [B] → [C] → None
Complete method
def delete_front(self):
if self.head is None:
print("Linked list is empty")
return
self.head = self.head.nextMemory sentence
Deleting the first node means moving
headforward once.
10. Delete a middle node
Before:
[A] → [B] → [C] → None
↑ ↑
prev curr
We want to delete B.
prev points to A.
curr points to B.
curr.next points to C.
Code
prev.next = curr.next
This means:
A.next = C
After:
[A] ─────→ [C] → None
B has been bypassed.
Memory sentence
Make the previous node point to the node after the deleted node.
11. Delete by value
Suppose:
head → [A] → [B] → [C] → None
We want to delete the first node containing B.
There are three cases.
Case 1: The list is empty
head → None
There is nothing to delete.
if self.head is None:
print("Linked list is empty")
Case 2: The target is at the head
head → [B] → [C] → None
Delete it using:
self.head = self.head.next
Case 3: The target is later in the list
Use two variables:
prev = self.head
curr = self.head.next
Then search:
while curr is not None and curr.data != target:
prev = curr
curr = curr.next
When the target is found:
prev.next = curr.next
Complete method
def remove(self, target):
# Case 1: empty list
if self.head is None:
print("Linked list is empty")
return
# Case 2: target is at the head
if self.head.data == target:
self.head = self.head.next
return
# Case 3: target is later in the list
prev = self.head
curr = self.head.next
while curr is not None and curr.data != target:
prev = curr
curr = curr.next
if curr is None:
print("Target not found")
else:
prev.next = curr.nextThis is the main WA2-style deletion method from your first revision paper. WA2 Revision Paper 1 soln.pdfPDF
Example trace
List:
[A] → [B] → [C] → [D] → None
Target:
C
Initially:
prev → A
curr → B
B is not C, so move both:
prev → B
curr → C
Now the target is found.
Run:
prev.next = curr.next
This means:
B.next = D
Final list:
[A] → [B] → [D] → None
12. Why the while condition is written in this order
Use:
while curr is not None and curr.data != target:
Do not use:
while curr.data != target and curr is not None:
Why?
If curr is None, this is illegal:
curr.data
None has no data attribute.
Therefore, always check:
curr is not None
before accessing:
curr.data
13. Delete by position
Positions start from 1:
Position 1 2 3 4
head → [A] → [B] → [C] → [D] → None
Suppose we want to delete position 3, containing C.
We need to stop at position 2, containing B.
Then:
prev.next = prev.next.next
prev.next is C.
prev.next.next is D.
Therefore:
B.next = D
Complete method
def delete_at_position(self, position):
if position < 1:
print("Invalid position")
return
if self.head is None:
print("Linked list is empty")
return
# Special case: delete the first node
if position == 1:
self.head = self.head.next
return
# Move to the node before the deletion position
prev = self.head
for count in range(position - 2):
if prev is None:
print("Invalid position")
return
prev = prev.next
# The node to delete must exist
if prev is None or prev.next is None:
print("Invalid position")
return
prev.next = prev.next.nextExample
head → [A] → [B] → [C] → [D] → None
Call:
my_list.delete_at_position(3)
Move to position 2:
prev → B
Then:
prev.next = prev.next.next
becomes:
B.next = D
Final list:
head → [A] → [B] → [D] → None
14. Deleting the last node
You do not need a completely different algorithm.
Example:
[A] → [B] → [C] → None
To delete C:
prev → B
curr → C
Then:
prev.next = curr.next
Since:
curr.next = None
this becomes:
B.next = None
Final list:
[A] → [B] → None
The same deletion pattern works for middle and last nodes.
15. Complete beginner-friendly class
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def display(self):
curr = self.head
while curr is not None:
print(curr.data)
curr = curr.next
def insert_front(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_at_position(self, data, position):
if position < 1:
print("Invalid position")
return
new_node = Node(data)
if position == 1:
new_node.next = self.head
self.head = new_node
return
curr = self.head
for count in range(position - 2):
if curr is None:
print("Invalid position")
return
curr = curr.next
if curr is None:
print("Invalid position")
return
new_node.next = curr.next
curr.next = new_node
def remove(self, target):
if self.head is None:
print("Linked list is empty")
return
if self.head.data == target:
self.head = self.head.next
return
prev = self.head
curr = self.head.next
while curr is not None and curr.data != target:
prev = curr
curr = curr.next
if curr is None:
print("Target not found")
else:
prev.next = curr.next
def delete_at_position(self, position):
if position < 1:
print("Invalid position")
return
if self.head is None:
print("Linked list is empty")
return
if position == 1:
self.head = self.head.next
return
prev = self.head
for count in range(position - 2):
if prev is None:
print("Invalid position")
return
prev = prev.next
if prev is None or prev.next is None:
print("Invalid position")
return
prev.next = prev.next.nextUsing it
my_list = LinkedList()
my_list.insert_front("C")
my_list.insert_front("B")
my_list.insert_front("A")List:
A → B → C
Display:
my_list.display()
Output:
A
B
C
Insert X at position 3:
my_list.insert_at_position("X", 3)
List:
A → B → X → C
Delete B:
my_list.remove("B")
List:
A → X → C
Delete position 2:
my_list.delete_at_position(2)
List:
A → C
16. Pseudocode versions for exams
Insert at position i
IF i = 1 THEN
new.next ← head
head ← new
ELSE
curr ← head
FOR count ← 1 TO i - 2
curr ← curr.next
ENDFOR
new.next ← curr.next
curr.next ← new
ENDIFYour notes describe the same two insertion cases: insertion at the front updates head, while insertion at position i updates the link of the node at position i - 1. 8.DataStructures.pdfPDF
Delete by value
IF head = NULL THEN
OUTPUT "Linked list is empty"
ELSE IF head.data = target THEN
head ← head.next
ELSE
prev ← head
curr ← head.next
WHILE curr <> NULL AND curr.data <> target
prev ← curr
curr ← curr.next
ENDWHILE
IF curr = NULL THEN
OUTPUT "Target not found"
ELSE
prev.next ← curr.next
ENDIF
ENDIFPart C: Array implementation and free-space list
Your teacher also highlighted:
- Linked list implemented using arrays
- Free-space list
Tutorial 8A explicitly includes linked lists stored using arrays and managing free space when adding or deleting items. 8.DataStructures.pdfPDF
17. Parallel-array linked list
Instead of storing actual Python node objects, we can use two arrays:
Data[index]
Next[index]
Example:
| Index | Data | Next |
|---|---|---|
| 0 | B | 3 |
| 1 | — | -1 |
| 2 | A | 0 |
| 3 | C | -1 |
Suppose:
Start = 2
Follow the indexes:
Start = 2
Data[2] = A
Next[2] = 0
Data[0] = B
Next[0] = 3
Data[3] = C
Next[3] = -1Logical list:
A → B → C
-1 plays the same role as None.
18. What is the free-space list?
Unused array positions are also linked together.
Suppose positions 1 and 4 are unused:
Free = 1
and:
Next[1] = 4
Next[4] = -1
Free-space chain:
Free → index 1 → index 4 → -1
This means positions 1 and 4 are available for new nodes.
The slides require this concept; the following algorithms are the standard Start, Free, Data and Next implementation consistent with those exercises.
19. Taking a space during insertion
Suppose:
Free = 1
Next[1] = 4
Use the first free position:
new_index = Free
Free = Next[Free]
Afterwards:
new_index = 1
Free = 4
Index 1 has been removed from the free-space list.
Store the new data:
Data[new_index] = new_item
Insert at the front
Next[new_index] = Start
Start = new_index
This is the array equivalent of:
new_node.next = head
head = new_node
Comparison:
| Object version | Array version |
|---|---|
new_node.next = head | Next[new_index] = Start |
head = new_node | Start = new_index |
20. Returning a space during deletion
Suppose we delete the node at delete_index.
After removing it from the main list, return it to the front of the free-space list:
Next[delete_index] = Free
Free = delete_index
This is similar to inserting the deleted index at the front of the free-space chain.
You may also clear its data:
Data[delete_index] = None
21. Array insertion and deletion templates
Insert at front
if Free == -1:
print("No free space")
else:
new_index = Free
Free = Next[Free]
Data[new_index] = new_item
Next[new_index] = Start
Start = new_indexDelete front
if Start == -1:
print("List is empty")
else:
delete_index = Start
Start = Next[Start]
Data[delete_index] = None
Next[delete_index] = Free
Free = delete_indexInsert after index curr
new_index = Free
Free = Next[Free]
Data[new_index] = new_item
Next[new_index] = Next[curr]
Next[curr] = new_index
Delete the node after index prev
delete_index = Next[prev]
Next[prev] = Next[delete_index]
Data[delete_index] = None
Next[delete_index] = Free
Free = delete_index
The six code patterns to memorise
# 1. Move forward
curr = curr.next
# 2. Insert at front
new_node.next = self.head
self.head = new_node
# 3. Insert after curr
new_node.next = curr.next
curr.next = new_node
# 4. Delete front
self.head = self.head.next
# 5. Delete curr
prev.next = curr.next
# 6. Search
while curr is not None and curr.data != target:
curr = curr.next
Final memory picture
INSERT AFTER curr
Before:
curr → [B] → [C]
Step 1:
new → [X] → [C]
Step 2:
curr → [B] → [X] → [C]
DELETE curr
Before:
prev → [A] → [B] → [C]
↑
curr
Change:
prev.next = curr.next
After:
[A] ─────────→ [C]The two most important lines for WA2 are:
new_node.next = curr.next
curr.next = new_node
and:
prev.next = curr.next