Traversal Forward and Backward in DSA C

Mental Model

Traversal means visiting each item in a list one by one, either from start to end or from end to start.

Analogy: Imagine walking through a row of houses on a street. Walking forward means going from the first house to the last, and walking backward means going from the last house back to the first.

Head -> 1 ↔ 2 ↔ 3 ↔ 4 -> null
↑
Current position at head

Dry Run Walkthrough

Input: Doubly linked list: 1 ↔ 2 ↔ 3 ↔ 4, traverse forward then backward

Goal: Visit all nodes from start to end, then from end back to start

Step 1: Start at head node with value 1

1 [curr↑] ↔ 2 ↔ 3 ↔ 4 -> null

Why: We begin traversal at the first node

Step 2: Move forward to node with value 2

1 ↔ 2 [curr↑] ↔ 3 ↔ 4 -> null

Why: Visit next node in forward direction

Step 3: Move forward to node with value 3

1 ↔ 2 ↔ 3 [curr↑] ↔ 4 -> null

Why: Continue forward traversal

Step 4: Move forward to node with value 4 (tail)

1 ↔ 2 ↔ 3 ↔ 4 [curr↑] -> null

Why: Reached last node in forward traversal

Step 5: Start backward traversal from tail node 4

1 ↔ 2 ↔ 3 ↔ 4 [curr↑] -> null

Why: Begin visiting nodes backward from last node

Step 6: Move backward to node with value 3

1 ↔ 2 ↔ 3 [curr↑] ↔ 4 -> null

Why: Visit previous node in backward direction

Step 7: Move backward to node with value 2

1 ↔ 2 [curr↑] ↔ 3 ↔ 4 -> null

Why: Continue backward traversal

Step 8: Move backward to node with value 1 (head)

1 [curr↑] ↔ 2 ↔ 3 ↔ 4 -> null

Why: Reached first node in backward traversal

Result:

Forward traversal: 1 -> 2 -> 3 -> 4 -> null
Backward traversal: 4 -> 3 -> 2 -> 1 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for doubly linked list
typedef struct Node {
    int data;
    struct Node* next;
    struct Node* prev;
} Node;

// Create a new node with given data
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

// Append node at the end
void append(Node** head_ref, int data) {
    Node* newNode = createNode(data);
    if (*head_ref == NULL) {
        *head_ref = newNode;
        return;
    }
    Node* temp = *head_ref;
    while (temp->next != NULL) {
        temp = temp->next; // advance temp to last node
    }
    temp->next = newNode; // link last node to new node
    newNode->prev = temp; // link new node back to last node
}

// Traverse forward from head
void traverseForward(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data); // print current node data
        curr = curr->next; // move forward
    }
    printf("null\n");
}

// Traverse backward from tail
void traverseBackward(Node* tail) {
    Node* curr = tail;
    while (curr != NULL) {
        printf("%d -> ", curr->data); // print current node data
        curr = curr->prev; // move backward
    }
    printf("null\n");
}

int main() {
    Node* head = NULL;
    append(&head, 1);
    append(&head, 2);
    append(&head, 3);
    append(&head, 4);

    printf("Forward traversal: ");
    traverseForward(head);

    // Find tail for backward traversal
    Node* tail = head;
    while (tail->next != NULL) {
        tail = tail->next; // advance to last node
    }

    printf("Backward traversal: ");
    traverseBackward(tail);

    return 0;
}

while (temp->next != NULL) { temp = temp->next; // advance temp to last node }

advance temp to last node to append new node at end

temp->next = newNode; // link last node to new node newNode->prev = temp; // link new node back to last node

connect new node forward and backward pointers

while (curr != NULL) { printf("%d -> ", curr->data); // print current node data curr = curr->next; // move forward }

traverse forward visiting each node

while (curr != NULL) { printf("%d -> ", curr->data); // print current node data curr = curr->prev; // move backward }

traverse backward visiting each node

while (tail->next != NULL) { tail = tail->next; // advance to last node }

find tail node to start backward traversal

Output

Forward traversal: 1 -> 2 -> 3 -> 4 -> null

Backward traversal: 4 -> 3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once in forward and once in backward traversal

Space: O(1) because traversal uses only a few pointers, no extra storage proportional to n

vs Alternative: Compared to singly linked list, backward traversal is not possible without extra memory or reversing the list

Edge Cases

Empty list

Traversal prints 'null' immediately without errors

DSA C

if (*head_ref == NULL) { *head_ref = newNode; return; }

Single node list

Forward and backward traversal print the single node value once

DSA C

while (temp->next != NULL) { temp = temp->next; }

When to Use This Pattern

When you need to visit elements in both directions efficiently, use a doubly linked list traversal pattern.

Common Mistakes

Mistake: Trying to traverse backward in a singly linked list without extra memory
Fix: Use a doubly linked list or store nodes in a stack to simulate backward traversal

Summary

Visits each node forward from head to tail, then backward from tail to head in a doubly linked list.

Use when you need to move through data in both directions easily.

The key is that each node links to both next and previous nodes, allowing forward and backward moves.