Data Structures in C: Implementing Linked Lists from Scratch

drwxr-xr-x2026-01-135 min0 views

Linked lists are fundamental dynamic data structures that store collections of elements using nodes connected via pointers, offering advantages over arrays including efficient insertion and deletion at any position without shifting elements [web:288]. Unlike arrays with fixed sizes and contiguous memory allocation, linked lists grow and shrink dynamically through runtime memory allocation using malloc and free, making them ideal for scenarios where the data size is unknown or frequently changes [web:289][web:292]. Each node in a linked list contains data and one or more pointers to other nodes, with singly linked lists having a single next pointer and doubly linked lists maintaining both next and previous pointers for bidirectional traversal [web:287].

This comprehensive guide builds linked lists from scratch in C, covering node structure definitions, singly linked list implementation with insertion at beginning, end, and specific positions, deletion operations, traversal techniques, doubly linked list implementation with bidirectional navigation, memory management best practices using malloc and free, and common linked list operations [web:288]. Mastering linked list implementation is essential for understanding advanced data structures, preparing for technical interviews, and building efficient algorithms that require dynamic memory management.

Understanding Linked List Basics

A linked list consists of nodes where each node contains data and a pointer to the next node in the sequence. The first node is called the head, and the last node points to NULL, indicating the end of the list. This structure allows for dynamic sizing and efficient insertions and deletions.

clinked_list_basics.c

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

// Node structure for singly linked list
typedef struct Node {
    int data;              // Data stored in the node
    struct Node* next;     // Pointer to next node
} Node;

int main() {
    printf("=== Linked List Basics ===\n\n");
    
    // Advantages over arrays:
    // 1. Dynamic size - grows/shrinks at runtime
    // 2. Efficient insertion/deletion - O(1) if position known
    // 3. No memory waste from fixed allocation
    // 4. Easy to implement stacks and queues
    
    // Disadvantages:
    // 1. No random access - must traverse from head
    // 2. Extra memory for pointers
    // 3. Not cache-friendly (non-contiguous memory)
    // 4. Reverse traversal difficult (singly linked)
    
    // Visual representation:
    // HEAD -> [data|next] -> [data|next] -> [data|next] -> NULL
    //         Node 1          Node 2          Node 3
    
    // Memory layout (non-contiguous):
    // Array:       [1][2][3][4][5]  (contiguous)
    // Linked List: [1]-->[3]-->[5]-->[2]-->[4]  (scattered in memory)
    
    printf("Linked list nodes can be anywhere in memory,\n");
    printf("connected via pointers rather than adjacency.\n");
    
    return 0;
}

Singly Linked List: Structure and Creation

A singly linked list has nodes with a single pointer to the next node, enabling forward traversal only [web:288]. Creating a linked list requires defining the node structure, allocating memory dynamically for each node using malloc, and linking nodes together through pointer assignments.

csingly_linked_list_creation.c

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

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    // Allocate memory for new node
    Node* newNode = (Node*)malloc(sizeof(Node));
    
    // Check if allocation succeeded
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    
    // Initialize node
    newNode->data = data;
    newNode->next = NULL;
    
    return newNode;
}

// Function to print the list
void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    Node* current = head;
    printf("List: ");
    
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    
    printf("NULL\n");
}

// Function to get list length
int getLength(Node* head) {
    int count = 0;
    Node* current = head;
    
    while (current != NULL) {
        count++;
        current = current->next;
    }
    
    return count;
}

int main() {
    printf("=== Creating a Singly Linked List ===\n\n");
    
    // Create nodes manually
    Node* head = createNode(10);
    Node* second = createNode(20);
    Node* third = createNode(30);
    
    // Link nodes together
    head->next = second;
    second->next = third;
    third->next = NULL;  // Last node points to NULL
    
    // Print the list
    printList(head);
    printf("Length: %d\n\n", getLength(head));
    
    // Memory visualization:
    // head -> [10|*] -> [20|*] -> [30|NULL]
    //         0x1000    0x2000    0x3000  (example addresses)
    
    // Free memory
    free(third);
    free(second);
    free(head);
    
    return 0;
}

Memory Management: Always check if malloc returns NULL before using the allocated memory [web:289]. Failed allocation can crash your program if not handled properly.

Insertion Operations in Singly Linked Lists

Insertion can occur at three positions: beginning (O(1) complexity), end (O(n) without tail pointer), or at a specific position [web:288]. Each insertion type requires different pointer manipulations to maintain list integrity while adding new nodes.

csingly_insertion.c

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert at the beginning - O(1)
void insertAtBeginning(Node** head, int data) {
    Node* newNode = createNode(data);
    
    // Point new node to current head
    newNode->next = *head;
    
    // Update head to point to new node
    *head = newNode;
    
    printf("Inserted %d at beginning\n", data);
}

// Insert at the end - O(n)
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    
    // If list is empty, new node becomes head
    if (*head == NULL) {
        *head = newNode;
        printf("Inserted %d at end (empty list)\n", data);
        return;
    }
    
    // Traverse to the last node
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    // Link last node to new node
    current->next = newNode;
    printf("Inserted %d at end\n", data);
}

// Insert after a specific node - O(1) if node pointer known
void insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL\n");
        return;
    }
    
    Node* newNode = createNode(data);
    
    // Link new node to next node
    newNode->next = prevNode->next;
    
    // Link previous node to new node
    prevNode->next = newNode;
    
    printf("Inserted %d after node\n", data);
}

// Insert at specific position - O(n)
void insertAtPosition(Node** head, int data, int position) {
    if (position < 0) {
        printf("Invalid position\n");
        return;
    }
    
    // If inserting at beginning
    if (position == 0) {
        insertAtBeginning(head, data);
        return;
    }
    
    Node* newNode = createNode(data);
    Node* current = *head;
    
    // Traverse to position - 1
    for (int i = 0; i < position - 1 && current != NULL; i++) {
        current = current->next;
    }
    
    // Check if position is valid
    if (current == NULL) {
        printf("Position out of bounds\n");
        free(newNode);
        return;
    }
    
    // Insert new node
    newNode->next = current->next;
    current->next = newNode;
    
    printf("Inserted %d at position %d\n", data, position);
}

void printList(Node* head) {
    Node* current = head;
    printf("List: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    printf("=== Insertion Operations ===\n\n");
    
    Node* head = NULL;
    
    // Insert at beginning
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
    printList(head);  // 10 -> 20 -> 30 -> NULL
    
    // Insert at end
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    printList(head);  // 10 -> 20 -> 30 -> 40 -> 50 -> NULL
    
    // Insert at position
    insertAtPosition(&head, 25, 2);
    printList(head);  // 10 -> 20 -> 25 -> 30 -> 40 -> 50 -> NULL
    
    // Insert after specific node
    insertAfter(head->next, 22);
    printList(head);  // 10 -> 20 -> 22 -> 25 -> 30 -> 40 -> 50 -> NULL
    
    // Free memory (will implement proper function later)
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
    
    return 0;
}

Pointer to Pointer: Functions that modify the head pointer use Node** (pointer to pointer) [web:288]. This allows the function to change where head points, essential for insertions at the beginning.

Deletion Operations in Singly Linked Lists

Deletion removes nodes from the list and frees their memory to prevent memory leaks [web:288]. Like insertion, deletion can occur at the beginning, end, or a specific position, requiring careful pointer manipulation to maintain list connectivity before freeing memory.

csingly_deletion.c

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) exit(1);
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* current = *head;
    while (current->next != NULL) current = current->next;
    current->next = newNode;
}

// Delete from beginning - O(1)
void deleteFromBeginning(Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    Node* temp = *head;
    *head = (*head)->next;
    
    printf("Deleted %d from beginning\n", temp->data);
    free(temp);
}

// Delete from end - O(n)
void deleteFromEnd(Node** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    // If only one node
    if ((*head)->next == NULL) {
        printf("Deleted %d from end\n", (*head)->data);
        free(*head);
        *head = NULL;
        return;
    }
    
    // Traverse to second-last node
    Node* current = *head;
    while (current->next->next != NULL) {
        current = current->next;
    }
    
    printf("Deleted %d from end\n", current->next->data);
    free(current->next);
    current->next = NULL;
}

// Delete node with specific value - O(n)
void deleteByValue(Node** head, int value) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    Node* temp = *head;
    Node* prev = NULL;
    
    // If head node contains the value
    if (temp != NULL && temp->data == value) {
        *head = temp->next;
        printf("Deleted node with value %d\n", value);
        free(temp);
        return;
    }
    
    // Search for the value
    while (temp != NULL && temp->data != value) {
        prev = temp;
        temp = temp->next;
    }
    
    // Value not found
    if (temp == NULL) {
        printf("Value %d not found\n", value);
        return;
    }
    
    // Unlink node and free memory
    prev->next = temp->next;
    printf("Deleted node with value %d\n", value);
    free(temp);
}

// Delete at specific position - O(n)
void deleteAtPosition(Node** head, int position) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    Node* temp = *head;
    
    // Delete head
    if (position == 0) {
        *head = temp->next;
        printf("Deleted node at position %d (value: %d)\n", position, temp->data);
        free(temp);
        return;
    }
    
    // Find node before position
    for (int i = 0; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    
    // Position out of bounds
    if (temp == NULL || temp->next == NULL) {
        printf("Position out of bounds\n");
        return;
    }
    
    // Unlink node and free
    Node* nodeToDelete = temp->next;
    temp->next = nodeToDelete->next;
    printf("Deleted node at position %d (value: %d)\n", position, nodeToDelete->data);
    free(nodeToDelete);
}

void printList(Node* head) {
    Node* current = head;
    printf("List: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    printf("=== Deletion Operations ===\n\n");
    
    Node* head = NULL;
    
    // Create list: 10 -> 20 -> 30 -> 40 -> 50
    for (int i = 10; i <= 50; i += 10) {
        insertAtEnd(&head, i);
    }
    printList(head);
    printf("\n");
    
    // Delete from beginning
    deleteFromBeginning(&head);
    printList(head);  // 20 -> 30 -> 40 -> 50
    printf("\n");
    
    // Delete from end
    deleteFromEnd(&head);
    printList(head);  // 20 -> 30 -> 40
    printf("\n");
    
    // Delete by value
    deleteByValue(&head, 30);
    printList(head);  // 20 -> 40
    printf("\n");
    
    // Rebuild list
    insertAtEnd(&head, 60);
    insertAtEnd(&head, 80);
    printList(head);  // 20 -> 40 -> 60 -> 80
    printf("\n");
    
    // Delete at position
    deleteAtPosition(&head, 2);
    printList(head);  // 20 -> 40 -> 80
    
    // Free remaining nodes
    while (head != NULL) {
        deleteFromBeginning(&head);
    }
    
    return 0;
}

Memory Leak Prevention: Always free deleted nodes using free() [web:292]. Failing to free memory causes memory leaks that accumulate over the program's lifetime.

Doubly Linked List: Structure and Implementation

Doubly linked lists extend singly linked lists by adding a previous pointer to each node, enabling bidirectional traversal [web:287][web:290]. This additional pointer simplifies certain operations like backward traversal and deletion but requires more memory and careful management of two pointer connections.

cdoubly_linked_list.c

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

// Node structure for doubly linked list
typedef struct DNode {
    int data;
    struct DNode* prev;  // Pointer to previous node
    struct DNode* next;  // Pointer to next node
} DNode;

// Create new node
DNode* createDNode(int data) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// Insert at beginning - O(1)
void insertAtBeginning(DNode** head, int data) {
    DNode* newNode = createDNode(data);
    
    newNode->next = *head;
    newNode->prev = NULL;
    
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    
    *head = newNode;
    printf("Inserted %d at beginning\n", data);
}

// Insert at end - O(n) without tail pointer
void insertAtEnd(DNode** head, int data) {
    DNode* newNode = createDNode(data);
    
    // If list is empty
    if (*head == NULL) {
        *head = newNode;
        printf("Inserted %d at end (empty list)\n", data);
        return;
    }
    
    // Traverse to last node
    DNode* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    // Update pointers
    current->next = newNode;
    newNode->prev = current;
    
    printf("Inserted %d at end\n", data);
}

// Delete from beginning - O(1)
void deleteFromBeginning(DNode** head) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    DNode* temp = *head;
    *head = (*head)->next;
    
    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    
    printf("Deleted %d from beginning\n", temp->data);
    free(temp);
}

// Delete by value - O(n)
void deleteByValue(DNode** head, int value) {
    if (*head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    DNode* current = *head;
    
    // Find the node
    while (current != NULL && current->data != value) {
        current = current->next;
    }
    
    if (current == NULL) {
        printf("Value %d not found\n", value);
        return;
    }
    
    // Update previous node's next pointer
    if (current->prev != NULL) {
        current->prev->next = current->next;
    } else {
        // Deleting head node
        *head = current->next;
    }
    
    // Update next node's prev pointer
    if (current->next != NULL) {
        current->next->prev = current->prev;
    }
    
    printf("Deleted node with value %d\n", value);
    free(current);
}

// Print list forward
void printForward(DNode* head) {
    printf("Forward: NULL <- ");
    DNode* current = head;
    while (current != NULL) {
        printf("%d", current->data);
        if (current->next != NULL) printf(" <-> ");
        current = current->next;
    }
    printf(" -> NULL\n");
}

// Print list backward
void printBackward(DNode* head) {
    if (head == NULL) {
        printf("Backward: NULL\n");
        return;
    }
    
    // Go to last node
    DNode* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    printf("Backward: NULL <- ");
    while (current != NULL) {
        printf("%d", current->data);
        if (current->prev != NULL) printf(" <-> ");
        current = current->prev;
    }
    printf(" -> NULL\n");
}

int main() {
    printf("=== Doubly Linked List ===\n\n");
    
    DNode* head = NULL;
    
    // Insert nodes
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
    insertAtEnd(&head, 40);
    insertAtEnd(&head, 50);
    
    printf("\n");
    printForward(head);
    printBackward(head);
    
    printf("\n");
    deleteFromBeginning(&head);
    printForward(head);
    
    printf("\n");
    deleteByValue(&head, 30);
    printForward(head);
    
    // Free memory
    while (head != NULL) {
        deleteFromBeginning(&head);
    }
    
    return 0;
}

Bidirectional Traversal: Doubly linked lists allow backward traversal without recursion [web:287]. This simplifies operations like reverse printing and makes deletion easier since you have direct access to the previous node.

Common Linked List Operations

Beyond basic insertion and deletion, linked lists support various operations including searching, reversing, finding length, detecting cycles, and merging lists. These operations demonstrate the flexibility and power of linked list data structures.

ccommon_operations.c

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

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) exit(1);
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* current = *head;
    while (current->next != NULL) current = current->next;
    current->next = newNode;
}

// Search for a value - O(n)
int search(Node* head, int value) {
    Node* current = head;
    int position = 0;
    
    while (current != NULL) {
        if (current->data == value) {
            return position;
        }
        current = current->next;
        position++;
    }
    
    return -1;  // Not found
}

// Reverse the list - O(n)
void reverse(Node** head) {
    Node* prev = NULL;
    Node* current = *head;
    Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;  // Save next
        current->next = prev;  // Reverse link
        prev = current;        // Move prev forward
        current = next;        // Move current forward
    }
    
    *head = prev;
}

// Find middle element - O(n) using slow/fast pointers
int findMiddle(Node* head) {
    if (head == NULL) return -1;
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow->data;
}

// Detect cycle using Floyd's algorithm - O(n)
int hasCycle(Node* head) {
    if (head == NULL) return 0;
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return 1;  // Cycle detected
        }
    }
    
    return 0;  // No cycle
}

// Get nth node from end - O(n)
int getNthFromEnd(Node* head, int n) {
    Node* main = head;
    Node* ref = head;
    
    // Move ref n nodes ahead
    for (int i = 0; i < n; i++) {
        if (ref == NULL) return -1;
        ref = ref->next;
    }
    
    // Move both until ref reaches end
    while (ref != NULL) {
        main = main->next;
        ref = ref->next;
    }
    
    return main->data;
}

// Remove duplicates from sorted list - O(n)
void removeDuplicates(Node* head) {
    Node* current = head;
    Node* next;
    
    while (current != NULL && current->next != NULL) {
        if (current->data == current->next->data) {
            next = current->next->next;
            free(current->next);
            current->next = next;
        } else {
            current = current->next;
        }
    }
}

void printList(Node* head) {
    Node* current = head;
    printf("List: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    printf("=== Common Linked List Operations ===\n\n");
    
    Node* head = NULL;
    
    // Create list: 10 -> 20 -> 30 -> 40 -> 50
    for (int i = 10; i <= 50; i += 10) {
        insertAtEnd(&head, i);
    }
    printList(head);
    
    // Search
    int value = 30;
    int pos = search(head, value);
    printf("\nValue %d found at position: %d\n", value, pos);
    
    // Find middle
    printf("Middle element: %d\n", findMiddle(head));
    
    // Nth from end
    printf("2nd element from end: %d\n", getNthFromEnd(head, 2));
    
    // Reverse list
    printf("\nReversing list...\n");
    reverse(&head);
    printList(head);
    
    // Test with duplicates
    printf("\nTesting duplicate removal:\n");
    Node* head2 = NULL;
    insertAtEnd(&head2, 10);
    insertAtEnd(&head2, 10);
    insertAtEnd(&head2, 20);
    insertAtEnd(&head2, 30);
    insertAtEnd(&head2, 30);
    printList(head2);
    removeDuplicates(head2);
    printf("After removing duplicates: ");
    printList(head2);
    
    // Free memory
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
    while (head2 != NULL) {
        temp = head2;
        head2 = head2->next;
        free(temp);
    }
    
    return 0;
}

Memory Management Best Practices

Proper memory management is critical when working with linked lists to avoid memory leaks and dangling pointers. Following established patterns ensures your linked list implementation is robust and reliable.

cmemory_management.c

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

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

// Complete memory cleanup function
void freeList(Node** head) {
    Node* current = *head;
    Node* next;
    
    while (current != NULL) {
        next = current->next;  // Save next before freeing
        free(current);         // Free current node
        current = next;        // Move to next
    }
    
    *head = NULL;  // Set head to NULL after freeing
    printf("All nodes freed\n");
}

// Safe node creation with error handling
Node* createNodeSafe(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    
    if (newNode == NULL) {
        fprintf(stderr, "Error: Memory allocation failed\n");
        return NULL;
    }
    
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert with memory check
int insertAtEndSafe(Node** head, int data) {
    Node* newNode = createNodeSafe(data);
    if (newNode == NULL) {
        return 0;  // Allocation failed
    }
    
    if (*head == NULL) {
        *head = newNode;
        return 1;
    }
    
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return 1;  // Success
}

int main() {
    printf("=== Memory Management Best Practices ===\n\n");
    
    Node* head = NULL;
    
    // Best practices:
    
    // 1. Always check malloc return value
    printf("1. Always check malloc return\n");
    Node* node = createNodeSafe(10);
    if (node == NULL) {
        printf("   Failed to allocate memory\n");
        return 1;
    }
    free(node);
    
    // 2. Free all allocated nodes
    printf("\n2. Free all allocated nodes\n");
    for (int i = 1; i <= 5; i++) {
        if (!insertAtEndSafe(&head, i * 10)) {
            printf("   Insertion failed\n");
            freeList(&head);
            return 1;
        }
    }
    printf("   Created list with 5 nodes\n");
    freeList(&head);
    
    // 3. Set pointers to NULL after freeing
    printf("\n3. Head is NULL after freeing: %s\n", 
           head == NULL ? "Yes" : "No");
    
    // 4. Don't access freed memory
    printf("\n4. Never access freed memory\n");
    Node* temp = createNodeSafe(100);
    int value = temp->data;  // Access before freeing
    free(temp);
    // printf("%d", temp->data);  // WRONG! Accessing freed memory
    printf("   Saved value before freeing: %d\n", value);
    
    // 5. Handle edge cases
    printf("\n5. Handle edge cases (empty list)\n");
    freeList(&head);  // Safe to call on NULL list
    
    // Common pitfalls to avoid:
    printf("\n=== Common Pitfalls ===\n");
    printf("1. Memory leak: Not freeing all nodes\n");
    printf("2. Dangling pointer: Using pointer after free\n");
    printf("3. Double free: Freeing same node twice\n");
    printf("4. Lost reference: Losing head pointer\n");
    printf("5. Null dereference: Not checking NULL\n");
    
    return 0;
}

Critical Practice: Always free all allocated nodes before program termination [web:292]. Use a cleanup function that traverses the list, freeing each node and setting head to NULL.

Comparison: Arrays vs Linked Lists

Understanding when to use linked lists versus arrays is essential for effective data structure selection. Each has distinct advantages and trade-offs in terms of memory, performance, and use cases.

Feature	Array	Linked List
Memory Allocation	Contiguous, fixed size	Non-contiguous, dynamic [web:292]
Random Access	O(1) direct indexing	O(n) must traverse
Insertion at Beginning	O(n) shift all elements	O(1) update head [web:288]
Deletion from Middle	O(n) shift elements	O(1) if pointer known
Memory Overhead	No extra space	Extra space for pointers
Cache Performance	Better (contiguous)	Worse (scattered)
Size Flexibility	Fixed at creation	Dynamic growth/shrink

Best Practices and Tips

Following established best practices ensures your linked list implementations are correct, efficient, and maintainable. These guidelines prevent common errors and improve code quality.

Always validate malloc: Check if malloc returns NULL before dereferencing the pointer to prevent crashes [web:289]
Use typedef for cleaner code: Define typedef struct Node for more readable type declarations
Maintain tail pointer: Keep track of the last node to make insertions at end O(1) instead of O(n)
Handle empty lists: Always check if head is NULL before operations to avoid null pointer dereferences
Free in reverse order: When freeing nodes, traverse forward but free as you go to avoid losing references
Use helper functions: Create reusable functions for common operations like createNode, printList, and freeList
Double pointer for head changes: Use Node** when functions need to modify the head pointer [web:288]
Consistent naming: Use clear variable names like current, prev, next for traversal pointers
Test edge cases: Verify operations work on empty lists, single-node lists, and boundary conditions
Comment pointer updates: Document which pointers are being updated and why during insertions and deletions

Conclusion

Linked lists are fundamental dynamic data structures built from nodes connected via pointers, each containing data and pointer fields to other nodes, offering O(1) insertion and deletion when position is known compared to arrays requiring O(n) element shifting. Singly linked lists have nodes with a single next pointer enabling forward traversal, while doubly linked lists add a previous pointer for bidirectional navigation at the cost of additional memory and pointer management complexity. Implementation requires careful memory management using malloc for node allocation and free for deallocation to prevent memory leaks, with validation of malloc return values being critical since allocation can fail. Core operations include insertion at beginning requiring O(1) time by updating head, insertion at end taking O(n) without tail pointer, deletion operations that must carefully update pointers before freeing memory, and traversal for searching and processing nodes sequentially.

Common linked list operations extend beyond basic insertion and deletion to include reversing lists by iteratively changing next pointers, finding middle elements using slow and fast pointer technique, detecting cycles with Floyd's algorithm, searching for values requiring O(n) traversal, and removing duplicates from sorted lists. Memory management best practices mandate checking malloc return values before use, freeing all allocated nodes before program termination through cleanup functions, setting pointers to NULL after freeing to avoid dangling references, and never accessing freed memory to prevent undefined behavior. Linked lists excel when insertion and deletion are frequent, size varies dynamically, and random access is not required—unlike arrays which provide O(1) random access but require contiguous memory and expensive element shifting for insertions and deletions. Best practices include using typedef for cleaner syntax, maintaining tail pointers for O(1) end insertions, handling empty list edge cases, using double pointers (Node**) when modifying head, creating helper functions for code reuse, and thoroughly testing boundary conditions. By mastering linked list implementation from scratch—including node structures, memory allocation, pointer manipulation, and proper cleanup—you build foundational knowledge essential for advanced data structures like stacks, queues, trees, and graphs, while developing the low-level programming skills critical for systems programming, embedded development, and technical interview success.