CITS2200 - Lecture 14

← Back to Home

CITS2200 - Lecture 13
Doubly-Linked Lists - Slides

Doubly Linked List

Core idea: what if a linked list could look both ways?

• A doubly linked list gives every node two pointers:
  • One to the previous node (prev) and one to the next (next)
  • This means you can traverse the list in either direction
• Each node stores three things: prev, next, and elem

---

Sentinel Nodes

Rather than dealing with messy edge cases when inserting at the start or end, a doubly linked list uses two dummy nodes called sentinels:

• header — sits before all real nodes, prev points to None
• trailer — sits after all real nodes, next points to None

Sentinel nodes hold no data:

• Exist so that every node has a predecessor and a successor
• Insertion and deletion logic is then clean and uniform

---

Insertion

To insert a new node q between node p and p’s successor:

1. Create q, setting q.prev = p and q.next = p.next
2. Update p.next.prev = q
3. Update p.next = q

Deletion

To remove node p:

1. Let predecessor = p.prev and successor = p.next
2. Set predecessor.next = successor
3. Set successor.prev = predecessor
4. Deprecate p by nulling out its links and element

Both of these functions work no matter where in the linked list they are used. This is because of the sentinel nodes removing the need to check for edge cases.

---

Performance

Operation	Time
All standard list ops	O(1)
Space per position	O(1)
Total space for n elements	O(n)
Everything runs in constant time:

• You always know the exact nodes you need to rewire
• No traversal is required

---

CITS2200 - Lecture 15