Create and Initialize Doubly Linked List in DSA C

Mental Model

A doubly linked list is a chain of nodes where each node knows both its previous and next neighbor, allowing easy movement in both directions.

Analogy: Imagine a train where each carriage is connected to the one before and after it, so you can walk forward or backward through the train easily.

null ← [head] → null

Dry Run Walkthrough

Input: Create a doubly linked list with nodes containing values 1, 2, 3 in that order

Goal: Build a doubly linked list where each node points to the next and previous nodes correctly

Step 1: Create first node with value 1; set head to this node

null ← [1] → null

Why: We need a starting point for the list

Step 2: Create second node with value 2; link first node's next to second; second's prev to first

null ← 1 ↔ [2] → null

Why: Add second node and connect it both ways

Step 3: Create third node with value 3; link second node's next to third; third's prev to second

null ← 1 ↔ 2 ↔ [3] → null

Why: Add third node and maintain two-way links

Result:

null ← 1 ↔ 2 ↔ 3 → null

Annotated Code

DSA C

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

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

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

// Function to create and initialize doubly linked list from array
Node* createDoublyLinkedList(int arr[], int size) {
    if (size == 0) return NULL; // empty list

    Node* head = createNode(arr[0]); // create first node
    Node* curr = head;

    for (int i = 1; i < size; i++) {
        Node* newNode = createNode(arr[i]);
        curr->next = newNode; // link current node to new node
        newNode->prev = curr; // link new node back to current
        curr = newNode; // move current to new node
    }
    return head;
}

// Function to print doubly linked list forward
void printListForward(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d", curr->data);
        if (curr->next != NULL) printf(" ↔ ");
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 3};
    int size = sizeof(arr) / sizeof(arr[0]);

    Node* head = createDoublyLinkedList(arr, size);

    printListForward(head);

    return 0;
}

Node* head = createNode(arr[0]); // create first node

initialize head with first node

curr->next = newNode; // link current node to new node

link current node's next to new node

newNode->prev = curr; // link new node back to current

link new node's prev to current node

curr = newNode; // move current to new node

advance current pointer to new node

Output

1 ↔ 2 ↔ 3

Complexity Analysis

Time: O(n) because we create and link each of the n nodes once

Space: O(n) because we allocate memory for n nodes

vs Alternative: Compared to singly linked list creation, doubly linked list requires extra space and steps to set prev pointers but allows backward traversal

Edge Cases

Empty array input

Function returns NULL indicating empty list

DSA C

if (size == 0) return NULL; // empty list

Single element array

Creates one node with prev and next as NULL

DSA C

Node* head = createNode(arr[0]); // create first node

When to Use This Pattern

When you need a list where you can move forward and backward easily, use a doubly linked list to keep track of both neighbors.

Common Mistakes

Mistake: Not setting the prev pointer of the new node to the current node
Fix: Always assign newNode->prev = curr to maintain backward link

Mistake: Forgetting to update the current pointer to the new node after linking
Fix: Set curr = newNode to continue building the list correctly

Summary

Creates a doubly linked list where each node links to both previous and next nodes.

Use when you want to traverse a list in both directions easily.

Remember to link both next and prev pointers when adding nodes.

Practice

1. What is the main purpose of a doubly linked list in data structures?

easy

A. To allow traversal in both forward and backward directions

B. To store data in a fixed-size array

C. To sort data automatically

D. To store data only in one direction

Solution

1. Step 1: Understand doubly linked list structure

   A doubly linked list has nodes with pointers to both next and previous nodes.

2. Step 2: Identify traversal capability

   This structure allows moving forward and backward through the list easily.

3. Final Answer:

   To allow traversal in both forward and backward directions -> Option A

4. Quick Check:

   Doubly linked list = bidirectional traversal [OK]

Hint: Remember: doubly means two directions [OK]

Common Mistakes:

• Confusing doubly linked list with singly linked list
• Thinking it sorts data automatically
• Assuming it uses arrays internally

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

easy

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

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

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

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

Solution

1. Step 1: Check node structure for doubly linked list

   Each node must have data, a pointer to next node, and a pointer to previous node.

2. Step 2: Identify correct syntax

   struct Node { int data; struct Node* prev; struct Node* next; }; correctly declares pointers to next and prev nodes using struct Node*.

3. Final Answer:

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

4. Quick Check:

   Node has data + prev pointer + next pointer [OK]

Hint: Pointers to prev and next must be struct Node* [OK]

Common Mistakes:

• Using int instead of pointer for next/prev
• Missing prev pointer in node
• Declaring next/prev as struct Node instead of pointer

3. What will be the output of the following C code snippet that creates a doubly linked list with two nodes and prints their data?

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

int main() {
  Node* head = (Node*)malloc(sizeof(Node));
  Node* second = (Node*)malloc(sizeof(Node));

  head->data = 10;
  head->prev = NULL;
  head->next = second;

  second->data = 20;
  second->prev = head;
  second->next = NULL;

  printf("%d -> %d -> NULL", head->data, second->data);
  return 0;
}

medium

A. Compilation error

B. 20 -> 10 -> NULL

C. 10 -> 20 -> NULL

D. 10 -> NULL

Solution

1. Step 1: Analyze node creation and linking

   Two nodes are created: head with data 10, second with data 20. head->next points to second, second->prev points to head.

2. Step 2: Understand print statement

   Prints head->data (10), then second->data (20), then "-> NULL".

3. Final Answer:

   10 -> 20 -> NULL -> Option C

4. Quick Check:

   Prints data in order: 10 then 20 [OK]

Hint: Follow pointers to print nodes in order [OK]

Common Mistakes:

• Confusing order of nodes
• Forgetting to set next or prev pointers
• Assuming print shows backward traversal

4. Identify the error in the following code snippet that attempts to initialize a doubly linked list node:

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

int main() {
  struct Node* node = malloc(sizeof(struct Node));
  node->data = 5;
  node->prev = NULL;
  node->next = NULL;
  free(node);
  printf("%d", node->data);
  return 0;
}

medium

A. Accessing freed memory after free(node)

B. Missing #include

C. Incorrect struct declaration

D. No error, code runs fine

Solution

1. Step 1: Review memory allocation and freeing

   Memory is allocated for node, initialized, then freed with free(node).

2. Step 2: Identify invalid access

   After freeing, code tries to print node->data, which accesses freed memory causing undefined behavior.

3. Final Answer:

   Accessing freed memory after free(node) -> Option A

4. Quick Check:

   Using pointer after free = error [OK]

Hint: Never use pointer after free() [OK]

Common Mistakes:

• Ignoring use-after-free errors
• Forgetting to include stdlib.h (but not main error here)
• Assuming free deletes pointer variable

5. You want to create a doubly linked list with nodes containing values 1, 2, and 3 in that order. Which code snippet correctly initializes this list with proper prev and next pointers?

hard

A. Node* n1 = malloc(sizeof(Node)); n1->data=1; n1->prev=NULL; n1->next=NULL;
Node* n2 = malloc(sizeof(Node)); n2->data=2; n2->prev=NULL; n2->next=NULL;
n1->next=n2;
Node* n3 = malloc(sizeof(Node)); n3->data=3; n3->prev=NULL; n3->next=NULL;
n2->next=n3;

B. Node* n1 = malloc(sizeof(Node)); n1->data=1; n1->prev=NULL; n1->next=NULL;
Node* n2 = malloc(sizeof(Node)); n2->data=2; n2->prev=n1; n2->next=NULL;
n1->next=n2;
Node* n3 = malloc(sizeof(Node)); n3->data=3; n3->prev=n2; n3->next=n1;
n2->next=n3;

C. Node* n1 = malloc(sizeof(Node)); n1->data=1; n1->prev=NULL; n1->next=NULL;
Node* n2 = malloc(sizeof(Node)); n2->data=2; n2->prev=n1; n2->next=NULL;
n1->next=n2;
Node* n3 = malloc(sizeof(Node)); n3->data=3; n3->prev=NULL; n3->next=NULL;
n2->next=n3;

D. Node* n1 = malloc(sizeof(Node)); n1->data=1; n1->prev=NULL; n1->next=NULL;
Node* n2 = malloc(sizeof(Node)); n2->data=2; n2->prev=n1; n2->next=NULL;
n1->next=n2;
Node* n3 = malloc(sizeof(Node)); n3->data=3; n3->prev=n2; n3->next=NULL;
n2->next=n3;

Solution

1. Step 1: Check initialization of first node

   n1 has data=1, prev=NULL, next=NULL initially.

2. Step 2: Link second node correctly

   n2 has data=2, prev=n1, next=NULL; n1->next points to n2.

3. Step 3: Link third node correctly

   n3 has data=3, prev=n2, next=NULL; n2->next points to n3.

4. Final Answer:

   Code snippet B correctly sets prev and next pointers for all nodes -> Option D

5. Quick Check:

   Each node's prev and next link neighbors properly [OK]

Hint: Prev of first is NULL; next of last is NULL [OK]

Common Mistakes:

• Not setting prev pointers for nodes after first
• Setting next pointers incorrectly
• Making circular links unintentionally