Skip to content

Linked Lists

1.4.2 Data structures · Paper 1 · 2 flashcards · 3 questions

Definition
A linked list is a linear data structure where elements (nodes) are stored in separate memory locations and connected by pointers.
Key Point
Linked List Characteristics:
• Each node contains data and a pointer to the next node
• Dynamic size - can grow and shrink
• Non-contiguous memory
• Sequential access only (no random access)
• Efficient insertion/deletion at any position

Singly Linked List

Worked Example
Worked Example: Linked List Node Structure
pseudocode 
// Node structure
record Node:
    string data
    Node next        // Pointer to next node
end record

// Creating nodes
node1 = new Node()
node1.data = "Alice"

node2 = new Node()
node2.data = "Bob"

node3 = new Node()
node3.data = "Charlie"

// Linking nodes
node1.next = node2
node2.next = node3
node3.next = null        // Last node points to null

// Traverse the list
current = node1
while current != null:
    print(current.data)
    current = current.next
end while
// Output: Alice, Bob, Charlie

Linked List Operations

Worked Example
Adding a Node to the Front:
pseudocode 
procedure addToFront(head, newData):
    newNode = new Node()
    newNode.data = newData
    newNode.next = head      // New node points to old head
    return newNode           // New node becomes new head
end procedure

// Usage
head = null
head = addToFront(head, "Zoe")     // List: ["Zoe"]
head = addToFront(head, "Yara")    // List: ["Yara", "Zoe"]
Worked Example
Adding a Node to the End:
pseudocode 
procedure addToEnd(head, newData):
    newNode = new Node()
    newNode.data = newData
    newNode.next = null
    
    if head == null then
        return newNode       // New node becomes head
    end if
    
    // Traverse to end
    current = head
    while current.next != null:
        current = current.next
    end while
    
    current.next = newNode   // Link last node to new node
    return head
end procedure
Worked Example
Deleting a Node:
pseudocode 
procedure deleteNode(head, targetData):
    if head == null then
        return null
    end if
    
    // If head node holds the target
    if head.data == targetData then
        return head.next     // New head is next node
    end if
    
    // Search for the node
    current = head
    while current.next != null:
        if current.next.data == targetData then
            current.next = current.next.next  // Skip the node
            return head
        end if
        current = current.next
    end while
    
    return head              // Target not found
end procedure

Linked List vs Array

Key Point
Memory
• Array: Contiguous
• Linked List: Non-contiguous

Size
• Array: Fixed
• Linked List: Dynamic

Access
• Array: Random O(1)
• Linked List: Sequential O(n)

Insert at front
• Array: O(n) - shift elements
• Linked List: O(1)

Insert at end
• Array: O(1) amortized
• Linked List: O(n) unless tracking tail

Delete
• Array: O(n) - shift elements
• Linked List: O(1) if pointer known

Memory overhead
• Array: None
• Linked List: Extra pointer per node