Step-by-Step Guide to Linked List Implementation

Sushil Kumar MishraSushil Kumar Mishra
6 min read

Table of contents

Introduction to Linked Lists

Linked lists are a fundamental data structure in computer science, allowing for efficient insertion and deletion of elements. Unlike arrays, linked lists do not require a contiguous block of memory, making them more flexible for dynamic memory allocation. In this blog, we'll explore the basic operations on a linked list and how to implement them in C.

1. Creating a Linked List

The first step in working with linked lists is creating one. The create_ll function initializes a linked list by dynamically allocating memory for new nodes and linking them together.

struct node *create_ll(struct node *start) {
    struct node *new_node, *ptr;
    int num;
    printf("Insertion !!!\n\n");
    printf("Enter -1 to end! \n");
    printf("Enter the data : \n");
    scanf("%d", &num);
    while (num != -1) {
        new_node = (struct node*)malloc(sizeof(struct node));
        new_node->data = num;
        if (start == NULL) {
            new_node->next = NULL;
            start = new_node;
        } else {
            ptr = start;
            while (ptr->next != NULL) {
                ptr = ptr->next;
            }
            ptr->next = new_node;
            new_node->next = NULL;
        }
        printf("Enter the data : \n");
        scanf("%d", &num);
    }
    return start;
}
  • Explanation: The function prompts the user to enter data, which is stored in the linked list until the user enters -1. Each node is dynamically allocated using malloc, and the nodes are linked together to form the list.

2. Displaying the Linked List

Once the linked list is created, you may want to display its contents. The display function iterates through the list and prints each node's data.

struct node *display(struct node *start) {
    struct node *ptr;
    ptr = start;
    printf("\n");
    printf("Linked List is displayed below :\n");
    while (ptr != NULL) {
        printf("%d\n", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
    return start;
}
  • Explanation: This function starts at the head of the list and traverses through each node, printing the data until it reaches the end.

3. Inserting at the Beginning

To insert a new node at the beginning of the list, the insert_beg function is used.

struct node *insert_beg(struct node *start) {
    struct node *new_node;
    int num;
    printf("Enter the data that you want to insert at the beginning : \n");
    scanf("%d", &num);
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = num;
    new_node->next = start;
    start = new_node;
    return start;
}
  • Explanation: A new node is created, and its next pointer is set to point to the current head of the list. The head of the list is then updated to this new node.

4. Inserting at the End

Inserting a node at the end of the list involves traversing to the last node and linking the new node to the end.

struct node *insert_end(struct node *start) {
    struct node *new_node,*ptr;
    int num;
    printf("Enter the data that you want to insert at the end : \n");
    scanf("%d", &num);
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = num;
    new_node->next = NULL;
    ptr = start;
    while (ptr->next != NULL) {
        ptr = ptr->next;
    }
    ptr->next = new_node;
    return start;
}
  • Explanation: The function iterates through the list until it finds the last node, then links the new node to this node.

5. Inserting Before a Specific Node

To insert a node before a specific value in the list, the insert_before function is used.

struct node *insert_before(struct node *start) {
    struct node *new_node, *pre_ptr, *ptr;
    int num,val;
    printf("Enter the data that you want to insert before a certain value : \n");
    scanf("%d", &num);
    printf("Enter the value before which the node has to be inserted : \n");
    scanf("%d", &val);
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = num;
    ptr = start;
    while(ptr->data != val) {
        pre_ptr = ptr;
        ptr = ptr->next;
    }
    pre_ptr->next = new_node;
    new_node->next = ptr;
    return start;
}
  • Explanation: The function finds the node before which the new node should be inserted, and adjusts the pointers accordingly.

6. Inserting After a Specific Node

Similarly, the insert_after function inserts a new node after a specific value in the list.

struct node *insert_after(struct node *start) {
    struct node *new_node, *pre_ptr, *ptr;
    int num, val;
    printf("Enter the data that you want to insert after a certain value : \n");
    scanf("%d", &num);
    printf("Enter the value after which you want to insert the node : \n");
    scanf("%d", &val);
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = num;
    ptr = start;
    pre_ptr = ptr;
    while(pre_ptr->data != val) {
        pre_ptr = ptr;
        ptr = ptr->next;
    }
    pre_ptr->next = new_node;
    new_node->next = ptr;
    return start;
}
  • Explanation: The function locates the target node and links the new node after it.

7. Deleting the First Node

The del_beg function removes the first node from the list.

struct node *del_beg(struct node *start) {
    struct node *ptr;
    printf("Deletion !!!\n\n");
    ptr = start;
    start = start->next;
    free(ptr);
    return start;
}
  • Explanation: The head of the list is updated to point to the second node, and the memory of the first node is freed.

8. Deleting the Last Node

To delete the last node, the del_end function is used.

struct node *del_end(struct node *start) {
    struct node *ptr, *pre_ptr;
    ptr = start;
    while(ptr->next != NULL) {
        pre_ptr = ptr;
        ptr = ptr->next;
    }
    pre_ptr->next = NULL;
    free(ptr);
    return start;
}
  • Explanation: The function traverses to the second-to-last node, sets its next pointer to NULL, and frees the memory of the last node.

9. Deleting a Specific Node

The del_node function removes a specific node by value.

struct node *del_node(struct node *start) {
    struct node *ptr, *pre_ptr;
    int val;
    printf("Enter the value of the node that has to be deleted : \n");
    scanf("%d", &val);
    ptr = start;
    if (ptr->data == val) {
        start = del_beg(start);
        return start;
    } else {
        while(ptr->data != val) {
            pre_ptr = ptr;
            ptr = ptr->next;
        }
        pre_ptr->next = ptr->next;
        free(ptr);
        return start;
    }
}
  • Explanation: The function finds the node to be deleted and adjusts the pointers of the surrounding nodes before freeing the memory of the target node.

10. Deleting After a Specific Node

The del_after function deletes the node immediately following a specific value.

struct node *del_after(struct node *start) {
    struct node *ptr, *pre_ptr;
    int val;
    printf("Enter the value after which the node has to be deleted : \n");
    scanf("%d", &val);
    ptr = start;
    pre_ptr = ptr;
    while(pre_ptr->data != val) {
        pre_ptr = ptr;
        ptr = ptr->next;
    }
    pre_ptr->next = ptr->next;
    free(ptr);
    return start;
}
  • Explanation: The function locates the target node and deletes the node after it by adjusting pointers and freeing memory.

11. Deleting the Entire Linked List

Finally, the del_ll function deletes the entire linked list.

struct node *del_ll(struct node *start) {
    struct node *ptr;
    if(start != NULL) {
        ptr = start;
        while(ptr != NULL) {
            printf("%d is to be deleted next \n", ptr->data);
            start = del_beg(start);
            ptr = start;
        }
    }
    return start;
}
  • Explanation: The function iteratively deletes each node starting from the head until the entire list is freed.

Conclusion

Linked lists are a versatile data structure that allows for efficient memory usage and dynamic data management. By mastering the implementation and manipulation of linked lists, you're building a strong foundation in data structures. Whether it's inserting, deleting, or traversing through nodes, these fundamental operations are crucial for efficient programming. Keep practicing, and soon you'll be able to handle even more complex data structures with confidence.

"Stay curious, keep learning, and let your code make a difference!"

~ Sushil Kumar Mishra

2
Subscribe to my newsletter

Read articles from Sushil Kumar Mishra directly inside your inbox. Subscribe to the newsletter, and don't miss out.

arraylist#linkedlistsDSAdatastructureinsertion deletionmemory-management

Written by

Sushil Kumar Mishra
Sushil Kumar Mishra