Doubly Linked List Structure and Node Design in DSA C

Mental Model

A doubly linked list is a chain of nodes where each node knows both its previous and next neighbor, making it easy to move forward and backward.

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

null ← [prev|data|next] -> null

Dry Run Walkthrough

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

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

Step 1: Create first node with value 1, prev and next point to null

null ← [null|1|null] -> null

Why: First node has no neighbors yet, so both pointers are null

Step 2: Create second node with value 2, link it after first node

null ← [null|1|2] -> [1|2|null] -> null

Why: First node's next points to second node; second node's prev points back to first

Step 3: Create third node with value 3, link it after second node

null ← [null|1|2] -> [1|2|3] -> [2|3|null] -> null

Why: Second node's next points to third node; third node's prev points back to second

Result:

null ← [null|1|2] -> [1|2|3] -> [2|3|null] -> 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 print the doubly linked list from head to tail
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d", curr->data);
        if (curr->next != NULL) {
            printf(" <-> ");
        }
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    // Step 1: Create first node
    Node* head = createNode(1);

    // Step 2: Create second node and link
    Node* second = createNode(2);
    head->next = second;          // first node next points to second
    second->prev = head;          // second node prev points to first

    // Step 3: Create third node and link
    Node* third = createNode(3);
    second->next = third;         // second node next points to third
    third->prev = second;         // third node prev points to second

    // Print the list
    printList(head);

    // Free memory
    free(third);
    free(second);
    free(head);

    return 0;
}

Node* newNode = (Node*)malloc(sizeof(Node));

allocate memory for new node

newNode->prev = NULL; newNode->next = NULL;

initialize pointers to null for isolated node

head->next = second; second->prev = head;

link first and second nodes bidirectionally

second->next = third; third->prev = second;

link second and third nodes bidirectionally

while (curr != NULL) { ... curr = curr->next; }

traverse list forward to print all node data

Output

1 <-> 2 <-> 3

Complexity Analysis

Time: O(n) because printing or traversing the list visits each node once

Space: O(n) because each node is stored separately in memory

vs Alternative: Compared to singly linked list, doubly linked list uses extra space for prev pointer but allows backward traversal

Edge Cases

Empty list (no nodes)

Printing shows nothing; no nodes to link

DSA C

while (curr != NULL) { ... }

Single node list

Node prev and next remain NULL; list prints single value

DSA C

newNode->prev = NULL; newNode->next = NULL;

When to Use This Pattern

When you need to move both forward and backward through a list easily, use a doubly linked list structure because each node stores links to both neighbors.

Common Mistakes

Mistake: Forgetting to set the prev pointer when linking nodes
Fix: Always assign both next and prev pointers when connecting nodes

Mistake: Not initializing prev and next pointers to NULL in new nodes
Fix: Set prev and next to NULL in node creation to avoid dangling pointers

Summary

It creates nodes that link forward and backward to form a doubly linked list.

Use it when you want easy two-way navigation through a list of items.

Remember each node has two pointers: one to the previous and one to the next node.