Doubly Linked Lists

Overview

A doubly linked list is a linear data structure where each node contains pointers to both the next and previous nodes, enabling bidirectional traversal. This provides more flexibility than singly linked lists at the cost of extra memory for the additional pointer.

Data Structure Definition

The doubly linked list node is defined in lists.h:15-20:

lists.h

typedef struct dlistint_s
{
    int n;
    struct dlistint_s *prev;
    struct dlistint_s *next;
} dlistint_t;

Each node contains:

n: The integer value
prev: Pointer to the previous node (NULL for head)
next: Pointer to the next node (NULL for tail)

This bidirectional linking allows traversal in both directions and easier insertion/deletion operations.

Basic Operations

Traversal and Printing

print_dlistint.c

/**
 * print_dlistint - prints all the elements of a dlistint_t list
 * @h: pointer to the head of the list
 * Return: the number of nodes
 */
size_t print_dlistint(const dlistint_t *h)
{
    size_t i = 0;

    while (h != NULL)
    {
        printf("%d\n", h->n);
        h = h->next;
        i++;
    }
    return (i);
}

Time Complexity: O(n) - visits each node once
Space Complexity: O(1) - only counter variable

Insertion Operations

Insert at Beginning

add_dnodeint.c

/**
 * *add_dnodeint - adds a new node at the beginning of a dlistint_t list
 * @head: pointer to the head of the list
 * @n: integer to add to the new node
 * Return: the address of the new element, or NULL if it failed
 */
dlistint_t *add_dnodeint(dlistint_t **head, const int n)
{
    dlistint_t *new_node;

    new_node = malloc(sizeof(dlistint_t));
    if (new_node == NULL)
        return (NULL);
    new_node->n = n;
    new_node->next = *head;
    new_node->prev = NULL;
    if (*head != NULL)
        (*head)->prev = new_node;
    *head = new_node;
    return (new_node);
}

Show Understanding Bidirectional Linking

Before insertion:

NULL <- [HEAD: 5] <-> [2] <-> [1] -> NULL

After add_dnodeint(&head, 10):

NULL <- [HEAD: 10] <-> [5] <-> [2] <-> [1] -> NULL
        ^new_node      ^old head

Critical steps:

new_node->next = *head - Point forward to old head
new_node->prev = NULL - New head has no previous
(*head)->prev = new_node - Old head’s prev points back to new node
*head = new_node - Update head pointer

Edge case: If list is empty (*head == NULL), skip step 3.

Insert at End

add_dnodeint_end.c

/**
 * *add_dnodeint_end - adds a new node at the end of a dlistint_t list
 * @head: pointer to the head of the list
 * @n: integer to add to the new node
 * Return: address of the new node or NULL if it failed
 */
dlistint_t *add_dnodeint_end(dlistint_t **head, const int n)
{
    dlistint_t *h;
    dlistint_t *new;

    new = malloc(sizeof(dlistint_t));
    if (new == NULL)
        return (NULL);

    new->n = n;
    new->next = NULL;

    h = *head;

    if (h != NULL)
    {
        while (h->next != NULL)
            h = h->next;
        h->next = new;
    }
    else
    {
        *head = new;
    }

    new->prev = h;

    return (new);
}

Key differences from singly linked list:

After finding the tail, we must set new->prev = h to link backward
The tail can now traverse backward to reach any previous node
Setting new->prev = h works even when h is NULL (empty list case)

Time Complexity: O(n) - must traverse to find tail

Advanced Operations

Insert at Index

insert_dnodeint_at_index.c

/**
 * *insert_dnodeint_at_index - inserts a new node at a given position
 * @h: pointer to the head of the list
 * @idx: position of the node to return
 * @n: value to add to the node
 * Return: address of the nth node or NULL if it failed
 */
dlistint_t *insert_dnodeint_at_index(dlistint_t **h, unsigned int idx, int n)
{
    dlistint_t *new;
    dlistint_t *head;
    unsigned int i;

    new = NULL;
    if (idx == 0)
        new = add_dnodeint(h, n);
    else
    {
        head = *h;
        i = 1;
        if (head != NULL)
            while (head->prev != NULL)
                head = head->prev;
        while (head != NULL)
        {
            if (i == idx)
            {
                if (head->next == NULL)
                    new = add_dnodeint_end(h, n);
                else
                {
                    new = malloc(sizeof(dlistint_t));
                    if (new != NULL)
                    {
                        new->n = n;
                        new->next = head->next;
                        new->prev = head;
                        head->next->prev = new;
                        head->next = new;
                    }
                }
                break;
            }
            head = head->next;
            i++;
        }
    }

    return (new);
}

Show Visualizing Insertion at Index

Inserting value 99 at index 2:Before:

NULL <- [0] <-> [1] <-> [2] <-> [3] -> NULL
                 idx=1   idx=2
                         (head points here)

After:

NULL <- [0] <-> [1] <-> [99] <-> [2] <-> [3] -> NULL
                         ^new

Four pointer updates required:

new->next = head->next;      // new -> [2]
new->prev = head;            // [1] <- new
head->next->prev = new;      // [2]'s prev -> new  
head->next = new;            // [1] -> new

Compare to singly linked list (only 2 pointer updates):

new->next = head->next;
head->next = new;

Delete at Index

delete_dnodeint_at_index.c

/**
 * delete_dnodeint_at_index - deletes a node at a given position
 * @head: pointer to the head of the list
 * @index: position of the node to return
 * Return: 1 on success, -1 on failure
 */
int delete_dnodeint_at_index(dlistint_t **head, unsigned int index)
{
    dlistint_t *h1;
    dlistint_t *h2;
    unsigned int i;

    h1 = *head;

    if (h1 != NULL)
        while (h1->prev != NULL)
            h1 = h1->prev;

    i = 0;

    while (h1 != NULL)
    {
        if (i == index)
        {
            if (i == 0)
            {
                *head = h1->next;
                if (*head != NULL)
                    (*head)->prev = NULL;
            }
            else
            {
                h2->next = h1->next;

                if (h1->next != NULL)
                    h1->next->prev = h2;
            }

            free(h1);
            return (1);
        }
        h2 = h1;
        h1 = h1->next;
        i++;
    }

    return (-1);
}

Deletion requires updating both directions:Case 1: Delete head (index 0)

*head = h1->next;           // Move head forward
if (*head != NULL)
    (*head)->prev = NULL;   // New head has no previous

Case 2: Delete middle/end node

h2->next = h1->next;        // Bridge forward link
if (h1->next != NULL)
    h1->next->prev = h2;    // Bridge backward link

Always check if next exists before updating its prev pointer!

Complete Function Set

From lists.h:22-30, the full API includes:

lists.h

size_t print_dlistint(const dlistint_t *h);
size_t dlistint_len(const dlistint_t *h);
dlistint_t *add_dnodeint(dlistint_t **head, const int n);
dlistint_t *add_dnodeint_end(dlistint_t **head, const int n);
void free_dlistint(dlistint_t *head);
dlistint_t *get_dnodeint_at_index(dlistint_t *head, unsigned int index);
int sum_dlistint(dlistint_t *head);
dlistint_t *insert_dnodeint_at_index(dlistint_t **h, unsigned int idx, int n);
int delete_dnodeint_at_index(dlistint_t **head, unsigned int index);

Usage Example

example.c

#include "lists.h"

int main(void)
{
    dlistint_t *head = NULL;
    
    /* Build list: 3 <-> 2 <-> 1 */
    add_dnodeint(&head, 1);
    add_dnodeint(&head, 2);
    add_dnodeint(&head, 3);
    
    /* Add to end: 3 <-> 2 <-> 1 <-> 0 */
    add_dnodeint_end(&head, 0);
    
    /* Insert at index 2: 3 <-> 2 <-> 99 <-> 1 <-> 0 */
    insert_dnodeint_at_index(&head, 2, 99);
    
    /* Traverse forward */
    dlistint_t *current = head;
    while (current)
    {
        printf("%d ", current->n);
        current = current->next;
    }
    // Output: 3 2 99 1 0
    
    /* Traverse backward from any node */
    current = get_dnodeint_at_index(head, 4);  // Get last node
    while (current)
    {
        printf("%d ", current->n);
        current = current->prev;
    }
    // Output: 0 1 99 2 3
    
    /* Delete at index 2 */
    delete_dnodeint_at_index(&head, 2);
    
    /* Cleanup */
    free_dlistint(head);
    
    return (0);
}

Complexity Summary

Operation	Time	Space	Notes
Insert at head	O(1)	O(1)	Direct access
Insert at tail	O(n)	O(1)	Must find tail
Insert at index	O(n)	O(1)	Traverse to position
Delete at index	O(n)	O(1)	Traverse to position
Search	O(n)	O(1)	Linear search
Traverse forward	O(n)	O(1)	Visit each node
Traverse backward	O(n)	O(1)	Unique to doubly linked

Advantages Over Singly Linked Lists

Bidirectional traversal: Can move forward and backward through the list
Easier deletion: Given a node, can delete it without needing previous node reference
Better for certain algorithms: Ideal for LRU caches, browser history, undo/redo functionality
Symmetric operations: Insert and delete operations are more uniform

Trade-offs

Advantages:

Bidirectional traversal
Easier node deletion when you have direct reference to the node
More flexible for certain algorithms

Disadvantages:

Extra memory for prev pointer (approximately 50% more per node)
More pointer updates per operation (4 vs 2 for insertions)
Slightly more complex code to maintain both directions

Get Started

Fundamentals

Pointers & Memory

Advanced Concepts

Data Structures

System Programming

Overview

Data Structure Definition

Basic Operations

Traversal and Printing

Insertion Operations

Insert at Beginning

Insert at End

Advanced Operations

Insert at Index

Delete at Index

Complete Function Set

Usage Example

Complexity Summary

Advantages Over Singly Linked Lists

Trade-offs

Build docs developers (and LLMs) love

Get Started

Fundamentals

Pointers & Memory

Advanced Concepts

Data Structures

System Programming

​Overview

​Data Structure Definition

​Basic Operations

​Traversal and Printing

​Insertion Operations

​Insert at Beginning

​Insert at End

​Advanced Operations

​Insert at Index

​Delete at Index

​Complete Function Set

​Usage Example

​Complexity Summary

​Advantages Over Singly Linked Lists

​Trade-offs

Build docs developers (and LLMs) love

Overview

Data Structure Definition

Basic Operations

Traversal and Printing

Insertion Operations

Insert at Beginning

Insert at End

Advanced Operations

Insert at Index

Delete at Index

Complete Function Set

Usage Example

Complexity Summary

Advantages Over Singly Linked Lists

Trade-offs