Traversal Forward and Backward in DSA C - Build from Scratch

Traversal Forward and Backward in a Doubly Linked List

📖 Scenario: Imagine you are managing a playlist of songs where you can move forward to the next song or backward to the previous song. This playlist is stored as a doubly linked list, where each song knows the next and previous songs.

🎯 Goal: You will create a doubly linked list with three songs, then traverse the list forward to print the songs in order, and finally traverse backward to print the songs in reverse order.

📋 What You'll Learn

Create a doubly linked list with exactly three nodes containing the song names: "Song1", "Song2", and "Song3"

Create a pointer called head pointing to the first node

Create a pointer called tail pointing to the last node

Traverse the list forward using a pointer called current and print each song name

Traverse the list backward using the same current pointer and print each song name

💡 Why This Matters

🌍 Real World

Doubly linked lists are used in music players, web browsers (back and forward navigation), and undo-redo features where moving forward and backward is needed.

💼 Career

Understanding traversal in doubly linked lists is important for software developers working on applications that require efficient two-way navigation through data.

1

Create the doubly linked list nodes

Define a struct called Node with char *data, struct Node *next, and struct Node *prev. Then create three nodes named node1, node2, and node3 with data "Song1", "Song2", and "Song3" respectively. Link node1 to node2 and node2 to node3 using next and prev pointers.

DSA C

// Define struct Node and create three linked nodes with data "Song1", "Song2", "Song3"
// Link nodes using next and prev pointers

Hint

Start by defining the Node struct with three fields. Then create three variables of type Node. Assign the song names to data and link the nodes using next and prev.

2

Create head and tail pointers

Inside main, create two pointers called head and tail. Set head to point to node1 and tail to point to node3.

DSA C

#include 
#include 

struct Node {
    char *data;
    struct Node *next;
    struct Node *prev;
};

int main() {
    struct Node node1, node2, node3;

    node1.data = "Song1";
    node1.next = &node2;
    node1.prev = NULL;

    node2.data = "Song2";
    node2.next = &node3;
    node2.prev = &node1;

    node3.data = "Song3";
    node3.next = NULL;
    node3.prev = &node2;

    // Create head and tail pointers
    // Your code here

    return 0;
}

Hint

Use pointers of type struct Node * and assign them the addresses of node1 and node3.

3

Traverse forward and backward

Create a pointer called current. First, set current to head and use a while loop to traverse forward printing each node's data. Then set current to tail and use another while loop to traverse backward printing each node's data.

DSA C

#include 
#include 

struct Node {
    char *data;
    struct Node *next;
    struct Node *prev;
};

int main() {
    struct Node node1, node2, node3;

    node1.data = "Song1";
    node1.next = &node2;
    node1.prev = NULL;

    node2.data = "Song2";
    node2.next = &node3;
    node2.prev = &node1;

    node3.data = "Song3";
    node3.next = NULL;
    node3.prev = &node2;

    struct Node *head = &node1;
    struct Node *tail = &node3;

    // Traverse forward and backward printing data
    // Your code here

    return 0;
}

Hint

Use a pointer current to move through the list. For forward traversal, move using next. For backward traversal, move using prev. Print the data at each node.

4

Print the traversal output

Run the program to print the song names first in forward order and then in backward order, each on its own line.

DSA C

#include 
#include 

struct Node {
    char *data;
    struct Node *next;
    struct Node *prev;
};

int main() {
    struct Node node1, node2, node3;

    node1.data = "Song1";
    node1.next = &node2;
    node1.prev = NULL;

    node2.data = "Song2";
    node2.next = &node3;
    node2.prev = &node1;

    node3.data = "Song3";
    node3.next = NULL;
    node3.prev = &node2;

    struct Node *head = &node1;
    struct Node *tail = &node3;

    struct Node *current = head;
    while (current != NULL) {
        printf("%s\n", current->data);
        current = current->next;
    }

    current = tail;
    while (current != NULL) {
        printf("%s\n", current->data);
        current = current->prev;
    }

    return 0;
}

// Run the program to see the output

Hint

When you run the program, it should print the songs in forward order first, then backward order, each song on its own line.

Practice

1. What does forward traversal in a linked list mean?

easy

A. Visiting nodes from the first node to the last node

B. Visiting nodes from the last node to the first node

C. Skipping every alternate node while visiting

D. Visiting nodes randomly

Solution

1. Step 1: Understand forward traversal

   Forward traversal means starting at the first node and moving to the next node repeatedly until the end.

2. Step 2: Compare with options

   Only Visiting nodes from the first node to the last node describes visiting nodes from first to last, which matches forward traversal.

3. Final Answer:

   Visiting nodes from the first node to the last node -> Option A

4. Quick Check:

   Forward traversal = first to last [OK]

Hint: Forward means start to end in order [OK]

Common Mistakes:

• Confusing forward with backward traversal
• Thinking traversal is random
• Assuming skipping nodes is traversal

2. Which of the following is the correct syntax to traverse a singly linked list forward in C?

easy

A. for(Node* curr = head; curr != NULL; curr = curr->prev) { /* process curr */ }

B. for(Node* curr = head; curr != NULL; curr = curr->next) { /* process curr */ }

C. while(head != NULL) { head = head->prev; }

D. for(Node* curr = tail; curr != NULL; curr = curr->prev) { /* process curr */ }

Solution

1. Step 1: Identify forward traversal syntax

   Forward traversal in singly linked list uses next pointer starting from head.

2. Step 2: Check options for correct pointer usage

   for(Node* curr = head; curr != NULL; curr = curr->next) { /* process curr */ } uses curr = curr->next starting from head, which is correct.

3. Final Answer:

   for(Node* curr = head; curr != NULL; curr = curr->next) { /* process curr */ } -> Option B

4. Quick Check:

   Use next pointer from head for forward traversal [OK]

Hint: Use next pointer from head for forward traversal [OK]

Common Mistakes:

• Using prev pointer in singly linked list
• Starting from tail in singly linked list
• Using incorrect loop conditions

3. What will be the output of the following code snippet that traverses a doubly linked list backward?

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

void printBackward(Node* tail) {
  Node* curr = tail;
  while(curr != NULL) {
    printf("%d ", curr->data);
    curr = curr->prev;
  }
}

// List: 1 <-> 2 <-> 3, tail points to node with data 3
printBackward(tail);

medium

A. 1 2 3

B. 3 1 2

C. 3 2 1

D. 2 3 1

Solution

1. Step 1: Understand backward traversal in doubly linked list

   Starting from tail (3), moving prev pointer visits nodes 3, 2, then 1.

2. Step 2: Trace the output

   Prints 3, then 2, then 1 with spaces.

3. Final Answer:

   3 2 1 -> Option C

4. Quick Check:

   Backward traversal prints tail to head [OK]

Hint: Backward traversal prints from tail to head [OK]

Common Mistakes:

• Confusing order of printing
• Using next pointer instead of prev
• Starting from head instead of tail

4. Identify the error in the following code that attempts to traverse a doubly linked list backward:

void traverseBackward(Node* tail) {
  Node* curr = tail;
  while(curr->next != NULL) {
    printf("%d ", curr->data);
    curr = curr->prev;
  }
}

medium

A. The printf statement is missing a newline character

B. The pointer curr should start from head, not tail

C. The code should use curr = curr->next instead of curr = curr->prev

D. The loop condition should check curr != NULL, not curr->next != NULL

Solution

1. Step 1: Analyze loop condition for backward traversal

   Backward traversal moves using prev pointer until curr becomes NULL.

2. Step 2: Identify incorrect condition

   Checking curr->next != NULL is wrong; it should be curr != NULL to avoid null pointer access.

3. Final Answer:

   The loop condition should check curr != NULL, not curr->next != NULL -> Option D

4. Quick Check:

   Loop until curr is NULL in backward traversal [OK]

Hint: Check curr != NULL in loops, not curr->next for backward traversal [OK]

Common Mistakes:

• Using next pointer condition in backward traversal
• Starting from head instead of tail
• Ignoring null pointer checks

5. Given a doubly linked list with nodes containing integers, write a function to print the list forward and then backward without using extra space. Which approach correctly achieves this?

hard

A. Traverse from head to tail printing data, then traverse from tail to head printing data

B. Traverse from head to tail printing data twice

C. Traverse from tail to head printing data, then traverse from head to tail printing data

D. Traverse from head to tail printing data, then reverse the list and print forward again

Solution

1. Step 1: Understand traversal without extra space

   Use existing next and prev pointers to traverse forward and backward.

2. Step 2: Identify correct approach

   Traverse from head to tail printing data, then traverse from tail to head printing data correctly traverses forward from head to tail, then backward from tail to head printing data without modifying list.

3. Final Answer:

   Traverse from head to tail printing data, then traverse from tail to head printing data -> Option A

4. Quick Check:

   Use head and tail pointers for forward and backward traversal [OK]

Hint: Print forward from head, backward from tail without changing list [OK]

Common Mistakes:

• Reversing list unnecessarily
• Printing forward twice
• Using extra space like arrays or stacks