CITS2200 - Lecture 13

← Back to Home

CITS2200 - Lecture 12
Linked Lists - Slides

Linked List

• Linked lists are a sequence of nodes connected by pointers
  • No fixed block in memory
  • Nodes can be anywhere in RAM
• This is different to Python lists:
  • Python lists are arrays and have contiguous memory

Linked List Operations

4 Key Operations:

1. Insert at head $-$ $O(1)$
   • Allocate new node
   • Set new node’s next → old head
   • Update head → new node
2. Remove at head $-$ $O(1)$
   • Mode head → head.next
   • Old head has no references → GC reclaims it
     • GC $-$ garbage collector
3. Insert at tail $-$ $O(1)$
   • Allocate new node, set next → None
   • Old tail’s next → new node
   • Update tail → new node
4. Remove at tail $-$ $O(n)$
   • No quick way to find the node before the tail
   • We must traverse the whole list → inefficient

Operation	Time	Notes
Insert at head	O(1)	Update head pointer
Remove at head	O(1)	Move head → head.next
Insert at tail	O(1)	Need tail pointer
Remove at tail	O(n)	⚠️ Must traverse entire list

---

Stack as Linked List

• Top element = first node (head)
• push(e) → insert at head → O(1)
• pop() → remove at head → O(1)
• Space: O(n), all ops: O(1)

Queue as Linked List

• Front = head, Rear = tail
• enqueue(e) → insert at tail → O(1)
• dequeue() → remove at head → O(1)
• ! Special case: if queue empties during dequeue, set _tail = None

---

CITS2200 - Lecture 14