IB CS Core — Topics 1–5 (SL & HL) · lesson 4 of 4 · 30 min

Singly and doubly linked lists

topic: Topic 5 (HL)

component:

Linked lists

A linked list is a dynamic data structure where each element (node) contains data and a pointer (reference) to the next node. Unlike arrays, linked lists do not require contiguous memory — nodes can be scattered throughout memory.

Singly linked list operations

Each node has two fields: data and next . The list has a head pointer to the first node. The last node’s next is null.

• // Insert at head
• PROCEDURE insertAtHead(list, value)
• newNode ← createNode(value)
• newNode.next ← list.head
• list.head ← newNode
• END PROCEDURE
• // Traverse
• PROCEDURE traverse(list)
• current ← list.head
• WHILE current ≠ null
• DISPLAY(current.data)
• current ← current.next
• END WHILE
• END PROCEDURE

Doubly linked list

Each node has three fields: data , next , and prev . This allows traversal in both directions and O(1) deletion when the node pointer is known. IB HL Paper 1 questions on linked lists often ask you to draw the state of the list after an insertion or deletion, showing the pointer changes. Draw boxes for nodes and arrows for pointers.

Knowledge check

• Question of
• Hide hint
• Show hint

✓ Correct! ✕ Not quite

• Try again
• See results
• Next question
• Check answer

---

Previous lesson: Linear and binary search
Back to IB CS Core — Topics 1–5 (SL & HL)