Example: stack

A stack interface can provide push, pop, peek and is_empty. Its rule is last-in, first-out. A client should obtain the most recently pushed remaining value from pop, regardless of whether the stack uses an array or linked nodes.

Interface contract

1. State the supported values and operations.
2. Specify success and failure results, such as empty-stack removal.
3. State which operation changes the collection.
4. Hide representation details that the caller does not need.

Implementation

An array stack can keep an element array and a top index. A linked stack can keep a head pointer and allocate nodes. Both can satisfy the same abstract rule, but have different capacity, allocation and locality properties. An ADT is not just a C struct declaration: behaviour is part of the definition.

Benefits

The client can use operations without rewriting representation logic. Testing can verify observable behaviour. An implementation can be replaced while keeping a compatible contract. In C, headers and carefully designed functions support this separation, although C does not automatically enforce every abstraction boundary.

Complexity

An ADT description should not be confused with an unconditional performance promise. The chosen implementation determines operation costs. Document those costs separately; for example, the array and linked stack versions shown later provide O(1) push/pop excluding allocator internals.

Questions to ask

1. Is random indexed access needed?
2. Are insertions mainly at an end or in the middle?
3. Must values remain ordered?
4. Is the maximum size known?
5. Are memory usage and allocation failures important?

Examples

A fixed table of marks suits an array because indexed access is direct. A changing sequence with frequent head insertion can suit a linked list. A reverse-order undo history suggests a stack, while arrival-order work suggests a queue. Relationships between cities suggest a graph.

Trade-offs

Arrays have contiguous storage and efficient indexed access, but a middle insertion can require shifting. Linked nodes can be relinked efficiently when the relevant location is known, but finding that location may require traversal and each node carries link storage.

Time and space

Compare whole workloads, not one isolated best-case operation. An operation that first searches n nodes and then relinks one link still has O(n) total search-and-update work. Include input storage, output storage and auxiliary storage deliberately rather than mixing those categories.

Design process

State the expected workload, choose a simple correct representation, define an interface, then test boundary cases. A more complicated structure can add maintenance cost without helping a small task. The selected structure must also represent the required logical relationships accurately.

Operations

1. Create an empty list.
2. Insert a value at a permitted position.
3. Delete an element or selected occurrence.
4. Retrieve, search or update a value.
5. Traverse all elements and obtain the current size when needed.

Logical versus physical order

In an array list, consecutive logical positions normally occupy consecutive element positions. In a linked list, explicit links describe the sequence even when nodes are physically separate. Neither representation requires the values themselves to be sorted.

Example

The list 10, 30, 20 has a first value 10 and last value 20. Inserting 15 after the first value produces 10, 15, 30, 20. Deleting 30 produces 10, 15, 20. The operation contract should specify whether positions are zero-based and whether duplicate values are allowed.

Boundary cases

An empty list has no first element to read or remove. Insertion can create its first element. Deleting the only element must restore a valid empty representation. Reject invalid positions rather than writing outside storage or following a missing link.

Complexity

The logical list does not prescribe one performance table. Arrays support O(1) indexed retrieval but may shift O(n) elements on insertion. Singly linked lists require O(n) indexed traversal, while head insertion uses O(1) link work. Choose and document the implementation.

Node

struct Node { int data; struct Node *next; };

Creation

Start head as NULL. Allocate a node, check success, assign its data and link it into the sequence. The complete example uses a tail pointer while building a known demonstration list so that each append needs only fixed link work. If allocation fails, release already owned nodes.

Traversal

1. Set current to head.
2. While current is not NULL, process current->data.
3. Move current to current->next.
4. Stop at NULL without dereferencing it.

Example

For 10 → 20 → 30 → NULL, traversal displays 10, 20 and 30. No assumption is made about the numerical memory addresses or physical adjacency of the nodes. An empty head makes the traversal body execute zero times.

Cleanup

Before freeing a node during traversal, save its next link in a separate pointer. Once freed, the old node must not be accessed to obtain the next value. After destroying the list, restore the owner’s head and tail to a valid empty state.

Complexity

Visiting n nodes takes O(n) time and a fixed current pointer gives O(1) auxiliary traversal space. The nodes occupy O(n) storage. Building by a maintained tail is O(n) link work, whereas repeatedly scanning from head to append can make construction O(n²), excluding allocator costs.

Diagram or flowchart

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
void destroy(struct Node *head)
{
    while (head != NULL) { struct Node *next = head->next; free(head); head = next; }
}
int append(struct Node **head, struct Node **tail, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = NULL;
    if (*tail != NULL) { (*tail)->next = node; } else { *head = node; }
    *tail = node;
    return 1;
}
void display(const struct Node *head)
{
    const struct Node *p = head;
    while (p != NULL) { printf("%d%s", p->data, p->next == NULL ? "\n" : " "); p = p->next; }
    if (head == NULL) { puts("Empty"); }
}
int delete_first(struct Node **head, struct Node **tail, int value)
{
    struct Node *current = *head, *previous = NULL;
    while (current != NULL && current->data != value) { previous = current; current = current->next; }
    if (current == NULL) { return 0; }
    if (previous != NULL) { previous->next = current->next; } else { *head = current->next; }
    if (*tail == current) { *tail = previous; }
    free(current);
    return 1;
}

int main(void)
{
    struct Node *head = NULL, *tail = NULL;
    for (int value = 10; value <= 30; value += 10) {
        if (!append(&head, &tail, value)) { destroy(head); puts("Allocation failed"); return 1; }
    }
    display(head);
    delete_first(&head, &tail, 20);
    display(head);
    destroy(head);
    head = tail = NULL;
    return 0;
}

10 20 30
10 30

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• February 2024 · Q1(a) · 1 marks

  Define a singly linked list.

  Paper DS03 · page 1
• March 2021 · Q1(a) · 7 marks

  Discuss singly linked lists.

  Paper DS04 · page 1
• March 2022 · Q1(a) · 8 marks

  Define a singly linked list and show its node structure and sketch.

  Paper DS05 · page 1

View all matching source questions →

Insert at beginning

1. Allocate and initialise new_node.
2. Set new_node->next = head.
3. Set head = new_node.

Insert at end

Set the new node’s next to NULL. If the list is empty, set head to it. Otherwise follow links to the final node and set its next to the new node. A maintained tail avoids that search. Do not lose the old head while traversing.

Delete the first matching value

1. Track current and previous while searching.
2. If no node matches, report failure without changing the list.
3. For a head match, set head to current->next.
4. Otherwise set previous->next to current->next.
5. Free current and stop using it.

Example

Deleting 20 from 10 → 20 → 30 links the 10 node directly to the 30 node before freeing the 20 node. Deleting 10 instead changes head. Deleting the sole node leaves head equal to NULL.

Complexity

Head insertion is O(1) link work. End insertion without a tail and value-based deletion can each need O(n) search. Once the relevant predecessor is already known, unlinking is O(1). Node storage grows with the list; the fixed search pointers add O(1) auxiliary space. The demonstration program includes creation, append, delete, traversal and cleanup.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
void destroy(struct Node *head)
{
    while (head != NULL) { struct Node *next = head->next; free(head); head = next; }
}
int append(struct Node **head, struct Node **tail, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = NULL;
    if (*tail != NULL) { (*tail)->next = node; } else { *head = node; }
    *tail = node;
    return 1;
}
void display(const struct Node *head)
{
    const struct Node *p = head;
    while (p != NULL) { printf("%d%s", p->data, p->next == NULL ? "\n" : " "); p = p->next; }
    if (head == NULL) { puts("Empty"); }
}
int delete_first(struct Node **head, struct Node **tail, int value)
{
    struct Node *current = *head, *previous = NULL;
    while (current != NULL && current->data != value) { previous = current; current = current->next; }
    if (current == NULL) { return 0; }
    if (previous != NULL) { previous->next = current->next; } else { *head = current->next; }
    if (*tail == current) { *tail = previous; }
    free(current);
    return 1;
}

int main(void)
{
    struct Node *head = NULL, *tail = NULL;
    for (int value = 10; value <= 30; value += 10) {
        if (!append(&head, &tail, value)) { destroy(head); puts("Allocation failed"); return 1; }
    }
    display(head);
    delete_first(&head, &tail, 20);
    display(head);
    destroy(head);
    head = tail = NULL;
    return 0;
}

10 20 30
10 30

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• February 2024 · Q2(a) · 5 marks

  Give singly linked-list insertion and deletion algorithms.

  Paper DS03 · page 1
• October 2020 · Q1(a) · 7 marks

  Give insertion and deletion algorithms for a singly linked list.

  Paper DS06 · page 1
• September 2021 · Q6(a) · 7 marks

  Give an algorithm to insert a node at the last position of a linear linked list.

  Paper DS07 · page 1

View all matching source questions →

Algorithm

1. Set current = head and previous = NULL. Keep last_match and last_previous as NULL.
2. Visit each node. When its key matches, save current and previous as the latest match.
3. Advance previous and current until the scan ends.
4. If no match was saved, report Not found.
5. Bypass the saved node using its saved predecessor, or update head when it was the head. Free the saved node.

Example

For IDs 7, 2, 7, 3 and key 7, the first saved match is the head. At the third node, the saved pair is replaced. After scanning the whole list, bypass the third node. The result is 7, 2, 3, preserving the earlier occurrence.

Boundary cases

An empty list and an absent key produce no deletion. A single matching node is removed and head becomes NULL. If the last occurrence is also the last node, its predecessor’s next becomes NULL. A representation with a tail pointer must update that tail too.

Interpretation

The paper uses a student scenario without a full record schema. The algorithm treats the student identifier as the key; it does not decide attendance policy or infer a person’s identity from a name.

Complexity

Every node must be examined to establish that a match is the last, giving O(n) time. A fixed number of remembered pointers gives O(1) auxiliary space.

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
void destroy(struct Node *head)
{
    while (head != NULL) { struct Node *next = head->next; free(head); head = next; }
}
int append(struct Node **head, struct Node **tail, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = NULL;
    if (*tail != NULL) { (*tail)->next = node; } else { *head = node; }
    *tail = node;
    return 1;
}
void display(const struct Node *head)
{
    const struct Node *p = head;
    while (p != NULL) { printf("%d%s", p->data, p->next == NULL ? "\n" : " "); p = p->next; }
    if (head == NULL) { puts("Empty"); }
}
int delete_last(struct Node **head, struct Node **tail, int key)
{
    struct Node *current = *head, *previous = NULL, *last = NULL, *last_previous = NULL;
    while (current != NULL) {
        if (current->data == key) { last = current; last_previous = previous; }
        previous = current; current = current->next;
    }
    if (last == NULL) { return 0; }
    if (last_previous != NULL) { last_previous->next = last->next; } else { *head = last->next; }
    if (*tail == last) { *tail = last_previous; }
    free(last); return 1;
}

int main(void)
{
    struct Node *head = NULL, *tail = NULL;
    int data[4] = {7, 2, 7, 3};
    for (int i = 0; i < 4; ++i) {
        if (!append(&head, &tail, data[i])) { destroy(head); puts("Allocation failed"); return 1; }
    }
    delete_last(&head, &tail, 7); display(head); destroy(head);
    return 0;
}

7 2 3

Related exam questions

The following are topic matches from the supplied papers. Marks are their printed allocations, separate from the practice answer badge.

• August/September 2022 · Q2(a) · 8 marks

  Write a function to delete the last occurrence of a student from a list.

  Paper DS02 · page 1

View all matching source questions →

Tail representation

With a non-empty tail pointer, the first node is tail->next. The only node in a one-node list points to itself. This representation gives convenient access to both the tail and the beginning without walking through the list.

Insertion

1. For an empty list, make the new node link to itself and set tail to it.
2. For a non-empty list, link new->next to tail->next and tail->next to new.
3. For an append, also set tail = new; for a head insertion keep the old tail.

Traversal

For a non-empty list, save start = tail->next. Process nodes and move forward until the pointer returns to start. A do-while form expresses the first valid visit. Testing only for NULL would not stop a normal circular traversal.

Deletion

Handle an empty list separately. When removing the only node, free it and set tail = NULL. Otherwise bypass the target through its predecessor and update tail if the target was the tail. The resulting final link must still reach the current first node.

Uses and complexity

Circular lists suit round-robin scheduling and repeated cycling through participants. Head insertion or tail append with this representation needs O(1) link work; a value search can require O(n). Traversal visits each node once and uses O(1) auxiliary pointers. A broken termination rule can loop indefinitely.

Diagram or flowchart

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int append(struct Node **tail, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value;
    if (*tail == NULL) { node->next = node; }
    else { node->next = (*tail)->next; (*tail)->next = node; }
    *tail = node; return 1;
}
int remove_front(struct Node **tail, int *out)
{
    if (*tail == NULL) { return 0; }
    struct Node *first = (*tail)->next; *out = first->data;
    if (first == *tail) { *tail = NULL; }
    else { (*tail)->next = first->next; }
    free(first); return 1;
}
void display(const struct Node *tail)
{
    if (tail == NULL) { puts("Empty"); return; }
    const struct Node *first = tail->next, *p = first;
    do { printf("%d%s", p->data, p->next == first ? "\n" : " "); p = p->next; } while (p != first);
}

int main(void)
{
    struct Node *tail = NULL; int value;
    for (int i = 10; i <= 30; i += 10) {
        if (!append(&tail, i)) {
            while (remove_front(&tail, &value)) { }
            puts("Allocation failed"); return 1;
        }
    }
    display(tail); remove_front(&tail, &value); display(tail);
    while (remove_front(&tail, &value)) { }
    return 0;
}

10 20 30
20 30

Node form

struct DNode {
    int data;
    struct DNode *previous, *next;
};

Insert between neighbours

For a new node between left and right, set new->previous = left and new->next = right. If left exists, set left->next = new; otherwise update head. If right exists, set right->previous = new; otherwise update tail. Both directions must describe the same sequence.

Delete a known node

Link its predecessor’s next to its successor when a predecessor exists, otherwise update head. Link its successor’s previous to its predecessor when a successor exists, otherwise update tail. Only after reconnecting both sides should the removed owned node be freed.

Traversal

Starting from head and following next displays forward order. Starting from tail and following previous displays reverse order. Do not dereference missing boundary neighbours; head->previous and tail->next are normally NULL in this non-circular form.

Complexity and trade-off

Deleting a known node uses O(1) link work because its predecessor is directly available. Searching by key still takes O(n). Nodes require an extra pointer compared with a singly linked representation, and each update must maintain more links. A single-node deletion sets both head and tail to NULL.

Diagram or flowchart

Complete C example

main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *previous, *next; };
struct List { struct Node *head, *tail; };
int append(struct List *list, int value)
{
    struct Node *node = malloc(sizeof *node);
    if (node == NULL) { return 0; }
    node->data = value; node->next = NULL; node->previous = list->tail;
    if (list->tail != NULL) { list->tail->next = node; } else { list->head = node; }
    list->tail = node; return 1;
}
void remove_node(struct List *list, struct Node *node)
{
    if (node == NULL) { return; }
    if (node->previous != NULL) { node->previous->next = node->next; } else { list->head = node->next; }
    if (node->next != NULL) { node->next->previous = node->previous; } else { list->tail = node->previous; }
    free(node);
}
void destroy(struct List *list)
{
    while (list->head != NULL) { remove_node(list, list->head); }
}

int main(void)
{
    struct List list = {NULL, NULL};
    for (int i = 10; i <= 30; i += 10) {
        if (!append(&list, i)) { destroy(&list); puts("Allocation failed"); return 1; }
    }
    remove_node(&list, list.head->next);
    for (struct Node *p = list.head; p != NULL; p = p->next) { printf("%d%s", p->data, p->next == NULL ? "\n" : " "); }
    for (struct Node *p = list.tail; p != NULL; p = p->previous) { printf("%d%s", p->data, p->previous == NULL ? "\n" : " "); }
    destroy(&list);
    return 0;
}

10 30
30 10

Array list

Contiguous elements permit direct indexed access and good locality. Fixed-capacity arrays need an overflow policy, while a dynamic array needs allocation management. Inserting or deleting in the middle can shift O(n) elements.

Singly linked list

Each node has a next link. Head insertion needs O(1) link work, but finding an arbitrary position or predecessor may take O(n). Nodes can be allocated separately as the list grows, with allocation failures handled.

Circular singly linked list

The last link returns to the first. A tail-based representation supports constant link work at the beginning and end and suits cycling tasks. Traversal must stop when it returns to its start, not when it sees NULL.

Doubly linked list

Each node has previous and next links. A known node can be removed using its neighbours without a predecessor search. More memory and more careful link updates are required. Searching by value remains linear.

Choosing and counting

Include the cost of locating a position before claiming an update is constant time. All n-element representations need O(n) data storage; linked representations add per-node links and allocator overhead. A maintained tail helps append but does not create random access. Choose the simplest representation meeting the required workload.

Reference table

Search algorithm

1. Set current = head.
2. While current exists, compare its data with key.
3. Return the matching node or a success result when equal.
4. Otherwise advance to next; report failure after reaching NULL.

Counting

Start count at zero. Increment it for every visited node. The empty list produces zero. If size is stored in the list descriptor instead, update it consistently on every successful insertion and deletion; a stale cached count is not useful.

Example

For 10 → 20 → 30, a search for 20 makes two comparisons. A search for 99 visits all three nodes before reporting failure. Returning a node pointer does not transfer ownership automatically; its validity ends if the node is later removed or the list is destroyed.

Complexity

A first-node match is O(1). The worst case is O(n), including a missing key. Counting without a cached size also takes O(n). A fixed current pointer and counter use O(1) auxiliary space.

Order and access

Sorted list values can allow a forward scan to stop early once it passes the key, but ordinary linked nodes still do not provide constant-time middle access. The array binary-search algorithm cannot simply assume it can jump to any linked-list midpoint in O(1).