First, what is a linked list? A linked list is a linear data structure that is made up of a sequence of nodes.
A singly linked list is a data structure in which each node points to the next node. The head of a singly linked list points to the address of the first element of the list. It is known as a singly linked list as it has only one link pointing to its next node.
Representation of a singly linked list
A singly linked list is represented by a node consisting of data and a pointer that points to the address of the next node:
/**
* struct node_s - singly linked list
* @data: The data *
* @next: points to the next node
*
* Description: singly linked list node structure
*/
typedef struct node_s
{
int data;
struct node_s *next;
} node_t;
Operations on a singly linked list
The following operations can be performed on a singly linked list:
Insertion - Inserts an element in a list.
Deletion − Deletes an element in a list.
Traversal − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.
Let's look at how to perform the above operations in a singly linked list:
Insertion operation
By performing this operation we can add elements to a singly linked list.
Insertion at the beginning
In this operation, we are adding an element at the beginning of the list:
#include <stdlib.h>
#include <stdio.h>
/**
* struct node_s - singly linked list
* @data: The data *
* @next: points to the next node
*
* Description: singly linked list node structure
*/
typedef struct node_s
{
int data;
struct node_s *next;
} node_t;
/**
* insert_at_begin - adds a new node at the beginning of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_begin(node_t **head, int data)
{
node_t *new;
if (head == NULL)
return (NULL);
/* create a new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* add data to the new node */
new->data = data;
/* point head to address of new node */
new->next = *head;
*head = new;
return (new);
}
/**
* print_list - prints all the elements of a list_t list
* @h: list
*
* Return: nothing
*/
void print_list(node_t *h)
{
while (h != NULL)
{
printf("%d ", h->data);
h = h->next;
printf("\n");
}
}
/**
* main - check the code
*
* Return: Always 0.
*/
int main(void)
{
node_t *head;
head = NULL;
insert_at_begin(&head, 1);
insert_at_begin(&head, 2);
insert_at_begin(&head, 3);
print_list(head);
return (0);
}
Output:
3
2
1
Insert at the end
In this operation, we are adding an element at the end of the list:
#include <stdlib.h>
#include <stdio.h>
/**
* struct node_s - singly linked list
* @data: The data *
* @next: points to the next node
*
* Description: singly linked list node structure
*/
typedef struct node_s
{
int data;
struct node_s *next;
} node_t;
/**
* insert_at_begin - adds a new node at the beginning of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_begin(node_t **head, int data)
{
node_t *new;
if (head == NULL)
return (NULL);
/* create a new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* add data to the new node */
new->data = data;
/* point head to address of new node */
new->next = *head;
*head = new;
return (new);
}
/**
* insert_at_end - adds a new node at the end of a ist
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_end(node_t **head, int data)
{
node_t *new, *temp;
/* check if the head pointer is NULL */
if (head == NULL)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node and set its next pointer to NULL */
new->data = data;
new->next = NULL;
/* if the linked list is empty, make the new node the head */
if (*head == NULL)
*head = new;
else
{
temp = *head;
/* traverse the linked list to find the last node */
while (temp->next != NULL)
temp = temp->next;
/* insert the new node at the end */
temp->next = new;
}
/* return a pointer to the newly inserted node */
return (new);
}
/**
* print_list - prints all the elements of a list_t list
* @h: list
*
* Return: nothing
*/
void print_list(node_t *h)
{
while (h != NULL)
{
printf("%d ", h->data);
h = h->next;
printf("\n");
}
}
/**
* main - check the code
*
* Return: Always 0.
*/
int main(void)
{
node_t *head;
head = NULL;
insert_at_begin(&head, 1);
insert_at_begin(&head, 2);
insert_at_begin(&head, 3);
printf("-----------------\n");
insert_at_end(&head, 5);
insert_at_end(&head, 8);
insert_at_end(&head, 13);
print_list(head);
return (0);
}
Output:
3
2
1
-----------------
3
2
1
5
8
13
Insert at a specified position
In this operation, we are adding an element at a specified position of the list:
#include <stdlib.h>
#include <stdio.h>
/**
* struct node_s - singly linked list
* @data: The data *
* @next: points to the next node
*
* Description: singly linked list node structure
*/
typedef struct node_s
{
int data;
struct node_s *next;
} node_t;
/**
* insert_at_begin - adds a new node at the beginning of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_begin(node_t **head, int data)
{
node_t *new;
if (head == NULL)
return (NULL);
/* create a new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* add data to the new node */
new->data = data;
/* point head to address of new node */
new->next = *head;
*head = new;
return (new);
}
/**
* insert_at_end - adds a new node at the end of a ist
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_end(node_t **head, int data)
{
node_t *new, *temp;
/* check if the head pointer is NULL */
if (head == NULL)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node and set its next pointer to NULL */
new->data = data;
new->next = NULL;
/* if the linked list is empty, make the new node the head */
if (*head == NULL)
*head = new;
else
{
temp = *head;
/* traverse the linked list to find the last node */
while (temp->next != NULL)
temp = temp->next;
/* insert the new node at the end */
temp->next = new;
}
/* return a pointer to the newly inserted node */
return (new);
}
/**
* insert_at_index - adds a new node at a specified
* end of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_index(node_t **head, unsigned int idx, int data)
{
unsigned int count = 0, i = 1;
node_t *new, *current;
/* initialize current pointer to point to the head of the list */
current = *head;
/* count the number of nodes in the linked list */
while (current)
{
current = current->next;
count++;
}
/* check if the index is out of bounds */
if (idx > count)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node */
new->data = data;
/* if the index is 0, insert the new node at the beginning of the list */
if (idx == 0)
{
new->next = *head;
*head = new;
return (new);
}
/* reset current pointer to point to the head of the list */
current = *head;
/* traverse the list to find the node before the insertion point */
for (i = 0; i < idx - 1; i++)
current = current->next;
/* insert the new node at the specified index */
new->next = current->next;
current->next = new;
/* return a pointer to the newly inserted node */
return (new);
}
/**
* print_list - prints all the elements of a list_t list
* @h: list
*
* Return: nothing
*/
void print_list(node_t *h)
{
while (h != NULL)
{
printf("%d ", h->data);
h = h->next;
printf("\n");
}
}
/**
* main - check the code
*
* Return: Always 0.
*/
int main(void)
{
node_t *head;
head = NULL;
insert_at_begin(&head, 1);
insert_at_begin(&head, 2);
insert_at_begin(&head, 3);
print_list(head);
printf("-----------------\n");
insert_at_end(&head, 5);
insert_at_end(&head, 8);
insert_at_end(&head, 13);
print_list(head);
printf("-----------------\n");
insert_at_index(&head, 5, 4096);
print_list(head);
return (0);
}
Output:
3
2
1
-----------------
3
2
1
5
8
13
-----------------
3
2
1
5
8
4096
13
Deletion operation
By performing this operation we can remove elements from a singly linked list.
Deletion at the beginning
In this operation, we are removing an element at the beginning of the list:
#include <stdlib.h>
#include <stdio.h>
/**
* struct node_s - singly linked list
* @data: The data *
* @next: points to the next node
*
* Description: singly linked list node structure
*/
typedef struct node_s
{
int data;
struct node_s *next;
} node_t;
/**
* insert_at_begin - adds a new node at the beginning of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_begin(node_t **head, int data)
{
node_t *new;
if (head == NULL)
return (NULL);
/* create a new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* add data to the new node */
new->data = data;
/* point head to address of new node */
new->next = *head;
*head = new;
return (new);
}
/**
* insert_at_end - adds a new node at the end of a ist
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_end(node_t **head, int data)
{
node_t *new, *temp;
/* check if the head pointer is NULL */
if (head == NULL)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node and set its next pointer to NULL */
new->data = data;
new->next = NULL;
/* if the linked list is empty, make the new node the head */
if (*head == NULL)
*head = new;
else
{
temp = *head;
/* traverse the linked list to find the last node */
while (temp->next != NULL)
temp = temp->next;
/* insert the new node at the end */
temp->next = new;
}
/* return a pointer to the newly inserted node */
return (new);
}
/**
* insert_at_index - adds a new node at a specified
* end of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_index(node_t **head, unsigned int idx, int data)
{
unsigned int count = 0, i = 1;
node_t *new, *current;
/* initialize current pointer to point to the head of the list */
current = *head;
/* count the number of nodes in the linked list */
while (current)
{
current = current->next;
count++;
}
/* check if the index is out of bounds */
if (idx > count)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node */
new->data = data;
/* if the index is 0, insert the new node at the beginning of the list */
if (idx == 0)
{
new->next = *head;
*head = new;
return (new);
}
/* reset current pointer to point to the head of the list */
current = *head;
/* traverse the list to find the node before the insertion point */
for (i = 0; i < idx - 1; i++)
current = current->next;
/* insert the new node at the specified index */
new->next = current->next;
current->next = new;
/* return a pointer to the newly inserted node */
return (new);
}
/**
* delete_at_begin - deletes a node at the beginning of a list
* @head: double pointer to head of a list
*
* Return: nothing
*/
void *delete_at_begin(node_t **head)
{
node_t *temp;
/* Check if the head pointer or the list is empty */
if ((*head)->next == NULL)
{
/* If only one node is present, set head to NULL and free the memory */
*head = NULL;
free(temp);
}
/* Store the address of the current head node in temp */
temp = *head;
/* Update the head pointer to point to the next node */
*head = (*head)->next;
/* Free the memory allocated to the previous head node */
free(temp);
}
/**
* print_list - prints all the elements of a list_t list
* @h: list
*
* Return: nothing
*/
void print_list(node_t *h)
{
while (h != NULL)
{
printf("%d ", h->data);
h = h->next;
printf("\n");
}
}
/**
* main - check the code
*
* Return: Always 0.
*/
int main(void)
{
node_t *head;
head = NULL;
insert_at_begin(&head, 1);
insert_at_begin(&head, 2);
insert_at_begin(&head, 3);
print_list(head);
printf("-----------------\n");
insert_at_end(&head, 5);
insert_at_end(&head, 8);
insert_at_end(&head, 13);
print_list(head);
printf("-----------------\n");
insert_at_index(&head, 5, 4096);
print_list(head);
printf("-----------------\n");
delete_at_begin(&head);
delete_at_begin(&head);
delete_at_begin(&head);
print_list(head);
return (0);
}
Output:
3
2
1
-----------------
3
2
1
5
8
13
-----------------
3
2
1
5
8
4096
13
-----------------
5
8
4096
13
Delete at the end
In this operation, we are removing an element at the end of the list:
#include <stdlib.h>
#include <stdio.h>
/**
* struct node_s - singly linked list
* @data: The data *
* @next: points to the next node
*
* Description: singly linked list node structure
*/
typedef struct node_s
{
int data;
struct node_s *next;
} node_t;
/**
* insert_at_begin - adds a new node at the beginning of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_begin(node_t **head, int data)
{
node_t *new;
if (head == NULL)
return (NULL);
/* create a new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* add data to the new node */
new->data = data;
/* point head to address of new node */
new->next = *head;
*head = new;
return (new);
}
/**
* insert_at_end - adds a new node at the end of a ist
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_end(node_t **head, int data)
{
node_t *new, *temp;
/* check if the head pointer is NULL */
if (head == NULL)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node and set its next pointer to NULL */
new->data = data;
new->next = NULL;
/* if the linked list is empty, make the new node the head */
if (*head == NULL)
*head = new;
else
{
temp = *head;
/* traverse the linked list to find the last node */
while (temp->next != NULL)
temp = temp->next;
/* insert the new node at the end */
temp->next = new;
}
/* return a pointer to the newly inserted node */
return (new);
}
/**
* insert_at_index - adds a new node at a specified
* end of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_index(node_t **head, unsigned int idx, int data)
{
unsigned int count = 0, i = 1;
node_t *new, *current;
/* initialize current pointer to point to the head of the list */
current = *head;
/* count the number of nodes in the linked list */
while (current)
{
current = current->next;
count++;
}
/* check if the index is out of bounds */
if (idx > count)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node */
new->data = data;
/* if the index is 0, insert the new node at the beginning of the list */
if (idx == 0)
{
new->next = *head;
*head = new;
return (new);
}
/* reset current pointer to point to the head of the list */
current = *head;
/* traverse the list to find the node before the insertion point */
for (i = 0; i < idx - 1; i++)
current = current->next;
/* insert the new node at the specified index */
new->next = current->next;
current->next = new;
/* return a pointer to the newly inserted node */
return (new);
}
/**
* delete_at_begin - deletes a node at the beginning of a list
* @head: double pointer to head of a list
*
* Return: nothing
*/
void *delete_at_begin(node_t **head)
{
node_t *temp;
/* Check if the head pointer or the list is empty */
if ((*head)->next == NULL)
{
/* If only one node is present, set head to NULL and free the memory */
*head = NULL;
free(temp);
}
/* Store the address of the current head node in temp */
temp = *head;
/* Update the head pointer to point to the next node */
*head = (*head)->next;
/* Free the memory allocated to the previous head node */
free(temp);
}
/**
* delete_at_end - deletes a node at the end of a list
* @head: double pointer to head of a list
*
* Return: nothing
*/
void *delete_at_end(node_t **head)
{
node_t *prev, *temp;
/* check if the head pointer or the list is empty */
if (*head == NULL)
return (NULL);
/* initialize pointers to traverse the list */
prev = NULL;
temp = *head;
/* traverse the list until the last node is reached */
while (temp->next != NULL)
{
prev = temp;
temp = temp->next;
}
/* if the last node is the head node */
if (temp == *head)
*head = NULL;
else
/* Update the previous node's next pointer to NULL */
prev->next = NULL;
/* Free the memory allocated to the last node */
free(temp);
}
/**
* print_list - prints all the elements of a list_t list
* @h: list
*
* Return: nothing
*/
void print_list(node_t *h)
{
while (h != NULL)
{
printf("%d ", h->data);
h = h->next;
printf("\n");
}
}
/**
* main - check the code
*
* Return: Always 0.
*/
int main(void)
{
node_t *head;
head = NULL;
insert_at_begin(&head, 1);
insert_at_begin(&head, 2);
insert_at_begin(&head, 3);
print_list(head);
printf("-----------------\n");
insert_at_end(&head, 5);
insert_at_end(&head, 8);
insert_at_end(&head, 13);
print_list(head);
printf("-----------------\n");
insert_at_index(&head, 5, 4096);
print_list(head);
printf("-----------------\n");
delete_at_begin(&head);
delete_at_begin(&head);
delete_at_begin(&head);
print_list(head);
printf("-----------------\n");
delete_at_end(&head);
delete_at_end(&head);
print_list(head);
return (0);
}
Output:
3
2
1
-----------------
3
2
1
5
8
13
-----------------
3
2
1
5
8
4096
13
-----------------
5
8
4096
13
-----------------
5
8
Delete at a specified position
In this operation, we are removing an element at a specified position of the list:
#include <stdlib.h>
#include <stdio.h>
/**
* struct node_s - singly linked list
* @data: The data *
* @next: points to the next node
*
* Description: singly linked list node structure
*/
typedef struct node_s
{
int data;
struct node_s *next;
} node_t;
/**
* insert_at_begin - adds a new node at the beginning of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_begin(node_t **head, int data)
{
node_t *new;
if (head == NULL)
return (NULL);
/* create a new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* add data to the new node */
new->data = data;
/* point head to address of new node */
new->next = *head;
*head = new;
return (new);
}
/**
* insert_at_end - adds a new node at the end of a ist
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_end(node_t **head, int data)
{
node_t *new, *temp;
/* check if the head pointer is NULL */
if (head == NULL)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node and set its next pointer to NULL */
new->data = data;
new->next = NULL;
/* if the linked list is empty, make the new node the head */
if (*head == NULL)
*head = new;
else
{
temp = *head;
/* traverse the linked list to find the last node */
while (temp->next != NULL)
temp = temp->next;
/* insert the new node at the end */
temp->next = new;
}
/* return a pointer to the newly inserted node */
return (new);
}
/**
* insert_at_index - adds a new node at a specified
* end of a list
* @head: double pointer to head of a list
* @data: data of the list
*
* Return: address of the new element, otherwise NULL
*/
node_t *insert_at_index(node_t **head, unsigned int idx, int data)
{
unsigned int count = 0, i = 1;
node_t *new, *current;
/* initialize current pointer to point to the head of the list */
current = *head;
/* count the number of nodes in the linked list */
while (current)
{
current = current->next;
count++;
}
/* check if the index is out of bounds */
if (idx > count)
return (NULL);
/* allocate memory for the new node */
new = malloc(sizeof(node_t));
if (new == NULL)
return (NULL);
/* assign data to the new node */
new->data = data;
/* if the index is 0, insert the new node at the beginning of the list */
if (idx == 0)
{
new->next = *head;
*head = new;
return (new);
}
/* reset current pointer to point to the head of the list */
current = *head;
/* traverse the list to find the node before the insertion point */
for (i = 0; i < idx - 1; i++)
current = current->next;
/* insert the new node at the specified index */
new->next = current->next;
current->next = new;
/* return a pointer to the newly inserted node */
return (new);
}
/**
* delete_at_begin - deletes a node at the beginning of a list
* @head: double pointer to head of a list
*
* Return: nothing
*/
void *delete_at_begin(node_t **head)
{
node_t *temp;
/* Check if the head pointer or the list is empty */
if ((*head)->next == NULL)
{
/* If only one node is present, set head to NULL and free the memory */
*head = NULL;
free(temp);
}
/* Store the address of the current head node in temp */
temp = *head;
/* Update the head pointer to point to the next node */
*head = (*head)->next;
/* Free the memory allocated to the previous head node */
free(temp);
}
/**
* delete_at_end - deletes a node at the end of a list
* @head: double pointer to head of a list
*
* Return: nothing
*/
void *delete_at_end(node_t **head)
{
node_t *prev, *temp;
/* check if the head pointer or the list is empty */
if (*head == NULL)
return (NULL);
/* initialize pointers to traverse the list */
prev = NULL;
temp = *head;
/* traverse the list until the last node is reached */
while (temp->next != NULL)
{
prev = temp;
temp = temp->next;
}
/* if the last node is the head node */
if (temp == *head)
*head = NULL;
else
/* update the previous node's next pointer to NULL */
prev->next = NULL;
/* free the memory allocated to the last node */
free(temp);
}
/**
* delete_at_idx - deletes a node at a specified postion
* of a list
* @head: double pointer to head of a list
*
* Return: nothing
*/
void *delete_at_idx(node_t **head, unsigned int idx)
{
node_t *temp, *to_delete;
unsigned int i = 0;
/* check if the head pointer or the list is empty */
if (*head == NULL)
return (NULL);
/* special case: If index is 0, delete the head node */
if (idx == 0)
{
to_delete = *head;
*head = (*head)->next;
free(to_delete);
return (NULL);
}
/* traverse the list to find the node before the index to delete */
temp = *head;
while (i < idx - 1 && temp->next != NULL)
{
temp = temp->next;
i++;
}
/* if index is out of bounds or the next node is NULL, return */
if (temp->next == NULL)
return (NULL);
/* store the node to be deleted and update pointers to skip it */
to_delete = temp->next;
temp->next = to_delete->next;
/* free the memory allocated to the deleted node */
free(to_delete);
}
/**
* print_list - prints all the elements of a list_t list
* @h: list
*
* Return: nothing
*/
void print_list(node_t *h)
{
while (h != NULL)
{
printf("%d ", h->data);
h = h->next;
printf("\n");
}
}
/**
* main - check the code
*
* Return: Always 0.
*/
int main(void)
{
node_t *head;
head = NULL;
insert_at_begin(&head, 1);
insert_at_begin(&head, 2);
insert_at_begin(&head, 3);
print_list(head);
printf("-----------------\n");
insert_at_end(&head, 5);
insert_at_end(&head, 8);
insert_at_end(&head, 13);
print_list(head);
printf("-----------------\n");
insert_at_index(&head, 5, 4096);
print_list(head);
printf("-----------------\n");
delete_at_begin(&head);
delete_at_begin(&head);
delete_at_begin(&head);
print_list(head);
printf("-----------------\n");
delete_at_end(&head);
delete_at_end(&head);
print_list(head);
printf("-----------------\n");
delete_at_idx(&head, 1);
print_list(head);
return (0);
}
Traversal operation
Traversing a singly linked list is where you visit each node of a singly linked list until the end is reached. By doing so you can then display the items.
/**
* print_list - prints all the elements of a list_t list
* @h: list
*
* Return: nothing
*/
void print_list(node_t *h)
{
/* traverse the list until the end is reached (NULL) */
while (h != NULL)
{
/* print the data of the current node */
printf("%d ", h->data);
/* move to the next node */
h = h->next;
/* print a newline after printing each node's data */
printf("\n");
}
}
Output:
3
2
1
-----------------
3
2
1
5
8
13
-----------------
3
2
1
5
8
4096
13
-----------------
5
8
4096
13
-----------------
5
8
-----------------
5
Challenge: Try to implement the other operations not implemented in this article and find their time and space complexities.
Happy coding!