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.