Linked List Data Structure

A Linked List is a linear data structure where elements, called nodes, are connected using pointers. Each node consists of two parts:

1. Data: Contains the actual value.
2. Pointer: Stores the address of the next node in the sequence.

Unlike arrays, linked lists do not store elements in contiguous memory locations, making them dynamic and flexible in size.

Types of Linked Lists

1. Singly Linked List:
   • Each node points to the next node.
   • The last node points to NULL.
   • Traversal is unidirectional.

   Example:

   [Data | Next] -> [Data | Next] -> [Data | NULL]
   

2. Doubly Linked List:
   • Each node has two pointers: one to the next node and one to the previous node.
   • Allows bidirectional traversal.

   Example:

   NULL <- [Prev | Data | Next] <-> [Prev | Data | Next] -> NULL
   

3. Circular Linked List:
   • The last node points back to the first node, forming a circle.
   • Can be singly or doubly linked.

   Example (Singly Circular):

   [Data | Next] -> [Data | Next] -> [Data | Next] -> (points back to first node)
   

Advantages of Linked Lists

• Dynamic Size: Unlike arrays, linked lists can grow or shrink as needed.
• Efficient Insertion/Deletion: Adding or removing elements is easier compared to arrays, especially in the middle of the list.

Disadvantages of Linked Lists

• Memory Overhead: Requires extra memory for pointers.
• Sequential Access: Cannot access elements directly; must traverse the list.
• Slower Search: Searching takes O(n)O(n) time compared to O(1)O(1) for arrays (random access).

Basic Operations

1. Insertion:
   • At Beginning: Add a node at the start of the list.
   • At End: Traverse to the last node and add a new node.
   • At a Position: Traverse to the position and insert the new node.
2. Deletion:
   • At Beginning: Remove the first node and update the head pointer.
   • At End: Traverse to the second-to-last node and set its pointer to NULL.
   • At a Position: Traverse to the position and adjust pointers to bypass the node.
3. Traversal:
   • Visit each node in the list, starting from the head, until the end (or return to the head in circular lists).
4. Search:
   • Traverse the list to find a specific value.

Applications of Linked Lists

1. Dynamic Memory Allocation: Used in stacks, queues, and heaps.
2. Graph Representations: Represent adjacency lists in graph algorithms.
3. File Systems: Maintain file directory structures.
4. Real-Time Applications: Implement undo functionality in text editors.

Example: Singly Linked List in C

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

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

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

// Main function
int main() {
    struct Node* head = NULL;
    struct Node* second = NULL;
    struct Node* third = NULL;

    // Allocate nodes
    head = (struct Node*)malloc(sizeof(struct Node));
    second = (struct Node*)malloc(sizeof(struct Node));
    third = (struct Node*)malloc(sizeof(struct Node));

    head->data = 1; 
    head->next = second;

    second->data = 2; 
    second->next = third;

    third->data = 3; 
    third->next = NULL;

    printList(head);
    return 0;
}

Output:

1 -> 2 -> 3 -> NULL

Comparison with Arrays

Linked lists are versatile and form the backbone of many advanced data structures like stacks, queues, and hash tables. Understanding their structure and operations is fundamental for efficient algorithm design.