In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.
- Linked List can be defined as collection of objects called nodes that are randomly stored in the memory
- A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
- The last node of the list contains pointer to the null.
Uses of Linked List
- The list is not required to be contiguously present in the memory. The node can reside anywhere in the memory and linked together to make a list. This achieves optimized utilization of space.
- list size is limited to the memory size and doesn't need to be declared in advance.
- Empty node can’t be present in the linked list.
- Empty node can’t be present in the linked list.
Till now, we were using array data structure to organize the group of elements that are to be stored individually in the memory. However, Array has several advantages and disadvantages which must be known in order to decide the data structure which will be used throughout the program.
The following are the types of linked list:
- Single linked list
- Double linked list
- Circular linked list
It is the commonly used linked list in programs. If we are talking about the linked list, it means it is a singly linked list. The singly linked list is a data structure that contains two parts, i.e., one is the data part, and the other one is the address part, which contains the address of the next or the successor node. The address part in a node is also known as a pointer.
Suppose we have three nodes, and the addresses of these three nodes are 100, 200 and 300 respectively. The representation of three nodes as a linked list is shown in the below figure:
We can observe in the above figure that there are three different nodes having address 100, 200 and 300 respectively. The first node contains the address of the next node, i.e., 200, the second node contains the address of the last node, i.e., 300, and the third node contains the NULL value in its address part as it does not point to any node. The pointer that holds the address of the initial node is known as a head pointer.
The linked list, which is shown in the above diagram, is known as a singly linked list as it contains only a single link. In this list, only forward traversal is possible; we cannot traverse in the backward direction as it has only one link in the list.
Representation of the node in a singly linked list
struct node{
int data;
struct node *next;
};
In the above representation, we have defined a user-defined structure named a node containing two members, the first one is data of integer type, and the other one is the pointer (next) of the node type.
As the name suggests, the doubly linked list contains two pointers. We can define the doubly linked list as a linear data structure with three parts: the data part and the other two address part. In other words, a doubly linked list is a list that has three parts in a single node, includes one data part, a pointer to its previous node, and a pointer to the next node.
Suppose we have three nodes, and the address of these nodes are 100, 200 and 300, respectively. The representation of these nodes in a doubly-linked list is shown below
As we can observe in the above figure, the node in a doubly-linked list has two address parts; one part stores the address of the next while the other part of the node stores the previous node's address. The initial node in the doubly linked list has the NULL value in the address part, which provides the address of the previous node.
Representation of the node in a doubly linked list:
struct node{
int data;
struct node *next;
struct node *prev;
};
In the above representation, we have defined a user-defined structure named a node with three members, one is data of integer type, and the other two are the pointers, i.e., next and prev of the node type. The next pointer variable holds the address of the next node, and the prev pointer holds the address of the previous node. The type of both the pointers, i.e., next and prev is struct node as both the pointers are storing the address of the node of the struct node type
A circular linked list is a variation of a singly linked list. The only difference between the singly linked list and a circular linked list is that the last node does not point to any node in a singly linked list, so its link part contains a NULL value. On the other hand, the circular linked list is a list in which the last node connects to the first node, so the link part of the last node holds the first node's address. The circular linked list has no starting and ending node. We can traverse in any direction, i.e., either backward or forward. The diagrammatic representation of the circular linked list is shown below:
struct node{
int data;
struct node *next;
};
A circular linked list is a sequence of elements in which each node has a link to the next node, and the last node is having a link to the first node. The representation of the circular linked list will be similar to the singly linked list, as shown below:
The insertion into a singly linked list can be performed at different positions. Based on the position of the new node being inserted, the insertion is categorized into the following categories.
- Inserting at Beginning
- Inserting at the End of the List
- Inserting after specified node
Inserting a new element into a singly linked list at beginning is quite simple. We just need to make a few adjustments in the node links. There are the following steps which need to be followed in order to inser a new node in the list at beginning.
- Allocate the space for the new node and store data into the data part of the node. This will
be done by the following statements.
ptr = (struct node *) malloc(sizeof(struct node *));
ptr → data = item - Make the link part of the new node pointing to the existing first node of the list. This will
be done by using the following statement.
ptr->next = head - At the last, we need to make the new node as the first node of the list this will be done by
using the following statement.
head = ptr;
Function for inserting element at beginning of the list
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\n memory insufficient to allocate");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head; head = ptr;
printf("\nNode inserted");
}
}
In order to insert a node at the last, there are two following scenarios which need to be mentioned.
- The node is being added to an empty list(CASE 1)
- The node is being added to the end of the linked list(CASE2) in the first case,(CASE1)
- The condition (head == NULL) gets satisfied. Hence, we just need to allocate the space
for the node by using malloc statement in C. Data and the link part of the node are set up
by using the following statements.
ptr->data = item;
ptr -> next = NULL; - Since, ptr is the only node that will be inserted in the list hence, we need to make this
node pointed by the head pointer of the list. This will be done by using the following
Statements.
Head = ptr;
In the second case: CASE(2): - The condition Head = NULL would fail, since Head is not null. Now, we need to declare
a temporary pointer temp in order to traverse through the list. temp is made to point the
first node of the list.
Temp = head; - Then, traverse through the entire linked list using the statements:
while (temp→ next != NULL)
temp = temp → next; - At the end of the loop, the temp will be pointing to the last node of the list. Now, allocate the space for the new node, and assign the item to its data part. Since, the new node is going to be the last node of the list hence, the next part of this node needs to be pointing to the null. We need to make the next part
- If the temp node (which is currently the last node of the list) point to the new node (ptr)
.
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
Function for inserting element at the end of the list
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n"); scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
next = NULL
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
printf("\nNode inserted");
}
}
}
- In order to insert an element after the specified number of nodes into the linked list, we
need to skip the desired number of elements in the list to move the pointer at the position
after which the node will be inserted. This will be done by using the following
statements.
emp=head;
for(i=0;i< loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
return;
}
} - Allocate the space for the new node and add the item to the data part of it. This will be
done by using the following statements.
ptr = (struct node *) malloc (sizeof(struct node));
ptr->data = item; - Now, we just need to make a few more link adjustments and our node at will be inserted
at the specified position. Since, at the end of the loop, the loop pointer temp would be
pointing to the node after which the new node will be inserted. Therefore, the next part of
the new node ptr must contain the address of the next part of the temp (since, ptr will be
in between temp and the next of the temp). This will be done by using the following
statements.
ptr→ next = temp → next;
now, we just need to make the next part of the temp, point to the new node ptr. This will insert the new node ptr, at the specified position.
temp ->next = ptr;
The Deletion of a node from a singly linked list can be performed at different positions. Based on the position of the node being deleted, the operation is categorized into the following categories
- Deleting at Beginning
- Deleting at the End of the List
- Deleting after specified node
Deleting a node from the beginning of the list is the simplest operation of all. It just need a few
adjustments in the node pointers. Since the first node of the list is to be deleted, therefore, we just
need to make the head, point to the next of the head. This will be done by using the following
statements
ptr = head;
head = ptr->next;
Now, free the pointer ptr which was pointing to the head node of the list. This will be done by
using the following statement.
free(ptr)
C Function:
void begdelete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\n Node deleted from the begining ...");
}
}
Here are two scenarios in which, a node is deleted from the end of the linked list.
- There is only one node in the list and that needs to be deleted.
- There are more than one node in the list and the last node of the list will be deleted.
In the first scenario,
the condition head → next = NULL will survive and therefore, the only node head of the
list will be assigned to null. This will be done by using the following statements.
ptr = head;
head = NULL;
free(ptr)
In the second scenario,
The condition head → next = NULL would fail and therefore, we have to traverse the
node in order to reach the last node of the list.
For this purpose, just declare a temporary pointer temp and assign it to head of the list.
We also need to keep track of the second last node of the list. For this purpose, two
pointers ptr and ptr1 will be used where ptr will point to the last node and ptr1 will point
to the second last node of the list.
this all will be done by using the following statements.
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
Now, we just need to make the pointer ptr1 point to the NULL and the last node of the
list that is pointed by ptr will become free. It will be done by using the following
statements.
ptr1->next = NULL;
free(ptr);
C Function:
void end_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...");
}
else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\n Deleted Node from the last ...");
}
}
}
In order to delete the node, which is present after the specified node, we need to skip the desired
number of nodes to reach the node after which the node will be deleted. We need to keep track of
the two nodes. The one which is to be deleted the other one if the node which is present before
that node. For this purpose, two pointers are used: ptr and ptr1.
Use the following statements to do so.
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
{
printf("\nThere are less than %d elements in the list..",loc);
return;
}
}
Now, our task is almost done, we just need to make a few pointer adjustments. Make the next of
ptr1 (points to the specified node) point to the next of ptr (the node which is to be deleted).
This will be done by using the following statements.
Traversing is the most common operation that is performed in almost every scenario of singly
linked list. Traversing means visiting each node of the list once in order to perform some operation
on that. This will be done by using the following statements.
ptr = head;
while (ptr!=NULL)
{
ptr = ptr -> next;
}
- Insertions and Deletions can be done easily.
- It does not need movement of elements for insertion and deletion.
- It space is not wasted as we can get space according to our requirements.
- Its size is not fixed.
- It can be extended or reduced according to requirements.
- Elements may or may not be stored in consecutive memory available.
- It is less expensive.
- It requires more space as pointers are also stored with information.
- Different amount of time is required to access each element.
- If we have to go to a particular element then we have to go through all those elements that come before that element.
- we can not traverse it from last & only from the beginning.
- It is not easy to sort the elements stored in the linear linked list.
Graphs, queues, and stacks can be implemented by using Linked List.