Table of contents
1.
Introduction
2.
How to Construct a Singly Linked List in C
2.1.
Defining the Node Structure
2.2.
Creating a New Node
2.3.
Adding Nodes to the List
2.4.
Insertion of a node
2.5.
Create a new node with the given data.
3.
Deletion of a node
4.
Traversal in a Singly Linked List
5.
Code for Implementing a Singly Linked List in C
5.1.
C
6.
Frequently Asked Questions
6.1.
What is the time complexity of inserting a node at the end of a singly linked list?
6.2.
Can singly linked lists be used for storing non-integer data types?
6.3.
How does deleting a node affect the performance of a singly linked list?
7.
Conclusion
Last Updated: Jun 11, 2024
Easy

Singly Linked List in C

Author Ravi Khorwal
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A singly linked list is a basic data structure in C programming. It is a collection of nodes where each node contains data & a pointer to the next node. This structure allows for dynamic memory usage and efficient insertions and deletions. Singly linked lists are useful for representing sequences of elements, such as lists or stacks.

Singly Linked List in C

In this article, we will learn how to construct a singly linked list in C, which will include creating nodes, inserting & deleting nodes, & traversing the list. 

How to Construct a Singly Linked List in C

A singly linked list in C is built using a series of nodes linked together through pointers. Each node typically contains at least two parts: data and a pointer to the next node. Now, let's learn how to construct a basic singly linked list. We will start from defining the node structure. 

Defining the Node Structure

First, we define a structure to represent each node in the list. This structure will include the data and a pointer to the next node.

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node* next;
} Node;

Creating a New Node

To add data to our list, we need to create new nodes. A function can be used to allocate memory for a new node and initialize it with data.

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Error creating a new node.\n");
        exit(0);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}


This function creates a new node with the provided data and sets the next pointer to NULL, indicating that the node does not yet link to any other node.

Adding Nodes to the List

We can start our list by creating a head pointer when we create the first node. Subsequent nodes can be added using various strategies, such as at the front of the list or at the end.

void insertAtFront(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}
void insertAtEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}


insertAtFront adds a new node at the beginning of the list, changing the head of the list to the new node. insertAtEnd traverses the list to find the last node and adds the new node after it.

The syntax for creating a node:

To create a node in a singly linked list, we use the following syntax:

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


Here, struct Node defines the structure of a node. Each node contains two fields:
 

  • data: An integer value that stores the data of the node.
     
  • next: A pointer to the next node in the list.
     

To create a new node, we allocate memory using the malloc() function & assign values to its data & next fields:

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;


In this code :

  • (struct Node*)malloc(sizeof(struct Node)) allocates memory for a new node using malloc().
     
  • newNode->data = value; assigns the specified value to the data field of the new node.
     
  • newNode->next = NULL; sets the next pointer of the new node to NULL, indicating that it is the last node in the list.
     

By using this syntax, we can create nodes & build a singly linked list by connecting them together using the next pointers.

Insertion of a node

There are three ways to insert a node into a singly linked list:

  1. Insertion at the beginning
     
  2. Insertion at the end
     
  3. Insertion at a specific position
     

To insert a node at the beginning of the list, we follow these steps:

  • Create a new node with the given data.
     
  • Set the next pointer of the new node to the current head of the list.
     
  • Update the head of the list to point to the new node.
     

Here's the code for inserting a node at the beginning:

void insertAtBeginning(struct Node** head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = *head;
    *head = newNode;
}


To insert a node at the end of the list, we follow these steps:

  • Create a new node with the given data.
     
  • Traverse the list to reach the last node.
     
  • Set the next pointer of the last node to the new node.
     

Here's the code for inserting a node at the end:

void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}


To insert a node at a specific position, we follow these steps:

Create a new node with the given data.

  • Traverse the list to reach the node just before the desired position.
     
  • Set the next pointer of the new node to the next node of the current node.
     
  • Update the next pointer of the current node to the new node.
     

Here's the code for inserting a node at a specific position:

void insertAtPosition(struct Node** head, int value, int position) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    if (position == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Invalid position\n");
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

Deletion of a node

Deleting a node from a singly linked list involves removing the node from the list & freeing the memory allocated to it. There are three ways to delete a node:

  1. Deletion at the beginning
     
  2. Deletion at the end
     
  3. Deletion at a specific position
     

To delete a node at the beginning of the list, we follow these steps:

  • Check if the list is empty. If it is, return.
     
  • Update the head of the list to point to the next node.
     
  • Free the memory of the deleted node.
     

Here's the code for deleting a node at the beginning:

void deleteAtBeginning(struct Node** head) {
    if (*head == NULL) {
        return;
    }
    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}


To delete a node at the end of the list, we follow these steps:

  • Check if the list is empty. If it is, return.
     
  • Traverse the list to reach the second-to-last node.
     
  • Set the next pointer of the second-to-last node to NULL.
     
  • Free the memory of the deleted node.
     

Here's the code for deleting a node at the end:

void deleteAtEnd(struct Node** head) {
    if (*head == NULL) {
        return;
    }
    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }
    struct Node* temp = *head;
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    free(temp->next);
    temp->next = NULL;
}


To delete a node at a specific position, we follow these steps:

  • Check if the list is empty or if the position is invalid. If so, return.
     
  • If the position is 1, update the head of the list to point to the next node & free the memory of the deleted node.
     
  • Traverse the list to reach the node just before the desired position.
     
  • Update the next pointer of the current node to skip the node to be deleted.
     
  • Free the memory of the deleted node.
     

Here's the code for deleting a node at a specific position:

void deleteAtPosition(struct Node** head, int position) {
    if (*head == NULL) {
        return;
    }
    if (position == 1) {
        struct Node* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    struct Node* temp = *head;
    for (int i = 1; i < position - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL || temp->next == NULL) {
        printf("Invalid position\n");
        return;
    }
    struct Node* nodeToDelete = temp->next;
    temp->next = temp->next->next;
    free(nodeToDelete);
}

Traversal in a Singly Linked List

Traversing a singly linked list means visiting each node in the list & performing some operation on the data stored in the nodes. Since each node contains a pointer to the next node, we can traverse the list by starting from the head & following the next pointers until we reach the end of the list (i.e., when the next pointer becomes NULL).

Here's the code for traversing a singly linked list & printing the data of each node:

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


In this code:

  1. We create a temporary pointer temp & initialize it to the head of the list.
     
  2. We start a loop that continues until temp becomes NULL, indicating the end of the list.
     
  3. Inside the loop, we print the data of the current node using printf().
     
  4. We update temp to point to the next node by assigning temp->next to temp.
     
  5. After the loop ends, we print a newline character to move to the next line.


By calling the printList() function & passing the head of the list as an argument, we can traverse the entire list & print the data of each node.

Note : Traversal is a very important operation in linked lists as it allows us to access & process the data stored in the nodes. We can perform various operations while traversing the list, such as searching for a specific element, updating the data of nodes, or applying some computation on the node values.

Code for Implementing a Singly Linked List in C

Till here, we have covered all the different component of singly linked list, now we will apply all the concepts here and create one complete implementation of singly linked list : 

  • C

C

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

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

void insertAtBeginning(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}

void insertAtEnd(struct Node** head, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;

if (*head == NULL) {
*head = newNode;
return;
}

struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

void insertAtPosition(struct Node** head, int value, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;

if (position == 1) {
newNode->next = *head;
*head = newNode;
return;
}

struct Node* temp = *head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}

if (temp == NULL) {
printf("Invalid position\n");
return;
}

newNode->next = temp->next;
temp->next = newNode;
}

void deleteAtBeginning(struct Node** head) {
if (*head == NULL) {
return;
}

struct Node* temp = *head;
*head = (*head)->next;
free(temp);
}

void deleteAtEnd(struct Node** head) {
if (*head == NULL) {
return;
}

if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}

struct Node* temp = *head;
while (temp->next->next != NULL) {
temp = temp->next;
}

free(temp->next);
temp->next = NULL;
}

void deleteAtPosition(struct Node** head, int position) {
if (*head == NULL) {
return;
}

if (position == 1) {
struct Node* temp = *head;
*head = (*head)->next;
free(temp);
return;
}

struct Node* temp = *head;
for (int i = 1; i < position - 1 && temp != NULL; i++) {
temp = temp->next;
}

if (temp == NULL || temp->next == NULL) {
printf("Invalid position\n");
return;
}

struct Node* nodeToDelete = temp->next;
temp->next = temp->next->next;
free(nodeToDelete);
}

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

int main() {
struct Node* head = NULL;

insertAtEnd(&head, 10);
insertAtBeginning(&head, 5);
insertAtEnd(&head, 15);
insertAtPosition(&head, 12, 3);

printf("Linked List: ");
printList(head);

deleteAtPosition(&head, 2);
deleteAtBeginning(&head);

printf("Linked List after deletion: ");
printList(head);

return 0;
}
You can also try this code with Online C Compiler
Run Code

Output

Linked List: 5 10 12 15 
Linked List after deletion: 12 15 


In this code:

  1. We define the Node structure with data & next fields.
     
  2. We implement the insertion functions: insertAtBeginning(), insertAtEnd(), & insertAtPosition().
     
  3. We implement the deletion functions: deleteAtBeginning(), deleteAtEnd(), & deleteAtPosition().
     
  4. We implement the printList() function to traverse & print the elements of the linked list.
     
  5. In the main() function, we create an empty linked list & perform insertion & deletion operations using the implemented functions.
     
  6. We print the linked list before & after the deletion operations to see the changes.

Frequently Asked Questions

What is the time complexity of inserting a node at the end of a singly linked list?

The time complexity is O(n), as it requires traversing the entire list to find the last node before insertion.

Can singly linked lists be used for storing non-integer data types?

Yes, singly linked lists can store any data type, including structures, by adjusting the data type in the node definition.

How does deleting a node affect the performance of a singly linked list?

Deleting a node does not generally affect the performance significantly. However, finding the node to delete requires O(n) time as it may involve scanning the entire list.

Conclusion

In this article, we learned about the very important concept of singly linked lists in C. We discussed about the structure of a node, which consists of a data field & a pointer to the next node. We saw the construction of a singly linked list & the various operations that can be performed on it, including insertion, deletion, & traversal. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry.

Live masterclass