Linked List (OCR A-Level Computer Science): Revision Notes

Linked List

Overview

A linked list is a dynamic data structure consisting of nodes, where each node stores data and a reference (pointer) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory locations, allowing them to grow or shrink in size dynamically.

Structure of a Linked List

• Node: The fundamental unit of a linked list. Each node contains:
  • Data: The value stored in the node.
  • Pointer: A reference to the next node in the list.
• Head: The first node in the linked list.
• Tail: The last node in the linked list, which points to NULL.

Types of Linked Lists

• Singly Linked List: Each node points to the next node.
• Doubly Linked List: Each node points to both the next and previous nodes.
• Circular Linked List: The last node points back to the first node.

Use Cases for Linked Lists

• Dynamic Memory Allocation: Efficiently manage memory when the size of data structures changes frequently.
• Implementing Stacks and Queues: Provides dynamic size management.
• Efficient Insertions and Deletions: Particularly useful when these operations are frequent, as no shifting of elements is required like in arrays.

Operations on a Linked List

Adding Data (Insertion)

At the Beginning:

1. Create a new node.
2. Point the new node's pointer to the current head.
3. Update the head to the new node.

At the End:

1. Traverse to the last node.
2. Point the last node's pointer to the new node.
3. Set the new node's pointer to NULL.

At a Specific Position:

1. Traverse to the node just before the desired position.
2. Update pointers to insert the new node.

Pseudocode for Insertion at the Beginning:

METHOD InsertAtBeginning(value)
    NEW_NODE ← Node(value)
    NEW_NODE.next ← head
    head ← NEW_NODE

Pseudocode for Insertion at the End:

METHOD InsertAtEnd(value)
    NEW_NODE ← Node(value)
    IF head IS NULL
        head ← NEW_NODE
    ELSE
        current ← head
        WHILE current.next IS NOT NULL
            current ← current.next
        ENDWHILE
        current.next ← NEW_NODE

Removing Data (Deletion)

From the Beginning:

1. Update the head to point to the next node.
2. Delete the original head node.

From the End:

1. Traverse to the second-to-last node.
2. Set its pointer to NULL.
3. Delete the last node.

From a Specific Position:

1. Traverse to the node just before the one to be removed.
2. Update its pointer to skip the removed node.
3. Delete the node.

Pseudocode for Deletion from the Beginning:

METHOD RemoveFromBeginning()
    IF head IS NOT NULL
        head ← head.next

Pseudocode for Deletion from the End:

METHOD RemoveFromEnd()
    IF head IS NULL
        RETURN
    ELSE IF head.next IS NULL
        head ← NULL
    ELSE
        current ← head
        WHILE current.next.next IS NOT NULL
            current ← current.next
        ENDWHILE
        current.next ← NULL

Searching for Data

• Traverse the linked list, comparing each node's data with the target value.
• Return the node if found; otherwise, indicate that the value is not present.

Pseudocode for Search:

METHOD Search(value)
    current ← head
    WHILE current IS NOT NULL
        IF current.data = value
            RETURN current
        current ← current.next
    ENDWHILE
    RETURN "Not Found"

Note Summary