Singly linked lists: nodes, links and traversal

From array position to linked order

An array scan visits positions 0, 1, 2 and so on. A singly linked list follows a different rule: begin at the head, process that node, and follow its next link. The next node need not occupy the next array position. This lesson teaches how to represent and trace that order, recognize the end and handle an empty list safely.

Prerequisites: initialized integer arrays, valid indices, if, while, functions, return values and the array-parameter convention. The previous recursion module taught separate calls and their returns; this lesson deliberately uses an iterative traversal. The recursion call stack and the data stored in a linked list are different concepts. You do not need recursion to walk this list.

We use a bounded array of node records, with integer indices as links. This is a real linked representation inside an array, not a claim that all linked lists use arrays. Pointer-based nodes and dynamic allocation with malloc/free, deletion and slot reuse, doubly linked lists, trees and formal complexity proofs belong to later lessons. No allocation or deallocation occurs here.

New C syntax before the program

A struct groups named fields into one record. typedef struct { int value; int next; } Node; gives that record type the short name Node. One Node has a data field called value and a link field called next. The dot selects a field: nodes[2].next means “the next field of the node at index 2.” The record's fields have different jobs even though both are integers.

Node nodes[4] creates four records in one fixed-size array. An initializer {10, 1} assigns 10 to value and 1 to next, in the declaration order. enum { CAP = 4, END = -1 }; defines two integer constants. CAP is the storage capacity; END is a link meaning “there is no next node.” END is never an array index to read. A stored data value may legitimately be -1; only the link or head field uses -1 as its sentinel.

A parameter const Node nodes[] lets a function read these same records without modifying their fields through that parameter. As with earlier array parameters, it is adjusted to a pointer parameter; it does not copy the whole array or discover its capacity. Callers must supply a live, initialized array with exactly CAP records. We use no pointer arithmetic, heap allocation or explicit pointer links. C still implements this array parameter using a pointer.

ReadResult is another record, containing ok and value. A function can return a record by value. An ok of 1 means its value is a successful read; an ok of 0 means there was no successful read and the caller must ignore value. This avoids treating a legitimate data value such as 0 or -1 as an error code. !x means “x is zero”; || means logical OR and && means logical AND, with left-to-right short-circuiting. Thus an invalid list or empty head prevents a front-node read.

Representation contract

For this small model:

• The actual array has CAP = 4 initialized records. used is between 0 and 4.
• Active records occupy indices 0 through used - 1; unused slots are not list members. The active nodes may be linked in any permutation of these indices.
• head is END for an empty list. Otherwise it is the index of the first active node.
• Each active node's next is either another active node index or END. Starting from head must visit all used active nodes exactly once and then reach END.
• There are no cycles or unreachable active nodes in a valid representation. Some other list implementations allow unrelated allocated records; this teaching model specifically does not count those records in used.

Capacity, member count, index and stored value are separate quantities. A list with three members may start at index 2. A node containing 30 does not imply a link to index 30. A record remaining in unused storage does not become a member merely because its fields contain numbers.

Worked trace: physical order versus logical order

The initialized active records are:

With head = 2 and used = 3, the logical chain is 2 -> 0 -> 1 -> END. Hence the data order is 20, 10, 30, not 10, 30, 20. The arrows are values in the link fields; they are not increments of the current index.

We keep head unchanged and move a separate variable named current. Assigning current = current + 1 would be an array scan, not a traversal of these links. Trying to read nodes[END] would use index -1 and is invalid C; the loop must stop before that read.

Complete bounded C11 example

Predict the first output line before running. This program validates the representation, reads the first value, inserts one node at the front and traverses again. Every read is made only after the required guard.

#include <stdio.h>

enum { CAP = 4, END = -1 };

typedef struct {
    int value;
    int next;
} Node;

typedef struct {
    int ok;
    int value;
} ReadResult;

int valid_list(const Node nodes[], int used, int head) {
    if (used < 0 || used > CAP) {
        return 0;
    }
    int current = head;
    int count = 0;
    while (current != END) {
        if (current < 0 || current >= used || count == used) {
            return 0;
        }
        current = nodes[current].next;
        count = count + 1;
    }
    return count == used;
}

int print_list(const Node nodes[], int used, int head) {
    if (!valid_list(nodes, used, head)) {
        return 0;
    }
    int current = head;
    while (current != END) {
        printf("%d ", nodes[current].value);
        current = nodes[current].next;
    }
    printf("END\n");
    return 1;
}

ReadResult read_front(const Node nodes[], int used, int head) {
    ReadResult result = {0, 0};
    if (!valid_list(nodes, used, head) || head == END) {
        return result;
    }
    result.ok = 1;
    result.value = nodes[head].value;
    return result;
}

int main(void) {
    Node nodes[CAP] = {{10, 1}, {30, END}, {20, 0}, {0, END}};
    int used = 3;
    int head = 2;
    if (!print_list(nodes, used, head)) {
        return 1;
    }
    ReadResult first = read_front(nodes, used, head);
    if (first.ok) {
        printf("front: %d\n", first.value);
    }
    if (valid_list(nodes, used, head) && used < CAP) {
        int fresh = used;
        nodes[fresh].value = 7;
        nodes[fresh].next = head;
        head = fresh;
        used = used + 1;
    }
    if (!print_list(nodes, used, head)) {
        return 1;
    }
    return 0;
}

The exact output is:

20 10 30 END
front: 20
7 20 10 30 END

Why the validator terminates safely

valid_list first rejects a used outside 0 through CAP. It then follows links while counting visited nodes. Before every array read it checks that current is in [0, used) and that fewer than used steps have already been taken. A malformed negative link other than END, an oversized link or a cycle therefore produces failure before an unsafe read or an unbounded loop. In a deterministic next-link chain, revisiting a node traps traversal in a cycle; it cannot later exit through a different next link. Allowing at most used reads detects such a cycle.

Reaching END is necessary but not sufficient here: count == used also ensures all active nodes were reached. For used = 3, a chain containing only index 0 and then END fails this model's completeness rule. The validator is defensive about fields and links; it cannot verify that a caller actually supplied CAP live initialized records. That remains the caller's storage promise.

The printing function validates first, so it emits no partial list on invalid input. The front reader validates first too; an empty or invalid list returns {0, 0}. A valid front value of 0 returns {1, 0}. Check ok, not the numerical value. The two zero values in a failed result are an initialized representation, not a successful zero-valued node.

Inserting at the front: save the old chain before replacing head

The insertion shown in main uses the next unused slot, index 3. It runs only if the old representation is valid and used < CAP.

1. fresh = used gives 3; no active node is overwritten.
2. nodes[3].value = 7 stores the payload.
3. nodes[3].next = head stores the old head, 2.
4. head = 3 makes the new node first.
5. used becomes 4, so the new chain uses all four active slots.

The new link chain is 3 -> 2 -> 0 -> 1 -> END. The old records do not shift physically. If head were changed to fresh before assigning nodes[fresh].next = head, the new node would point to itself and lose access to the old chain from the head. The order of the two assignments matters.

At used == CAP, the guard skips every insertion statement; head, used and all records remain unchanged. There is no valid slot nodes[CAP]. Starting from used = 0, head = END with an initialized CAP-record array, the same insertion block creates index 0 with next = END: a correct one-node list. This lesson never deletes a node, so the next unused index is always used; do not extend that policy to deletion and reuse without designing a free-slot rule.

A precise analogy

Imagine four numbered lockers. A locker holds a message and the number of the next locker to visit. A separate start card names the first locker. “END” means finish without opening another locker. The locker number is an address within our small model, while the message is data; the message itself does not tell you where to go. You can change the visiting order by changing cards without moving lockers.

This analogy explains link order and head. It does not grant permission to follow an invalid number, model arbitrary computer memory or guarantee that following cards will stop. A cycle of cards needs rejection just as a cycle of links does.

Key box

• A node combines data and one outgoing next link; “singly” means one next link per node in this model.
• Head identifies the first node; END marks no node, including an empty head.
• Follow nodes[current].next; do not assume index adjacency.
• Keep the stored head and the traversal cursor separate.
• Guard before indexing. Empty, full and malformed states need distinct treatment.
• Inserting at the front preserves the old head in the new next field before changing head.
• Array-index links are a bounded teaching representation. They are not native C pointers.

Try it first, then check

1. Keep the three initial records but make the data in index 0 equal to -1. Does traversal stop there? No. The values become 20, -1, 30; links remain 2, 0, 1, END. The sentinel applies to links, not payloads.
2. Start with an empty initialized array, insert 8 and then 5 using the shown block twice. The links become 1 -> 0 -> END, and values are 5, 8. used is 2 and head is 1.
3. In the initial list, change node 1's next from END to 2. Validation rejects the resulting cycle: after three reads current is 2 and count is used. No fourth array read is performed.

Six original practice questions

Choose exactly one of the four options. These are original foundation exercises, not previous-year questions or a full GATE mock. All questions use the bounded representation and C definitions above; any change to a link is hypothetical unless explicitly stated.

Question 1

For the initial three records and head = 2, which data sequence does traversal print before END?

A. 10, 30, 20 B. 20, 10, 30 C. 2, 0, 1 D. 20, 30, 10

Question 2

An initialized CAP-record array has used = 0 and head = END. What does read_front return?

A. {1, 0}, because empty means a stored zero B. It reads nodes[-1] and returns its value C. {0, 0}, with no node-data read D. {1, -1}, because END is the first data value

Question 3

The original list has head = 2 and used = 3. Which order correctly prepends value 7 in fresh slot 3? Assume nodes[3].value = 7 has been set.

A. head = 3; nodes[3].next = head; used = 4; B. nodes[3].next = head; head = 3; used = 4; C. nodes[3].next = END; head = 3; used = 4; D. nodes[2].next = 3; head = 3; used = 4;

Question 4

A valid list has used = CAP = 4. What does the guarded insertion block in main do?

A. Overwrites nodes[3] B. Writes nodes[4] and increases used C. Resets head to END D. Skips insertion and preserves the entire state

Question 5

In the initial list only nodes[1].next changes from END to 2. What does valid_list return, and why?

A. 0: the chain repeats, and the step guard rejects it before a fourth link read B. 1: every individual index is within range C. 1: visiting three nodes once is enough even without reaching END D. It must recurse forever

Question 6

Which statement about a valid front node whose value is -1 is correct?

A. It is necessarily an empty list B. read_front returns ok = 0 because -1 always signals failure C. read_front returns ok = 1 and value = -1; the next field separately controls traversal D. Its next must also be -1

Worked answers

1. B

A is incorrect: this is physical array order, not linked order.

B is correct: indices 2, 0, 1 contain values 20, 10, 30.

C is incorrect: these are the visited indices, not their data.

D is incorrect: node 2 links to index 0, whose value is 10, not directly to index 1.

2. C

A is incorrect: an empty list has no successful front read, so ok is 0.

B is incorrect: validation and the head guard return before indexing with END.

C is correct: validation accepts the empty representation; the head guard returns the initialized failure result.

D is incorrect: END is a head/link marker, not an existing data node.

3. B

A is incorrect: after head becomes 3, assigning next = head creates a self-cycle at 3.

B is correct: it saves old head 2 in next before making 3 the new head. The chain is 3, 2, 0, 1, END.

C is incorrect: the new head immediately ends the chain; the three old active nodes become unreachable.

D is incorrect: it changes the old head link and never links the new node to the old head. With the initial unused next = END, only node 3 is reachable.

4. D

A is incorrect: no insertion assignment executes because used < CAP is false.

B is incorrect: nodes[4] is outside the four-slot array; the guard prevents this write.

C is incorrect: there is no reset assignment on failure.

D is correct: capacity is exhausted, so head, used and every record remain unchanged.

5. A

A is correct: reads at indices 2, 0, 1 leave current = 2 and count = used = 3; the next iteration returns 0 before a read.

B is incorrect: valid index ranges alone do not exclude a cycle.

C is incorrect: a valid chain must also terminate at END after reaching every active node.

D is incorrect: the validator is iterative and explicitly bounds its number of link reads.

6. C

A is incorrect: emptiness is represented by head == END, not by a stored payload.

B is incorrect: read_front uses a separate ok field; every int payload is permitted.

C is correct: a successful read can return -1 as data. Only head and next interpret END as no node.

D is incorrect: data and link are independent fields; the node may have a following node.

Scope and next step

You can now distinguish stored data, node indices and links, trace a bounded singly linked list and prepend safely. Next, study the LIFO rule of a stack and the FIFO rule of a queue. These three lessons are an introductory bridge, not complete data-structures or GATE CS coverage. They do not change an existing course’s examination year. Hindi is a teaching aid, not a claim about an official Hindi GATE paper.