Linked List in C

A linked list is a linear data structure that does not store elements in contiguous memory locations, the elements in the linked list are linked using pointers. It is a collection of nodes in which each node stores data and a pointer that links to the next node to form a sequence of nodes.

In this article, we will learn about the linked list, its types, representation of the linked list in C, and also the basic and efficient operations that can be performed on a linked list as well as its applications.

Types of Linked List in C

Following are the types of linked list in C:

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Circular Doubly Linked List
5. Header Linked List

Here, we will discuss about the singly linked list. To learn more about linked list refer: Introduction to Linked List – Data Structure and Algorithm Tutorials

What is Singly linked list in C?

A linked list or singly linked list is a non-primitive, linear data structure that is made up of a group of nodes in which each node has two parts: the first is data, and the second is a pointer. The pointer part of the linked list holds the address of the next node and the last node points to null to indicate the end of the linked list. This allows dynamically increasing or decreasing the length of the linked list at run-time, which means it is dynamic in nature.

Representation of a Linked List in C

A linked list is represented as a pointer to the first node where each node contains:

• Data: Here the actual information is stored.
• Next: Pointer that links to the next node.

Linked List

Implementation of Linked List in C

To implement a singly linked list in C, we first need to define a node structure that consists of two parts: data and the pointer to the next node. Let’s see how to create a new node.

Define a Node in Singly Linked List in C

Node-Singly Linked List

To define a node in a singly linked list we use the below node structure:

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

Basic Operations on C Linked List

Following basic operations can be performed on a singly-linked List:

1. Insertion

Insertion operation can be performed in the following three ways:

• Insertion at the beginning of linked list
• Insertion at the end of linked list
• Insertion at specific position in linked list

a. Insertion at the Beginning of Linked List

Insertion at the Beginning- Singly Linked List

To insert a node at the beginning of a singly linked list, first create a new node and make the new node to be the first node by following the below approach:

Approach:

• Set the next pointer of the new node to head (newNode -> next = head).
• Remove the head from original node and update the new node as the head.

b. Insertion at the End of Linked List

Insertion at the End – Singly Linked List

To insert a node at the end of a singly linked list, traverse the list until the end, and the last node’s next should be pointing at the new node. Follow the below approach:

Approach:

• Start traversing the list until the last node.
• Update the last node’s next pointer from null to pointing to new node.
• Point new nodes’s next pointer to null.

c. Insertion at Specific Position in Linked List

Insertion at Specific Position- Singly Linked List

To insert a node at a specific position in a linked list, first create a new node and then follow the below approach:

Approach:

• First, check if the given position for insertion is 0 or if the list is empty:
  • Use the insertion at beginning approach only.
• If the given position is not the beginning position:
  • Initialize a new pointer temp to the head of the list.
  • Start traversing the list using temp pointer until you reach the node just before the desired position
• Insert the newNode at the specified position:
  • Set next pointer of new Node to temp->next.
  • Update temp->next to new node.

2. Deletion

Similar to insertion, deletion operation can also be performed in three ways:

• Deletion at the beginning of linked list
• Deletion at the end of linked list
• Deletion at Specific Position in linked list

a. Deletion at the Beginning of the Linked List

Deletion at Beginning-Singly Linked list

To delete a node at the beginning of linked list, simply update the head pointer and point it on second node from beginning by following the below approach to achieve this:

Approach:

• First, check if the given linked list is empty or not:
• If the linked list is empty, there is nothing to delete simply return.
• If the linked list is not empty do the following:
  • First store the head in a temp variable.
  • Update the head and point it to second node from beginning.
  • Delete the node pointed by temp.

b. Deletion at the End of the Linked List

Deletion at the end- Singly linked list

To delete a node at the end of a singly linked list, traverse the list until the second last node, and update its next pointer to point to NULL.

Approach:

• Start traversing the list until the second last node.
• Update the second last node’s next pointer to null.

c. Deletion at a Specific Position in Doubly Linked List

Deletion at Specific Position- Singly Linked List

To delete a node from a specific position in a singly linked list, follow the below approach:

Approach:

• First, check if the list is empty:
  • return null.
• If the node to be deleted is the first (head) node:
  • Use deletion at the beginning approach only.
• Otherwise :
  • Start traversing the list using temp pointer until you reach the node just before the desired position call it prevNode.
  • Set the next pointer of the prevNode to prevNode->next->next.
  • delete the node to be deleted.

3. Traversal

Linked list traversal means iterating over the each node of the list and performing the desired operations. To traverse a linked list and print its data, follow the below approach.

Approach:

• Initialize a temporary pointer temp and copy head of list into it.
• Using a while loop traverse through the list.
• Move the temp pointer to temp->next in each iteration until temp reaches at the end(null).
• Keep printing the data of the current node during each iteration.

C Program to Implement Linked List

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

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

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

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

// Function to insert a node at the end
void insertAtEnd(struct Node** head, int data) {
    struct Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Function to delete a node with a given key
void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;
    
    // If head node itself holds the key
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    
    // Search for the key
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    // If key was not present in list
    if (temp == NULL) return;
    
    // Unlink the node from linked list
    prev->next = temp->next;
    free(temp);
}

// Function to search for a node with a given key
int search(struct Node* head, int key) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return 1; // Key found
        }
        current = current->next;
    }
    return 0; // Key not found
}

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

// Driver Code
int main() {
    struct Node* head = NULL;
    
    // Insertion
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtBeginning(&head, 5);
    printf("Linked List after insertions: ");
    traverse(head);
    
    // Deletion
    deleteNode(&head, 20);
    printf("Linked List after deletion of 20: ");
    traverse(head);
    
    // Searching
    int key = 10;
    if (search(head, key)) {
        printf("Element %d is found in the linked list.\n", key);
    } else {
        printf("Element %d is not found in the linked list.\n", key);
    }
    
    // Traversal
    printf("Final Linked List: ");
    traverse(head);
    
    return 0;
}

Linked List after insertions: 5 -> 10 -> 20 -> 30 -> NULL
Linked List after deletion of 20: 5 -> 10 -> 30 -> NULL
Element 10 is found in the linked list.
Final Linked List: 5 -> 10 -> 30 -> NULL

Advantages of a Linked List

• Linked list is dynamic data structure it has memory allocation and de-allocation, which means that memory is only used when needed and not earlier in order to avoid waste.
• In linked list items are arranged in a linear fashion, new items can be inserted or removed as and when needed without affecting other items on the list, which makes these processes efficient.
• Memory is utilized effectively since nodes are created on-demand, which means that memory is not pre-allocated when the system has less load.
• Several linear data structures, like stacks and queues, can be implemented with the help of linked lists.

Disadvantages of a Linked List

• In a linked list whenever we want to find the element with position n, all the other elements must be visited first, and this could take quite a lot of time.
• In a linked list, there is more memory needed than there is with an array because each node contains some pointer information.
• An operation that involves accessing elements of a linked list is not as simple as that in an array since elements of a linked list do not have indices that would help you jump to a given position directly.
• Reversing a linked list involves more than one level of pointer arrows in a singly linked list is not feasible or efficient.

Applications of Linked Lists

The following are the applications of linked list:

• Linked list are commonly used to implement stacks and queues.
• It can be used to implement graphs, with the adjacent vertices stored in the nodes of the linked list.
• It can be used in dynamic memory allocation.
• It is used for representing sparse matrices.
• It can be used to store and manipulate polynomials.
• Linked list is used in operating systems to manage task scheduling.
• It is also used in compilers to build a symbol table.

Frequently Asked Questions on Linked List

How is the Linked List Different From an Array?

Unlike arrays, linked list elements are not stored at contiguous locations. The elements are linked using pointers.

What are the Types of Linked Lists?

There are following types of linked list: singly linked lists, doubly linked lists, and circular linked lists, circular doubly linked list, header linked list.

How to Reverse a Linked List?

A linked list can be reversed by changing the next pointers of each node to start pointing to the previous node instead.

How to Detect a Loop in a Linked List?

Loop in a linked list can be detected using Floyd’s Cycle-Finding Algorithm, also known as the tortoise and the hare algorithm.

How to Find the Middle of a Linked List?

The middle of a linked list can be found using the two-pointer technique.

How to Implement a Stack Using a Linked List?

A stack can be implemented using a linked list where the top of the stack is represented by the head node of the linked list.