How to create, traverse, add data to and remove data from these data structures

How to create, traverse, add data to and remove data from the data structures mentioned above. (NB this can be either using arrays and procedural programming or an object-oriented approach)

1.4.2 Data Structures

Practise exam questions

Data Structures — Note 3 of 3

Candidates should have experience of implementing these structures in a variety of contexts, for example through a procedural program, through a different data structure and through an object-oriented approach. Candidates need to be able to read, trace and write code to implement features of these data structures. (Again we would recommend a general understanding backed up with practice implementing them, rather than trying to memorise code patterns).

What you need to know

You need to be able to read, trace and write code that creates and manipulates linked lists, stacks, queues, trees, graphs and hash tables. This can be done procedurally using arrays and pointers, or using an object-oriented approach.

What to know

Stack using an array: a top pointer tracks the last item. Push: check for overflow, increment top, store the item. Pop: check for underflow, read the item at top, decrement top.
Queue using an array: front and rear pointers. Enqueue: check the queue is not full, move rear, store the item. Dequeue: check it is not empty, read the item at front, move front. In a circular queue, pointers wrap using MOD.
Linked list traversal: start at the start pointer and follow each node's next pointer until it is null.
Linked list insertion: find the node before the insertion point, set the new node's pointer to that node's next, then point that node at the new node.
Linked list deletion: make the previous node point to the node after the one being removed; the removed node can be returned to a free list.
Binary search tree insertion: start at the root; go left if the new value is smaller, right if larger, until an empty position is found.
Hash table: apply the hash function to the key to find the index; on a collision, use the agreed method (e.g. check the next free slot).
Graph traversal: depth-first (using a stack or recursion) and breadth-first (using a queue), marking nodes as visited.

Exam technique

Tip:Always check for the edge cases: full and empty structures, and inserting at the start or end of a linked list.
Tip:General understanding is more useful than memorised code; be ready to apply these ideas to an unfamiliar scenario.

Code examples

Stack with an array (OCR pseudocode style)

text

array stack[10]
top = -1

procedure push(item)
    if top == 9 then
        print("Stack overflow")
    else
        top = top + 1
        stack[top] = item
    endif
endprocedure

function pop()
    if top == -1 then
        print("Stack underflow")
        return null
    else
        item = stack[top]
        top = top - 1
        return item
    endif
endfunction

Circular queue in Python

python

SIZE = 5
queue = [None] * SIZE
front, rear, count = 0, -1, 0

def enqueue(item):
    global rear, count
    if count == SIZE:
        print("Queue full")
        return
    rear = (rear + 1) % SIZE      # wrap around
    queue[rear] = item
    count += 1

def dequeue():
    global front, count
    if count == 0:
        print("Queue empty")
        return None
    item = queue[front]
    front = (front + 1) % SIZE    # wrap around
    count -= 1
    return item

Linked list traversal and insertion with an object-oriented approach

python

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

def traverse(start):
    current = start
    while current is not None:
        print(current.data)
        current = current.next

def insert_after(node, data):
    new_node = Node(data)
    new_node.next = node.next     # new node points to the old next
    node.next = new_node          # previous node points to the new node