Linked List

A linked list is a linear data structure consisting of a sequence of elements, where each element is a separate object called a node. Each node contains data and a reference (pointer) to the next node in the sequence. Linked lists offer dynamic memory allocation and flexibility compared to arrays, as they can grow and shrink in size dynamically.

Types of Linked Lists

1. Singly Linked List:

   • Each node contains data and a pointer to the next node.
   • The last node points to NULL, indicating the end of the list.

2. Doubly Linked List:

   • Each node contains data, a pointer to the next node, and a pointer to the previous node.
   • Allows traversal in both forward and backward directions.

3. Circular Linked List:

   • Similar to singly or doubly linked list, but the last node points back to the first node, forming a circular structure.

Implementation

Linked lists are implemented using structures (or classes in object-oriented programming) to define the nodes and pointers.

1. Singly Linked List Implementation:

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

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = value;
        newNode->next = NULL;
    }
    return newNode;
}

// Function to insert a node at the beginning of the linked list
void insertAtBeginning(Node** headRef, int value) {
    Node* newNode = createNode(value);
    if (newNode != NULL) {
        newNode->next = *headRef;
        *headRef = newNode;
    }
}
// Other operations like insertAtEnd, insertAfter, deleteNode, etc., can be implemented similarly.

2. Doubly Linked List Implementation:

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

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode != NULL) {
        newNode->data = value;
        newNode->next = NULL;
        newNode->prev = NULL;
    }
    return newNode;
}

// Function to insert a node at the beginning of the linked list
void insertAtBeginning(Node** headRef, int value) {
    Node* newNode = createNode(value);
    if (newNode != NULL) {
        newNode->next = *headRef;
        if (*headRef != NULL)
            (*headRef)->prev = newNode;
        *headRef = newNode;
    }
}
// Other operations like insertAtEnd, insertAfter, deleteNode, etc., can be implemented similarly.

Operations

Common operations performed on linked lists include:

• Insertion: Adding a new node to the list.
• Deletion: Removing a node from the list.
• Traversal: Iterating through the list to access each node's data.
• Search: Finding a specific value in the list.

Advantages of Linked Lists

• Dynamic size: Linked lists can grow or shrink in size dynamically.
• Efficient insertion and deletion: Insertion and deletion operations are faster compared to arrays.
• Flexibility: Linked lists can be easily modified and reorganized.

Disadvantages of Linked Lists

• Inefficient random access: Accessing elements by index is slower compared to arrays.
• Extra memory overhead: Each node in the linked list requires additional memory for storing pointers.

Applications of Linked Lists

• Dynamic memory allocation: Managing memory dynamically in languages like C.
• Implementation of other data structures: Linked lists are used to implement stacks, queues, and hash tables.
• File systems: Managing file systems with hierarchical structures.
• Polynomial manipulation: Representing polynomials in algebraic calculations.

Examples of Linked List Usage

• Implementing stacks and queues using singly or doubly linked lists.
• Memory management in programming languages.
• Representing sparse matrices.
• Music playlist management in media players.