TABLE OF CONTENTS.
Prerequisites.
What is a singly linked list?
Types of linked lists.
Why a linked list?
Representation of a single linked list.
Creating a node of a singly linked list.
Creating a singly linked list.
Conclusion.
Prerequisites.
Before we dive deep into the linked list, we need to have a basic understanding of some topics like:
Arrays.
How to allocate memory using the malloc function.
Pointers.
Structure.
What is a singly linked list?
A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from the head to the last node (tail). Each element in a linked list is called a node. A single node contains data and a pointer to the next node which helps in maintaining the structure of the list.
A list is made up of nodes that consist of two parts:
Data: Contains the actual data.
Pointer: Contains the address of the next node.
Types of linked lists.
There are three types of linked lists:
Singly-linked list: Navigation is forward only.
Doubly linked list: Forward and backward navigation is possible.
Circular linked list: The last element is linked to the first element.
Why a linked list?
Well, some of you might be about why we need a linked list when we already have arrays for storing data. There are some limitations of arrays that can be eliminated by using a linked list.
Deletion and insertion can be achieved very quickly as they do not require shifting elements while using a linked list.
The linked list is dynamic. So, we can change the size according to our requirements.
No memory wastage.
Representation of a singly linked list.
Let's take a simple example, suppose we want to store a list of numbers: 20,65,70,90. for this purpose, we have to create four different nodes because we have four different numbers to store. for simplicity purposes, I have taken these addresses: 1000,2000,3000,4000.
We can see that the first node contains 2000, which is the address of the second node of the list, and we can see that the second node contains the address of the third node of the list, and the third node contains the address of the last node of the list, and the last node contains NULL which means it is not containing any address.
But how can we access the first node of the linked list?
In order to access the first node of the linked list we need a pointer; with the help of a pointer we can access the first node of the linked list, and from the first node, we can access the rest of the list.
Creating a node of a singly linked list.
A self-referential structure is a structure that contains a pointer to a structure of the same type. example
struct abc {
int data1;
char data2;
struct abc *ptr;
};
We will use the self-referential structure for creating a node of the single linked list.
struct node {
int data;
struct node * link;
};
Generally, we could have multiple data but there must be only one pointer.
Creating a node in C.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node * link;
};
int main() {
struct node * head = NULL;
head = (struct node*)malloc(sizeof(struct node));
head -> data = 60;
head -> link = NULL;
printf("%d", head -> data);
return 0;
}
Creating a singly linked list.
We already know how to create a node of the list. our task now is to create three such nodes and link them. example
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node * link;
};
int main() {
struct node *head = malloc(sizeof(struct node));
head -> data = 60;
head -> link = NULL;
struct node *current = malloc(sizeof(struct node));
current -> data = 50;
current -> link = NULL;
head -> link = current;
return 0;
}
We will be using two methods to add the third node to the list.
Method 1:
Create another pointer that will point to the third node of the list.
struct node * current2 = malloc(sizeof(struct node));
current2 -> data = 70;
current2 -> link = NULL;
current -> link = current2;
return 0;
}
Pictorial representation:
But, there is a problem with this method, imagine you want to create a singly linked list containing 20 or 30 nodes, are you going to create 20 pointers for them? That is a waste of memory.
Method 2:
What does the head link give? 2000, right?
What does head -> link -> link give? 3000, right?
what does head -> link -> link -> link give? NULL.
curent= malloc(sizeof(struct node));
current -> data = 70;
current -> link = NULL;
We can see here that the current pointer is pointing to the third node of the list, and it is no longer pointing to the second node of the list.
In other to update that part you just need :
head -> link -> link = current;
return 0;
}
Final code.
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node * link;
};
int main() {
struct node *head = malloc(sizeof(struct node));
head -> data = 60;
head -> link = NULL;
struct node *current = malloc(sizeof(struct node));
current -> data = 50;
current -> link = NULL;
head -> link = current;
current = malloc(sizeof(struct node));
current -> data = 70;
current -> link = NULL;
head -> link -> link = current;
return 0;
}
Conclusion.
Head -> link gives the address 2000, head -> link -> link gives access to the link part of the second node, so I update the linked part of the second node using the current pointer. I simply assign current to get it updated to 3000.
I hope you find this article helpful. Feel free to comment if you want me to write another article on insertion, deletion, and traversal operations for a singly linked list in C.
Happy Coding!