QUESTION 08

Explain singly linked-list representation, creation and traversal.

5 marks

Answer in brief

A singly linked list connects nodes in one forward direction.

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

Set current to head.
While current is not NULL, process current->data.
Move current to current->next.
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

CodeBhavya illustration of nodes — Explain singly linked-list representation, creation and traversal. · Download diagram

Complete C example

main.c

Download 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;
}

Sample input and output

The example uses values in the code.

Output

10 20 30
10 30