Understanding Linked Lists (C Language Implementation)

Understanding Linked Lists (C Language Implementation)

1. Basic Concepts of Linked Lists

Linked List is a dynamic data structure composed of a series of nodes (Node), where each node contains:

1. Data Field: stores the actual data
2. Pointer Field: stores the memory address of the next node

2. Comparison of Linked Lists and Arrays

Characteristics	Array	Linked List
Memory Allocation	Static contiguous memory	Dynamic scattered memory
Size Adjustment	Fixed size	Dynamic expansion/contraction
Insertion/Deletion	O(n) (requires moving elements)	O(1) (just modify pointers)
Random Access	O(1) (direct indexing)	O(n) (needs traversal)

3. Types of Linked Lists

1. Single Linked List: nodes have only one pointer to the successor
2. Doubly Linked List: nodes contain pointers to both predecessor and successor
3. Circular Linked List: the tail node points to the head node forming a loop

4. Implementation of Single Linked List (C Language)

1. Node Definition

typedef struct Node {
    int data;           // Data field
    struct Node* next;  // Pointer field
} Node;

2. Core Operations Implementation

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

// Create a new 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 head
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

// Insert at tail
void insertAtTail(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 node
void deleteNode(Node** head, int data) {
    if (*head == NULL) return;
    
    Node *current = *head, *prev = NULL;
    
    // Delete head node
    if (current != NULL && current->data == data) {
        *head = current->next;
        free(current);
        return;
    }
    
    // Find the node to delete
    while (current != NULL && current->data != data) {
        prev = current;
        current = current->next;
    }
    
    if (current == NULL) return;  // Not found
    
    // Unlink and free memory
    prev->next = current->next;
    free(current);
}

// Traverse the linked list
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// Reverse the linked list
void reverseList(Node** head) {
    Node *prev = NULL, *current = *head, *next = NULL;
    
    while (current != NULL) {
        next = current->next;  // Save next node
        current->next = prev;  // Reverse pointer
        prev = current;        // Move prev
        current = next;        // Move current
    }
    *head = prev;  // Update head pointer
}

// Free the entire linked list
void freeList(Node** head) {
    Node* current = *head;
    Node* next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

3. Main Function Test

int main() {
    Node* head = NULL;
    
    // Insertion test
    insertAtTail(&head, 10);
    insertAtHead(&head, 5);
    insertAtTail(&head, 20);
    insertAtHead(&head, 2);
    
    printf("Original Linked List: ");
    printList(head);  // 2 -> 5 -> 10 -> 20 -> NULL
    
    // Deletion test
    deleteNode(&head, 5);
    printf("After Deletion: ");
    printList(head);  // 2 -> 10 -> 20 -> NULL
    
    // Reversal test
    reverseList(&head);
    printf("After Reversal: ");
    printList(head);  // 20 -> 10 -> 2 -> NULL
    
    // Free memory
    freeList(&head);
    
    return 0;
}

5. Implementation of Doubly Linked List (Key Code)

typedef struct DNode {
    int data;
    struct DNode* prev;
    struct DNode* next;
} DNode;

// Insert in doubly linked list
void insertDNode(DNode** head, int data) {
    DNode* newNode = (DNode*)malloc(sizeof(DNode));
    newNode->data = data;
    newNode->next = *head;
    newNode->prev = NULL;
    
    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}

// Delete from doubly linked list
void deleteDNode(DNode** head, DNode* delNode) {
    if (*head == NULL || delNode == NULL) return;
    
    if (*head == delNode) *head = delNode->next;
    if (delNode->next != NULL) delNode->next->prev = delNode->prev;
    if (delNode->prev != NULL) delNode->prev->next = delNode->next;
    
    free(delNode);
}

6. Applications of Linked Lists

1. Dynamic Memory Management: Memory Allocators
2. Implementing Advanced Data Structures: Stacks, Queues, Hash Tables
3. File Systems: FAT Table Management of Disk Blocks
4. Browser History: Forward/Backward Functionality
5. Music Playlists: Song Order Management

7. Common Interview Questions

1. Detect if a linked list has a cycle (Floyd’s Tortoise and Hare method)
2. Merge two sorted linked lists
3. Find the middle node of a linked list
4. Delete the N-th node from the end
5. Check if a linked list is a palindrome

By mastering these core operations and principles, you will be able to easily tackle programming tasks and interview challenges related to linked lists!