ADT Linked List

A linked list stores a sequence of items where each item, called a node, holds two things: the data and a pointer (a reference) to the next node. A separate head (or start) pointer marks the first node, and the final node's pointer is the null pointer, signalling the end.

Unlike an array, the nodes are not stored in one contiguous block. To insert or delete you simply change a couple of pointers — no shuffling of data. That makes a linked list ideal when the collection grows and shrinks a lot, such as the waiting list at a coaching centre.

class Node:
    def __init__(self, data):
        self.data = data       # value stored
        self.next = None       # link to next node

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

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:        # walk to the last node
                current = current.next
            current.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def search(self, key):
        current = self.head
        while current:
            if current.data == key:
                return True
            current = current.next
        return False

    def delete(self, key):
        current = self.head
        previous = None
        while current and current.data != key:
            previous = current
            current = current.next
        if current is None:
            return "Node not found"
        if previous is None:          # deleting the head
            self.head = current.next
        else:
            previous.next = current.next   # bypass the node

# after append(10), append(20), append(30)
# 10 -> 20 -> 30 -> None
# search(20) -> True   search(40) -> False
# after delete(20)
# 10 -> 30 -> None

Because exam languages may not have objects, a linked list is simulated with parallel arrays. The index of a node is its “address”. StartPointer holds the index of the first node; each NextPointer holds the index of the following node; the null pointer is a special value (this page uses -1; some papers use 0). Unused indices form the free list, headed by FreePointer.

StartPointer = 1, FreePointer = 3. List order: Adri(1) → Mohar(2) → Mehrin(0) → Ø. Free list: 3 → 4 → Ø. Null pointer = -1. Follow StartPointer=1: index 1 → 2 → 0 → -1 (end).

FUNCTION SearchList(Item) RETURNS INTEGER
    NullPtr <- -1
    NowPtr  <- StartPointer
    WHILE NowPtr <> NullPtr
        IF LinkList[NowPtr].Data = Item THEN
            RETURN NowPtr          // found: return its index
        ELSE
            NowPtr <- LinkList[NowPtr].NextPtr   // advance
        ENDIF
    ENDWHILE
    RETURN NullPtr                // not found
ENDFUNCTION

Insert (take a node from the free list):

To insert, you grab the first free node (at FreePointer), advance the free pointer, write the data, then re-link so the new node sits in the right place. Two pointer changes: the previous node points to the new node, and the new node points to what came next. No data is moved.

PROCEDURE InsertAfter(PrevPtr, NewData)
    IF FreePointer = -1 THEN
        OUTPUT "No free space"
    ELSE
        NewPtr <- FreePointer                       // take a free node
        FreePointer <- LinkList[FreePointer].NextPtr // advance free list
        LinkList[NewPtr].Data <- NewData
        LinkList[NewPtr].NextPtr <- LinkList[PrevPtr].NextPtr
        LinkList[PrevPtr].NextPtr <- NewPtr         // re-link
    ENDIF
ENDPROCEDURE

Delete (return the node to the free list):

Delete by pointing the previous node past the deleted one. The freed node is then linked back into the free list.

Fifteen exam-style tasks. Click Hint for bullet-point guidance, then Help to reveal a worked Python/pseudocode solution.