A doubly linked list is a linear data structure where each node contains data and two pointers: one pointing to the next node and another pointing to the previous node. This bidirectional linking enables traversal in both directions, making operations like insertion, deletion, and reverse traversal more efficient compared to singly linked lists. For C programmers, mastering doubly linked lists is essential for implementing complex data structures like deques, memory management systems, and navigation systems.

What is a Doubly Linked List?

In a doubly linked list, each node has three components:

• Data: The actual value stored in the node
• Next pointer: Points to the next node in the list (or NULL if last)
• Prev pointer: Points to the previous node in the list (or NULL if first)

This bidirectional linking allows O(1) insertion and deletion at both ends and anywhere in the middle when you have a pointer to the node.

Why Doubly Linked Lists are Essential in C

1. Bidirectional Traversal: Navigate forward and backward through the list
2. Efficient Deletion: Delete any node without needing the previous node reference
3. Deque Operations: O(1) insertion and deletion at both ends
4. Navigation Systems: Implement next/previous functionality easily
5. Undo/Redo Features: Track operations in both directions
6. LRU Caches: Implement least-recently-used cache eviction policies

Basic Doubly Linked List Implementation

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Node structure for doubly linked list
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
// List structure to manage head and tail
typedef struct {
Node *head;
Node *tail;
int size;
} DoublyLinkedList;
// Create a new node
Node* createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed\n");
return NULL;
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// Initialize an empty list
DoublyLinkedList* createList() {
DoublyLinkedList *list = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList));
if (list == NULL) {
printf("Memory allocation failed\n");
return NULL;
}
list->head = NULL;
list->tail = NULL;
list->size = 0;
return list;
}
// Check if list is empty
bool isEmpty(DoublyLinkedList *list) {
return list->head == NULL;
}
// Get list size
int getSize(DoublyLinkedList *list) {
return list->size;
}

Insertion Operations

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// INSERTION OPERATIONS
// ============================================================
// Insert at beginning (head)
void insertAtHead(DoublyLinkedList *list, int data) {
Node *newNode = createNode(data);
if (newNode == NULL) return;
if (isEmpty(list)) {
// List was empty
list->head = newNode;
list->tail = newNode;
} else {
newNode->next = list->head;
list->head->prev = newNode;
list->head = newNode;
}
list->size++;
printf("Inserted %d at head\n", data);
}
// Insert at end (tail)
void insertAtTail(DoublyLinkedList *list, int data) {
Node *newNode = createNode(data);
if (newNode == NULL) return;
if (isEmpty(list)) {
list->head = newNode;
list->tail = newNode;
} else {
newNode->prev = list->tail;
list->tail->next = newNode;
list->tail = newNode;
}
list->size++;
printf("Inserted %d at tail\n", data);
}
// Insert at specific position (0-based index)
bool insertAtPosition(DoublyLinkedList *list, int data, int position) {
if (position < 0 || position > list->size) {
printf("Invalid position! Valid positions: 0 to %d\n", list->size);
return false;
}
if (position == 0) {
insertAtHead(list, data);
return true;
}
if (position == list->size) {
insertAtTail(list, data);
return true;
}
Node *newNode = createNode(data);
if (newNode == NULL) return false;
// Traverse to the insertion point
Node *current = list->head;
for (int i = 0; i < position; i++) {
current = current->next;
}
// Insert before current
newNode->prev = current->prev;
newNode->next = current;
current->prev->next = newNode;
current->prev = newNode;
list->size++;
printf("Inserted %d at position %d\n", data, position);
return true;
}
// Insert after a specific node (given node pointer)
bool insertAfterNode(Node *prevNode, int data) {
if (prevNode == NULL) {
printf("Previous node cannot be NULL\n");
return false;
}
Node *newNode = createNode(data);
if (newNode == NULL) return false;
newNode->next = prevNode->next;
newNode->prev = prevNode;
if (prevNode->next != NULL) {
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
printf("Inserted %d after node with data %d\n", data, prevNode->data);
return true;
}
// Insert before a specific node (given node pointer)
bool insertBeforeNode(Node *nextNode, int data) {
if (nextNode == NULL) {
printf("Next node cannot be NULL\n");
return false;
}
Node *newNode = createNode(data);
if (newNode == NULL) return false;
newNode->prev = nextNode->prev;
newNode->next = nextNode;
if (nextNode->prev != NULL) {
nextNode->prev->next = newNode;
}
nextNode->prev = newNode;
printf("Inserted %d before node with data %d\n", data, nextNode->data);
return true;
}
// Insert in sorted order (assuming list is sorted)
void insertSorted(DoublyLinkedList *list, int data) {
if (isEmpty(list) || data <= list->head->data) {
insertAtHead(list, data);
return;
}
if (data >= list->tail->data) {
insertAtTail(list, data);
return;
}
Node *current = list->head;
while (current != NULL && current->data < data) {
current = current->next;
}
// Insert before current
insertBeforeNode(current, data);
}

Deletion Operations

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// DELETION OPERATIONS
// ============================================================
// Delete from head
int deleteFromHead(DoublyLinkedList *list) {
if (isEmpty(list)) {
printf("List is empty! Cannot delete\n");
return -1;
}
Node *temp = list->head;
int data = temp->data;
if (list->head == list->tail) {
// Only one node
list->head = NULL;
list->tail = NULL;
} else {
list->head = list->head->next;
list->head->prev = NULL;
}
free(temp);
list->size--;
printf("Deleted %d from head\n", data);
return data;
}
// Delete from tail
int deleteFromTail(DoublyLinkedList *list) {
if (isEmpty(list)) {
printf("List is empty! Cannot delete\n");
return -1;
}
Node *temp = list->tail;
int data = temp->data;
if (list->head == list->tail) {
list->head = NULL;
list->tail = NULL;
} else {
list->tail = list->tail->prev;
list->tail->next = NULL;
}
free(temp);
list->size--;
printf("Deleted %d from tail\n", data);
return data;
}
// Delete by value (first occurrence)
bool deleteByValue(DoublyLinkedList *list, int value) {
if (isEmpty(list)) {
printf("List is empty!\n");
return false;
}
Node *current = list->head;
// Search for the value
while (current != NULL && current->data != value) {
current = current->next;
}
if (current == NULL) {
printf("Value %d not found in list\n", value);
return false;
}
// Found the node to delete
if (current == list->head) {
deleteFromHead(list);
} else if (current == list->tail) {
deleteFromTail(list);
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
list->size--;
printf("Deleted %d from list\n", value);
}
return true;
}
// Delete at specific position
bool deleteAtPosition(DoublyLinkedList *list, int position) {
if (position < 0 || position >= list->size) {
printf("Invalid position! Valid positions: 0 to %d\n", list->size - 1);
return false;
}
if (position == 0) {
deleteFromHead(list);
return true;
}
if (position == list->size - 1) {
deleteFromTail(list);
return true;
}
// Traverse to the node
Node *current = list->head;
for (int i = 0; i < position; i++) {
current = current->next;
}
current->prev->next = current->next;
current->next->prev = current->prev;
int data = current->data;
free(current);
list->size--;
printf("Deleted %d from position %d\n", data, position);
return true;
}
// Delete all nodes with a given value
int deleteAllByValue(DoublyLinkedList *list, int value) {
if (isEmpty(list)) return 0;
int count = 0;
Node *current = list->head;
while (current != NULL) {
Node *next = current->next;
if (current->data == value) {
if (current == list->head) {
deleteFromHead(list);
} else if (current == list->tail) {
deleteFromTail(list);
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
list->size--;
}
count++;
}
current = next;
}
printf("Deleted %d occurrences of %d\n", count, value);
return count;
}
// Clear entire list
void clearList(DoublyLinkedList *list) {
Node *current = list->head;
while (current != NULL) {
Node *temp = current;
current = current->next;
free(temp);
}
list->head = NULL;
list->tail = NULL;
list->size = 0;
printf("List cleared\n");
}

Traversal Operations

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// TRAVERSAL OPERATIONS
// ============================================================
// Forward traversal
void displayForward(DoublyLinkedList *list) {
if (isEmpty(list)) {
printf("List is empty\n");
return;
}
printf("Forward traversal (head to tail): ");
Node *current = list->head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf(" (size: %d)\n", list->size);
}
// Backward traversal
void displayBackward(DoublyLinkedList *list) {
if (isEmpty(list)) {
printf("List is empty\n");
return;
}
printf("Backward traversal (tail to head): ");
Node *current = list->tail;
while (current != NULL) {
printf("%d ", current->data);
current = current->prev;
}
printf(" (size: %d)\n", list->size);
}
// Display with details (shows links)
void displayDetailed(DoublyLinkedList *list) {
if (isEmpty(list)) {
printf("List is empty\n");
return;
}
printf("Detailed view (prev <- data -> next):\n");
Node *current = list->head;
while (current != NULL) {
printf("  [");
if (current->prev != NULL)
printf("%d", current->prev->data);
else
printf("NULL");
printf(" <- %d -> ", current->data);
if (current->next != NULL)
printf("%d", current->next->data);
else
printf("NULL");
printf("]\n");
current = current->next;
}
}
// Find node by value (returns first occurrence)
Node* findNode(DoublyLinkedList *list, int value) {
Node *current = list->head;
while (current != NULL) {
if (current->data == value) {
printf("Found %d at address %p\n", value, (void*)current);
return current;
}
current = current->next;
}
printf("Value %d not found\n", value);
return NULL;
}
// Find node by index
Node* getNodeAtIndex(DoublyLinkedList *list, int index) {
if (index < 0 || index >= list->size) {
printf("Index out of bounds\n");
return NULL;
}
// Optimize by choosing direction
if (index < list->size / 2) {
// Start from head
Node *current = list->head;
for (int i = 0; i < index; i++) {
current = current->next;
}
return current;
} else {
// Start from tail (faster for indices near end)
Node *current = list->tail;
for (int i = list->size - 1; i > index; i--) {
current = current->prev;
}
return current;
}
}
// Get first node
Node* getFirst(DoublyLinkedList *list) {
return list->head;
}
// Get last node
Node* getLast(DoublyLinkedList *list) {
return list->tail;
}
// Get next node (given current)
Node* getNext(Node *current) {
return (current != NULL) ? current->next : NULL;
}
// Get previous node (given current)
Node* getPrev(Node *current) {
return (current != NULL) ? current->prev : NULL;
}

Search and Update Operations

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// SEARCH AND UPDATE OPERATIONS
// ============================================================
// Search for value (returns index)
int searchValue(DoublyLinkedList *list, int value) {
Node *current = list->head;
int index = 0;
while (current != NULL) {
if (current->data == value) {
printf("Value %d found at index %d\n", value, index);
return index;
}
current = current->next;
index++;
}
printf("Value %d not found\n", value);
return -1;
}
// Search from both ends simultaneously (optimized)
int searchOptimized(DoublyLinkedList *list, int value) {
if (isEmpty(list)) return -1;
Node *forward = list->head;
Node *backward = list->tail;
int forwardIdx = 0;
int backwardIdx = list->size - 1;
while (forwardIdx <= backwardIdx) {
if (forward->data == value) {
printf("Found %d at index %d (from start)\n", value, forwardIdx);
return forwardIdx;
}
if (backward->data == value) {
printf("Found %d at index %d (from end)\n", value, backwardIdx);
return backwardIdx;
}
forward = forward->next;
backward = backward->prev;
forwardIdx++;
backwardIdx--;
}
printf("Value %d not found\n", value);
return -1;
}
// Count occurrences of a value
int countOccurrences(DoublyLinkedList *list, int value) {
int count = 0;
Node *current = list->head;
while (current != NULL) {
if (current->data == value) {
count++;
}
current = current->next;
}
return count;
}
// Update node value
bool updateNode(DoublyLinkedList *list, int oldValue, int newValue) {
Node *node = findNode(list, oldValue);
if (node) {
node->data = newValue;
printf("Updated node value from %d to %d\n", oldValue, newValue);
return true;
}
return false;
}
// Update all occurrences
int updateAll(DoublyLinkedList *list, int oldValue, int newValue) {
int count = 0;
Node *current = list->head;
while (current != NULL) {
if (current->data == oldValue) {
current->data = newValue;
count++;
}
current = current->next;
}
printf("Updated %d occurrences from %d to %d\n", count, oldValue, newValue);
return count;
}

Utility and Helper Functions

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// UTILITY FUNCTIONS
// ============================================================
// Reverse the list (iterative)
void reverseList(DoublyLinkedList *list) {
if (isEmpty(list) || list->size == 1) return;
Node *current = list->head;
Node *temp = NULL;
// Swap next and prev for all nodes
while (current != NULL) {
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;  // Move to next (which was prev)
}
// Swap head and tail
temp = list->head;
list->head = list->tail;
list->tail = temp;
printf("List reversed\n");
}
// Create a copy of the list
DoublyLinkedList* copyList(DoublyLinkedList *list) {
DoublyLinkedList *newList = createList();
if (newList == NULL) return NULL;
Node *current = list->head;
while (current != NULL) {
insertAtTail(newList, current->data);
current = current->next;
}
printf("List copied\n");
return newList;
}
// Concatenate two lists (append second to first)
void concatenate(DoublyLinkedList *list1, DoublyLinkedList *list2) {
if (isEmpty(list2)) return;
if (isEmpty(list1)) {
list1->head = list2->head;
list1->tail = list2->tail;
} else {
list1->tail->next = list2->head;
list2->head->prev = list1->tail;
list1->tail = list2->tail;
}
list1->size += list2->size;
// Important: list2 nodes are now part of list1
// Set list2 pointers to NULL to avoid double free later
list2->head = NULL;
list2->tail = NULL;
list2->size = 0;
printf("Lists concatenated\n");
}
// Split list at given position
DoublyLinkedList* splitAt(DoublyLinkedList *list, int position) {
if (position < 0 || position >= list->size) {
printf("Invalid split position\n");
return NULL;
}
if (position == list->size - 1) {
// Split at end - second list empty
return createList();
}
Node *splitNode = getNodeAtIndex(list, position);
Node *nextNode = splitNode->next;
// Create new list for second half
DoublyLinkedList *newList = createList();
newList->head = nextNode;
newList->tail = list->tail;
newList->size = list->size - position - 1;
// Update original list
splitNode->next = NULL;
list->tail = splitNode;
list->size = position + 1;
// Update new list's prev pointers
if (nextNode) {
nextNode->prev = NULL;
}
printf("List split at position %d\n", position);
return newList;
}
// Remove duplicates (keep first occurrence)
void removeDuplicates(DoublyLinkedList *list) {
if (list->size <= 1) return;
Node *outer = list->head;
while (outer != NULL && outer->next != NULL) {
Node *inner = outer->next;
while (inner != NULL) {
Node *next = inner->next;
if (inner->data == outer->data) {
// Remove duplicate
inner->prev->next = inner->next;
if (inner->next) {
inner->next->prev = inner->prev;
}
if (inner == list->tail) {
list->tail = inner->prev;
}
free(inner);
list->size--;
}
inner = next;
}
outer = outer->next;
}
printf("Duplicates removed\n");
}
// Sort list (bubble sort - example only, use merge sort for large lists)
void sortList(DoublyLinkedList *list) {
if (list->size <= 1) return;
bool swapped;
Node *current;
Node *last = NULL;
do {
swapped = false;
current = list->head;
while (current->next != last) {
if (current->data > current->next->data) {
// Swap data
int temp = current->data;
current->data = current->next->data;
current->next->data = temp;
swapped = true;
}
current = current->next;
}
last = current;
} while (swapped);
printf("List sorted\n");
}
// Merge two sorted lists
DoublyLinkedList* mergeSorted(DoublyLinkedList *list1, DoublyLinkedList *list2) {
DoublyLinkedList *merged = createList();
Node *p1 = list1->head;
Node *p2 = list2->head;
while (p1 != NULL && p2 != NULL) {
if (p1->data <= p2->data) {
insertAtTail(merged, p1->data);
p1 = p1->next;
} else {
insertAtTail(merged, p2->data);
p2 = p2->next;
}
}
// Add remaining elements
while (p1 != NULL) {
insertAtTail(merged, p1->data);
p1 = p1->next;
}
while (p2 != NULL) {
insertAtTail(merged, p2->data);
p2 = p2->next;
}
printf("Lists merged\n");
return merged;
}

Advanced Operations

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// ============================================================
// ADVANCED OPERATIONS
// ============================================================
// Rotate left by k positions
void rotateLeft(DoublyLinkedList *list, int k) {
if (isEmpty(list) || k <= 0 || k >= list->size) return;
k = k % list->size;
if (k == 0) return;
Node *newHead = getNodeAtIndex(list, k);
Node *newTail = newHead->prev;
// Rearrange pointers
list->tail->next = list->head;
list->head->prev = list->tail;
list->head = newHead;
list->tail = newTail;
list->head->prev = NULL;
list->tail->next = NULL;
printf("List rotated left by %d positions\n", k);
}
// Rotate right by k positions
void rotateRight(DoublyLinkedList *list, int k) {
if (isEmpty(list) || k <= 0 || k >= list->size) return;
k = k % list->size;
if (k == 0) return;
rotateLeft(list, list->size - k);
}
// Check if list is palindrome
bool isPalindrome(DoublyLinkedList *list) {
if (list->size <= 1) return true;
Node *left = list->head;
Node *right = list->tail;
while (left != right && left->prev != right) {
if (left->data != right->data) {
return false;
}
left = left->next;
right = right->prev;
}
return true;
}
// Swap two nodes by value (not data)
void swapNodes(DoublyLinkedList *list, int value1, int value2) {
if (value1 == value2) return;
Node *node1 = findNode(list, value1);
Node *node2 = findNode(list, value2);
if (node1 == NULL || node2 == NULL) return;
// Swap data (simpler than swapping pointers)
int temp = node1->data;
node1->data = node2->data;
node2->data = temp;
printf("Swapped %d and %d\n", value1, value2);
}
// Create a loop for testing (for detection algorithms)
void createLoop(DoublyLinkedList *list, int pos) {
if (pos < 0 || pos >= list->size) return;
Node *loopNode = getNodeAtIndex(list, pos);
list->tail->next = loopNode;  // Create loop
printf("Loop created at position %d\n", pos);
}
// Detect if list has a loop (Floyd's cycle detection)
bool hasLoop(DoublyLinkedList *list) {
if (isEmpty(list)) return false;
Node *slow = list->head;
Node *fast = list->head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
// Find middle node
Node* findMiddle(DoublyLinkedList *list) {
if (isEmpty(list)) return NULL;
Node *slow = list->head;
Node *fast = list->head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}

Complete Working Example

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
// Include all the functions defined above
// (In practice, you'd split into header and source files)
int main() {
printf("========================================\n");
printf("    DOUBLY LINKED LIST DEMONSTRATION\n");
printf("========================================\n\n");
// Create a new list
DoublyLinkedList *list = createList();
// Test insertion operations
printf("--- Insertion Operations ---\n");
insertAtHead(list, 10);
insertAtHead(list, 20);
insertAtTail(list, 30);
insertAtTail(list, 40);
insertAtPosition(list, 25, 2);
displayForward(list);
displayBackward(list);
printf("\n--- More Insertions ---\n");
insertSorted(list, 15);
insertSorted(list, 35);
insertSorted(list, 5);
displayForward(list);
printf("\n--- Detailed View ---\n");
displayDetailed(list);
printf("\n--- Deletion Operations ---\n");
deleteFromHead(list);
deleteFromTail(list);
deleteByValue(list, 25);
displayForward(list);
printf("\n--- Search Operations ---\n");
searchValue(list, 30);
searchOptimized(list, 15);
Node *found = findNode(list, 30);
if (found) {
printf("Node found with data: %d\n", found->data);
}
printf("\n--- Get by Index ---\n");
Node *node = getNodeAtIndex(list, 2);
if (node) {
printf("Node at index 2: %d\n", node->data);
}
printf("\n--- Update Operations ---\n");
updateNode(list, 15, 16);
displayForward(list);
printf("\n--- Reverse List ---\n");
reverseList(list);
displayForward(list);
printf("\n--- Sort List ---\n");
sortList(list);
displayForward(list);
printf("\n--- Remove Duplicates ---\n");
insertAtTail(list, 30);
insertAtTail(list, 30);
displayForward(list);
removeDuplicates(list);
displayForward(list);
printf("\n--- Palindrome Check ---\n");
DoublyLinkedList *palList = createList();
insertAtTail(palList, 1);
insertAtTail(palList, 2);
insertAtTail(palList, 3);
insertAtTail(palList, 2);
insertAtTail(palList, 1);
displayForward(palList);
printf("Is palindrome? %s\n", isPalindrome(palList) ? "Yes" : "No");
printf("\n--- Rotate Operations ---\n");
displayForward(list);
rotateLeft(list, 2);
displayForward(list);
rotateRight(list, 1);
displayForward(list);
printf("\n--- Split Operation ---\n");
DoublyLinkedList *secondHalf = splitAt(list, 2);
printf("First list: ");
displayForward(list);
printf("Second list: ");
displayForward(secondHalf);
printf("\n--- Merge Operation ---\n");
DoublyLinkedList *merged = mergeSorted(list, secondHalf);
displayForward(merged);
printf("\n--- Middle Node ---\n");
Node *middle = findMiddle(merged);
if (middle) {
printf("Middle node data: %d\n", middle->data);
}
printf("\n--- Clear Lists ---\n");
clearList(merged);
clearList(palList);
free(merged);
free(palList);
free(list);
free(secondHalf);
printf("\nAll lists cleared. Program completed.\n");
return 0;
}

Memory Management and Cleanup

#include <stdio.h>
#include <stdlib.h>
// ============================================================
// MEMORY MANAGEMENT
// ============================================================
// Free entire list
void freeList(DoublyLinkedList **list) {
if (list == NULL || *list == NULL) return;
Node *current = (*list)->head;
while (current != NULL) {
Node *temp = current;
current = current->next;
free(temp);
}
free(*list);
*list = NULL;
printf("List freed from memory\n");
}
// Safe function to check if node belongs to list
bool nodeBelongsToList(DoublyLinkedList *list, Node *node) {
Node *current = list->head;
while (current != NULL) {
if (current == node) return true;
current = current->next;
}
return false;
}
// Remove a range of nodes
void removeRange(DoublyLinkedList *list, int start, int end) {
if (start < 0 || end >= list->size || start > end) {
printf("Invalid range\n");
return;
}
Node *startNode = getNodeAtIndex(list, start);
Node *endNode = getNodeAtIndex(list, end);
Node *prevNode = startNode->prev;
Node *nextNode = endNode->next;
// Update connections
if (prevNode) {
prevNode->next = nextNode;
} else {
list->head = nextNode;
}
if (nextNode) {
nextNode->prev = prevNode;
} else {
list->tail = prevNode;
}
// Free the removed nodes
Node *current = startNode;
while (current != nextNode) {
Node *temp = current;
current = current->next;
free(temp);
list->size--;
}
printf("Removed nodes from %d to %d\n", start, end);
}

Performance Analysis

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// ============================================================
// PERFORMANCE ANALYSIS
// ============================================================
void performanceTest() {
const int NUM_OPERATIONS = 100000;
clock_t start, end;
printf("=== Performance Analysis ===\n\n");
DoublyLinkedList *list = createList();
// Test insertion at head
start = clock();
for (int i = 0; i < NUM_OPERATIONS; i++) {
insertAtHead(list, i);
}
end = clock();
printf("Insert %d at head: %.3f seconds\n", 
NUM_OPERATIONS, (double)(end - start) / CLOCKS_PER_SEC);
// Test insertion at tail
clearList(list);
start = clock();
for (int i = 0; i < NUM_OPERATIONS; i++) {
insertAtTail(list, i);
}
end = clock();
printf("Insert %d at tail: %.3f seconds\n", 
NUM_OPERATIONS, (double)(end - start) / CLOCKS_PER_SEC);
// Test traversal
start = clock();
Node *current = list->head;
while (current != NULL) {
current = current->next;
}
end = clock();
printf("Forward traversal: %.3f seconds\n", 
(double)(end - start) / CLOCKS_PER_SEC);
// Test reverse traversal
start = clock();
current = list->tail;
while (current != NULL) {
current = current->prev;
}
end = clock();
printf("Reverse traversal: %.3f seconds\n", 
(double)(end - start) / CLOCKS_PER_SEC);
// Test search (optimized)
start = clock();
for (int i = 0; i < 1000; i++) {
int randomIndex = rand() % NUM_OPERATIONS;
Node *node = getNodeAtIndex(list, randomIndex);
}
end = clock();
printf("1000 random accesses: %.3f seconds\n", 
(double)(end - start) / CLOCKS_PER_SEC);
freeList(&list);
printf("\nComplexity Analysis:\n");
printf("  Insert at head/tail: O(1)\n");
printf("  Insert at position:  O(n)\n");
printf("  Delete from head/tail: O(1)\n");
printf("  Delete by value:     O(n)\n");
printf("  Search by value:     O(n)\n");
printf("  Access by index:     O(n)\n");
printf("  Traversal:           O(n)\n");
printf("  Reverse traversal:   O(n) (with prev pointers)\n");
}
int main() {
performanceTest();
return 0;
}

Comparison with Singly Linked List

#include <stdio.h>
#include <stdlib.h>
// ============================================================
// COMPARISON WITH SINGLY LINKED LIST
// ============================================================
void printComparison() {
printf("=== Singly vs Doubly Linked List ===\n\n");
printf("Singly Linked List:\n");
printf("  + Less memory per node (one pointer)\n");
printf("  + Simpler implementation\n");
printf("  - Can only traverse forward\n");
printf("  - Need previous node to delete current\n");
printf("  - O(n) to find previous node\n\n");
printf("Doubly Linked List:\n");
printf("  + Can traverse both directions\n");
printf("  + Delete node with only its pointer\n");
printf("  + Insert before a node easily\n");
printf("  + Reverse traversal is O(n)\n");
printf("  - More memory per node (two pointers)\n");
printf("  - More pointer updates for operations\n");
printf("  - Slightly slower due to extra pointer maintenance\n\n");
printf("Memory comparison (assuming 64-bit system):\n");
printf("  Singly node: data(4) + next(8) = 12 bytes + padding ≈ 16 bytes\n");
printf("  Doubly node: data(4) + next(8) + prev(8) = 20 bytes + padding ≈ 24 bytes\n");
printf("  Doubly uses about 50%% more memory per node\n");
}
int main() {
printComparison();
return 0;
}

Summary Table of Operations

Conclusion

Doubly linked lists are versatile data structures that excel in scenarios requiring bidirectional traversal and frequent insertions/deletions. Key advantages over singly linked lists include:

1. Bidirectional Navigation: Traverse in both directions with equal ease
2. Efficient Deletion: Remove any node without needing the previous node reference
3. Deque Operations: O(1) operations at both ends
4. Flexible Insertions: Insert before or after any node in O(1) with node reference

However, these benefits come with trade-offs:

• Memory Overhead: Approximately 50% more memory per node
• Complexity: More pointer updates during operations
• Implementation Difficulty: Slightly more complex to implement correctly

Common applications include:

• Browser History: Forward/back navigation
• Music Playlists: Next/previous track functionality
• Undo/Redo Features: Track operations in both directions
• LRU Cache Implementation: Efficient cache eviction policies
• Deque Data Structure: Double-ended queue implementations

Mastering doubly linked lists in C provides a foundation for understanding more complex data structures and their memory management implications. The bidirectional nature makes them invaluable in systems where navigation in both directions is required.