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

Linked Lists

Overview

A linked list is a dynamic data structure used to store a sequence of elements. Unlike arrays, linked lists do not store elements in contiguous memory locations. Instead, each element, called a node, contains the data and a reference (or pointer) to the next node in the sequence. This structure allows for efficient insertion and deletion operations.

Structure of a Linked List

• Node: Each node contains:
  • Data: The value or information.
  • Pointer: A reference to the next node in the list (or null/.None for the last node).
• Head: A reference to the first node in the list.
• Tail: (Optional) A reference to the last node for easier insertion at the end.

Types of Linked Lists

Singly Linked List:

• Each node points to the next node.
• Traversal is unidirectional (from head to tail).

Doubly Linked List:

• Each node points to both the next and the previous node.
• Allows bidirectional traversal.

Circular Linked List:

• The last node points back to the head, forming a circle.

Operations on Linked Lists

Creating a Linked List

• In a procedural approach (e.g., using arrays), linked lists can be simulated by storing data and pointers as arrays.
• In an object-oriented approach, nodes and lists are implemented as classes.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

Traversing a Linked List

• Start from the head and follow the pointers until reaching the end.
• Algorithm:
  1. Start at the head node.
  2. Print or process the data of the current node.
  3. Move to the next node using the pointer.
  4. Repeat until the next pointer is None.

def traverse(self):
    current = self.head
    while current:
        print(current.data)
        current = current.next

Adding Data to a Linked List

At the Beginning:

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

def add_to_start(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

At the End:

1. Create a new node.
2. Traverse to the last node.
3. Set the last node's next pointer to the new node.

def add_to_end(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node
        return
    current = self.head
    while current.next:
        current = current.next
    current.next = new_node

Removing Data from a Linked List

• From the Beginning: 5. Update the head to point to the next node.
• From the End: 6. Traverse to the second-to-last node. 7. Set its next pointer to None.
• From a Specific Position: 8. Traverse to the node before the target node. 9. Update its next pointer to skip the target node.

def remove(self, key):
    current = self.head
    if current and current.data == key:  # Removing the head node
        self.head = current.next
        current = None
        return

    prev = None
    while current and current.data != key:
        prev = current
        current = current.next

    if current is None:  # Key not found
        return

    prev.next = current.next
    current = None

Practical Applications

• Dynamic Memory Management: Linked lists grow and shrink dynamically, unlike arrays.
• Queue and Stack Implementation: Often implemented using linked lists.
• Efficient Insertion/Deletion: Inserting or deleting elements does not require shifting, unlike arrays.

Note Summary