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.