Why Doubly Linked List Over Singly Linked List in DSA C - See It Work

Why Doubly Linked List Over Singly Linked List

📖 Scenario: Imagine you are managing a playlist of songs where you want to move forward and backward easily between songs.A singly linked list lets you move forward only, but a doubly linked list lets you move both forward and backward.

🎯 Goal: You will create a simple doubly linked list with three songs, then show how to move forward and backward through the list.

📋 What You'll Learn

Create a doubly linked list node structure with data, next, and prev pointers

Create three nodes with song names: "Song1", "Song2", "Song3"

Link the nodes to form a doubly linked list

Traverse the list forward and print the song names

Traverse the list backward and print the song names

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding doubly linked lists helps in software development roles that involve data structure design, memory management, and building efficient navigation systems.

1

Create doubly linked list nodes with song names

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

DSA C

// Define struct Node and create node1, node2, node3 with data
// Your code here

Hint

Remember to include next and prev pointers in the struct for doubly linked list nodes.

2

Link the nodes to form a doubly linked list

Link node1 to node2 and node2 to node3 by setting their next and prev pointers correctly to form a doubly linked list.

DSA C

#include 
#include 

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

int main() {
    Node node1, node2, node3;
    node1.data = "Song1";
    node2.data = "Song2";
    node3.data = "Song3";

    // Link nodes to form doubly linked list
    // Your code here

    return 0;
}

Hint

Set next of a node to the next node's address and prev to the previous node's address. The first node's prev and last node's next are NULL.

3

Traverse the list forward and backward

Create a pointer current starting at &node1. Use a while loop to move forward using current->next and print each node's data. Then move backward from the last node using current->prev and print each node's data.

DSA C

#include 
#include 

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

int main() {
    Node node1, node2, node3;
    node1.data = "Song1";
    node2.data = "Song2";
    node3.data = "Song3";

    node1.next = &node2;
    node1.prev = NULL;

    node2.next = &node3;
    node2.prev = &node1;

    node3.next = NULL;
    node3.prev = &node2;

    // Traverse forward and backward
    // Your code here

    return 0;
}

Hint

Use one loop to go forward until current->next is NULL, then another loop to go backward until current is NULL.

4

Print the traversal results

Print the song names during forward and backward traversal exactly as shown in the code. The output should first list songs forward, then backward.

DSA C

#include 
#include 

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

int main() {
    Node node1, node2, node3;
    node1.data = "Song1";
    node2.data = "Song2";
    node3.data = "Song3";

    node1.next = &node2;
    node1.prev = NULL;

    node2.next = &node3;
    node2.prev = &node1;

    node3.next = NULL;
    node3.prev = &node2;

    Node *current = &node1;
    printf("Forward traversal:\n");
    while (current != NULL) {
        printf("%s\n", current->data);
        if (current->next == NULL) {
            break;
        }
        current = current->next;
    }

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

    return 0;

    // Your code here
}

Hint

Run the program and check that the output matches the forward and backward song lists exactly.

Practice

1. Why might a doubly linked list be preferred over a singly linked list?

easy

A. Because it cannot be modified after creation

B. Because it uses less memory than singly linked list

C. Because it only stores one pointer per node

D. Because it allows traversal in both forward and backward directions

Solution

1. Step 1: Understand traversal capabilities

   A singly linked list allows traversal only in one direction, from head to tail.

2. Step 2: Compare with doubly linked list

   A doubly linked list stores two pointers per node, allowing traversal forward and backward.

3. Final Answer:

   Because it allows traversal in both forward and backward directions -> Option D

4. Quick Check:

   Traversal direction = Both [OK]

Hint: Doubly linked lists have two pointers per node [OK]

Common Mistakes:

• Thinking doubly linked lists use less memory
• Confusing traversal directions
• Assuming singly linked lists allow backward traversal

2. Which of the following is the correct way to declare a node in a doubly linked list in C?

easy

A. struct Node { int data; struct Node* prev; };

B. struct Node { int data; struct Node* next; };

C. struct Node { int data; struct Node* prev; struct Node* next; };

D. struct Node { int data; int next; int prev; };

Solution

1. Step 1: Identify required pointers for doubly linked list node

   A doubly linked list node must have pointers to both previous and next nodes.

2. Step 2: Check each option

   struct Node { int data; struct Node* prev; struct Node* next; }; correctly declares both prev and next pointers as struct Node pointers.

3. Final Answer:

   struct Node { int data; struct Node* prev; struct Node* next; }; -> Option C

4. Quick Check:

   Node pointers = prev and next [OK]

Hint: Doubly linked nodes have both prev and next pointers [OK]

Common Mistakes:

• Omitting prev pointer
• Using int instead of pointer for next/prev
• Confusing singly linked list node with doubly linked

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

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

Node* head = NULL;

// Function to add node at end
void append(int val) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = val;
  newNode->next = NULL;
  if (head == NULL) {
    newNode->prev = NULL;
    head = newNode;
    return;
  }
  Node* temp = head;
  while (temp->next != NULL) temp = temp->next;
  temp->next = newNode;
  newNode->prev = temp;
}

// Print list forward
void printForward() {
  Node* temp = head;
  while (temp != NULL) {
    printf("%d ", temp->data);
    temp = temp->next;
  }
}

int main() {
  append(10);
  append(20);
  append(30);
  printForward();
  return 0;
}

medium

A. 10 20 30

B. 30 20 10

C. 10 20

D. Compilation error

Solution

1. Step 1: Trace append function calls

   append(10) creates first node with data 10, head points to it. append(20) adds node with 20 at end. append(30) adds node with 30 at end.

2. Step 2: Trace printForward function

   printForward starts at head and prints data while moving next. It prints 10, then 20, then 30.

3. Final Answer:

   10 20 30 -> Option A

4. Quick Check:

   List forward print = 10 20 30 [OK]

Hint: Forward print shows nodes in insertion order [OK]

Common Mistakes:

• Confusing forward and backward traversal
• Assuming printForward prints in reverse
• Missing NULL checks causing errors

4. Identify the bug in the following code snippet that tries to delete the last node of a doubly linked list:

void deleteLast() {
  if (head == NULL) return;
  Node* temp = head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->prev->next = NULL;
  free(temp);
}

medium

A. No bug, code works correctly

B. Does not handle case when list has only one node

C. Incorrect pointer used for deletion

D. Memory leak due to missing free

Solution

1. Step 1: Analyze deletion logic

   The code finds last node by moving to node where next is NULL, then sets previous node's next to NULL and frees last node.

2. Step 2: Check edge case for single node list

   If list has only one node, temp->prev is NULL, so temp->prev->next causes a crash or undefined behavior.

3. Final Answer:

   Does not handle case when list has only one node -> Option B

4. Quick Check:

   Single node deletion needs special handling [OK]

Hint: Check for single node before accessing prev pointer [OK]

Common Mistakes:

• Ignoring single node edge case
• Assuming prev pointer always exists
• Not freeing memory after deletion

5. You want to implement a feature that allows moving backward through a list of recently opened files in a text editor. Which linked list type is best and why?

hard

A. Doubly linked list, because it allows moving backward and forward easily

B. Singly linked list, because it uses less memory and is simpler

C. Circular singly linked list, because it loops infinitely

D. Array, because linked lists cannot move backward

Solution

1. Step 1: Understand feature requirements

   The feature requires moving backward and forward through the list of files.

2. Step 2: Match data structure capabilities

   Singly linked lists allow only forward traversal, arrays allow random access but not efficient insertion/deletion, doubly linked lists allow easy backward and forward traversal.

3. Step 3: Evaluate options

   Doubly linked list fits best because it supports moving backward and forward efficiently.

4. Final Answer:

   Doubly linked list, because it allows moving backward and forward easily -> Option A

5. Quick Check:

   Backward traversal = Doubly linked list [OK]

Hint: Backward navigation needs doubly linked list [OK]

Common Mistakes:

• Choosing singly linked list for backward moves
• Ignoring traversal needs
• Assuming arrays handle backward traversal efficiently