Introduction to Linked Lists

A linked list is a data structure in C that consists of a sequence of elements, each containing a data part and a reference (link) to the next element in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations, which allows for efficient insertion and deletion of elements.

Components of a Linked List

A linked list is composed of two main components:

  • Node: Each node contains two parts: data and a pointer to the next node.
  • Head: The head is the first node in the linked list. It serves as the entry point to the list. If the list is empty, the head is set to NULL.

Structure of a Node

A node in a linked list is typically defined as a structure in C. Here’s how a node can be represented in C: 

    #include <stdio.h>

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

In this example, struct Node contains two members: data (which stores the value of the node) and next (a pointer to the next node in the list).

Types of Linked Lists

  • Singular Linked List: Each node points to the next node. The last node points to NULL, indicating the end of the list.
  • Doubly Linked List: Each node has two pointers: one pointing to the next node and one pointing to the previous node.
  • Circular Linked List: The last node in the list points back to the head node, forming a circle.

Operations on Linked Lists

Common operations that can be performed on a linked list include insertion, deletion, traversal, and searching.

1. Insertion into a Linked List

Inserting a new node into a linked list can be done in several ways: inserting at the beginning, at the end, or at a specific position.

Inserting at the Beginning

To insert a node at the beginning, we create a new node, set its next pointer to the current head, and then update the head to point to the new node. 

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

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

    // Function to insert at the beginning
    void insertAtBeginning(struct Node** head, int newData) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = newData;
        newNode->next = *head;
        *head = newNode;
    }

    // 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");
    }

    int main() {
        struct Node* head = NULL;
        
        insertAtBeginning(&head, 10);
        insertAtBeginning(&head, 20);
        insertAtBeginning(&head, 30);

        printList(head);  // Output: 30 -> 20 -> 10 -> NULL
        
        return 0;
    }

In this example, the function insertAtBeginning inserts a new node at the beginning of the list. The new node becomes the head of the list.

2. Deletion from a Linked List

Deleting a node from a linked list can be done in various ways, such as deleting the first node, the last node, or a specific node.

Deleting the First Node

To delete the first node, we update the head to point to the next node, effectively removing the first node from the list. 

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

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

    // Function to delete the first node
    void deleteFirstNode(struct Node** head) {
        if (*head == NULL) {
            printf("List is empty\n");
            return;
        }
        struct Node* temp = *head;
        *head = (*head)->next;
        free(temp);
    }

    // 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");
    }

    int main() {
        struct Node* head = NULL;
        
        insertAtBeginning(&head, 10);
        insertAtBeginning(&head, 20);
        insertAtBeginning(&head, 30);
        
        printf("Original List:\n");
        printList(head);  // Output: 30 -> 20 -> 10 -> NULL

        deleteFirstNode(&head);
        
        printf("List after deletion:\n");
        printList(head);  // Output: 20 -> 10 -> NULL
        
        return 0;
    }

In this example, the function deleteFirstNode deletes the first node from the linked list. After deletion, the new head points to the second node.

3. Traversing a Linked List

Traversing a linked list involves visiting each node in the list, starting from the head and following the next pointers until reaching the end (NULL). 

    #include <stdio.h>

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

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

    int main() {
        struct Node* head = NULL;
        printList(head);  // Output: NULL

        return 0;
    }

In this example, the printList function traverses the linked list and prints each node's data until the end of the list (NULL).

Advantages of Linked Lists

  • Dynamic Size: Unlike arrays, linked lists can grow or shrink in size dynamically as elements are added or removed.
  • Efficient Insertions and Deletions: Linked lists allow efficient insertion and deletion of elements, especially when working with large datasets.
  • Memory Efficiency: Linked lists do not require contiguous memory locations, making them more memory-efficient for certain applications.

Disadvantages of Linked Lists

  • Memory Overhead: Each node in a linked list requires additional memory for the pointer (link), which increases memory usage.
  • Access Time: Linked lists have slower access times for random elements compared to arrays, as you must traverse the list to find an element.

Conclusion

Linked lists are a powerful and flexible data structure in C that allow efficient insertion and deletion of elements. By understanding the structure of a linked list and how to perform basic operations like insertion, deletion, and traversal, you can efficiently work with dynamic data in your programs.





Advertisement