Linked List

    A linked list is a user-defined data structure, which is a collection of nodes, and each node points to another node. Linked lists store elements in a sequential manner, and each node points to its successor node. They are often used in place of the array because some operations of the linked list have less time complexity as compared to an array. Some important terminologies we use in a linked list are:

    • Node
    • Next
    • Linked list

    Node: A node in a linked list contains elements and the next pointer.

    Next: Next is a pointer, which we assign inside the node so it can point to the next node.

    Linked List: The linked list is a collection of sequential nodes.

    Linked List Representation

    In the linked list, each node is linked with another node, and each node contains a next pointer, which usually points to the address of the next node, except the last node.

    • The first node in the linked list is known as the head node.
    • Each node contains some data value and a next pointer.
    • The next pointer holds the address of the next node.
    • The next pointer of the last node contains a Null value.

    Types of Linked Lists

    There are 3 main types of linked lists:

    • Simple linked list
    • Doubly linked list
    • Circular linked list

    Simple Linked List

    In a simple linked list, each node contains some data value and the address of the next sequential node in the next pointer. Each node contains only one pointer variable, so we can only traverse forward.

    Simple Linked List Implementation Using C programming language:

    #include<stdio.h>
    #include<stdlib.h>
    struct node
      {
      int data;
      struct node *next;
    };
    void display(struct node* head)
    {
          struct node *temp = head;
          printf("\n\nElements Presesnt in the linked List are \n");
          while(temp != NULL)
          {
       printf("%d --->",temp->data);
       temp = temp->next;
          }
    }
    void InsertAtMiddle(struct node *head, int position, int value) {
        struct node *temp = head;
        struct node *newNode;
        newNode = malloc(sizeof(struct node));
        newNode->data = value; 
        int i;
        for(i=2; inext != NULL) {
            temp = temp->next;
            }
        }
        newNode->next = temp->next;
        temp->next = newNode;
    }
    void InsertAtBeginning(struct node** headRef, int value) {
        struct node* head = *headRef;
        struct node *newNode;
        newNode = malloc(sizeof(struct node));
        newNode->data = value;
        newNode->next = head;
        head = newNode;
        *headRef = head;
    }
    void InsertAtEnd(struct node* head, int value){
        struct node *newNode;
        newNode = malloc(sizeof(struct node));
        newNode->data = value;
        newNode->next = NULL;
        struct node *temp = head;
        while(temp->next != NULL)
        {
              temp = temp->next;
        }
        temp->next = newNode;
    }
    void DeleteFromDeginning(struct node** headRef){
        struct node* head =  *headRef;
        head = head->next;
        *headRef = head;
    }
    void deleteFromEnd(struct node* head){
        struct node* temp = head;
        while(temp->next->next!=NULL)
        {
            temp = temp->next;
        }
        temp->next = NULL;
    }
    void DeleteFromMiddle(struct node* head, int position){
        struct node* temp = head;
        int i;
        for(i=2; inext != NULL) {
        temp = temp->next;
        }
    }
    temp->next = temp->next->next;
    }

    Doubly Linked List

    In the doubly linked list , each node contains two pointers, except the head node; one pointer points to the next node, and the second pointer points to the previous node. In the doubly linked list, we can traverse back and forth direction.

    Circular Linked List

    A circular linked list is similar to a simple linked list, but here, the last node of the list points to the head of the node instead of Null. In the circular linked list, the next pointer of the last node contains the address of the first node, which is the head node.

    Operations on Linked List

    Here are some basic operations we can perform on a linked list:

    • Insertion
    • Deletion
    • Traverse
    • Search
    • Sorting

    1. Insertion

    In the insertion operation, we add new nodes or elements to the present linked list. The insertion operation itself is divided into 3 parts:

    • Insert at the beginning of a linked list
    • Insert in the middle of a liked list
    • Insert at the last of a liked list.

    2. Deletion

    In deletion, we go through each node of the list and try to delete the target element by removing its pointer variable. In deletion operation, we assign the target element's next pointer value to its previous node's next pointer.

    3. Traverse

    The traverse operation refers to the process of visiting and inspecting each node in the list sequentially. It involves moving through the linked list from the beginning (head node) to the end, examining or performing operations on each node along the way.

    4. Search

    The search operation begins at the head node of the linked list. The search operation involves finding a specific element within the list. Think of a linked list as a chain of connected nodes, where each node contains a piece of data and a reference to the next node in the sequence.

    5. Sorting

    Sorting refers to the process of arranging the elements or nodes within the list in a specific order, often ascending or descending, based on a few criteria, like numerical or alphabetical values.

    Conclusion

    In conclusion, linked lists are fundamental data structures in computer science that offer flexible storage for various applications. They help in multiple fields in various areas, such as memory management, symbol tables, and graph algorithms.

    We hope this tutorial helps you understand the key concepts of the linked list.

    People are also reading: