Singly
Linked List
Like arrays, linked lists are linear data structure. Unlike arrays, the linked lists elements are not stored in contiguous memory location, the elements in linked list are linked using pointers.
Why Linked list?
Though Arrays can store elements in contiguous memory location, they have few disadvantages or limitations.
+91-4446311234
+1-6502652492
+91-7530088009
int id[] = {100, 108, 111, 123, 133, 143}Hence, linked list have advantages over arrays such as
Limitations
Though, we say linked list is better than array, we have few disadvantages such as
Representation of a
Linked List
A linked list is represented by a pointer to the first node of the linked list. The first node in the linked list is called ad HEAD. If the linked list is empty, then the value of the head is NULL.
Each node is separated into two different parts:
From the above image,
In simple words, a linked list consists of nodes where each node contains a data field and a reference link (pointer) to the next node in the linked list.
The following is the representation of Linked List:
struct Node{
int data;
struct Node *next;
};Creating a
Linked List:
Let see how we create a singly linked list consists of three elements, for example look at the below C code:
#include<stdio.h>
#include<stdlib.h>
struct Node{
int data;
struct Node *next;
};
void main()
{
struct Node *head = NULL;
struct Node *second = NULL;
struct Node *third = NULL;
head = (struct Node*)malloc(sizeof(struct Node*));
second = (struct Node*)malloc(sizeof(struct Node*));
third = (struct Node*)malloc(sizeof(struct Node*));
head->data = 100; //First node has data 100
head->next = second; //Link first node with the second node
second->data = 101; //Second node has data 101
second->next = third; //Link second node with the third node
third->data = 102l; //Third node has data 102
third->next = NULL; //Last node is not linked to any
}
From the above example, structure Node has defined with two parts, namely integer data and Node pointer. The head node assigned the data 100 and the pointer has assigned to the next node (second). The second node is linked to the third node and the pointer to the third node is NULL which is a last node in the linked list.
In the previous example program, we have created Linked list with three nodes. Let us traverse the Linked List and print the data of the each node. For traversal, let us write a general method printList() which prints all the data in the linked list.
void printList(struct Node *p)
{
while (p != NULL){
printf("%d ", p->data);
p = p->next;
}
}
Output
100 101 102Linked List
Insertion
In Linked List, the new node can be inserted in three ways such as:
Add a node
at the front:
Generally, a new node is added at the front of the Linked List and newly added node becomes the new head of the Linked List.
As per the above figure,
Let us call the function which adds the node at the front as push() function. The push() function must receive a pointer to the head pointer, because it should change the head pointer to point to the new node.
Example
void push(struct Node **head_ref, int new_data)
{
struct Node *new_node = (struct Node*)malloc(sizeof(struct Node*));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
In the above example, the push function has two arguments namely, pointer reference (**head_ref) and the new_data to be added. Here we send the pointer reference as an argument, as we add new_data as the first (head) node to the linked list.
The time complexity to add the new_node at the front is O(1).
Add a node after a
given node:
We are given pointer to a node, and the new node is inserted after the given node.
From the above figure,
Let us call the function insertAfter() which add a node after a given node. The function insertAfter() receives two parameters namely, prev_node (the new node is added next to this prev_node) and a new_data.
Example
void insertAfter(struct Node *prev_node, int new_data)
{
/*check if the previous node is NULL */
if(prev_node == NULL)
{
printf("The given previous node cannot be NULL");
return;
}
struct Node *new_node = (struct Node *)malloc(sizeof(struct Node*));
/*Insert new_node next to prev_node */
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
return;
}
In the above example, we insert the new node, next to the given node. For example, the existing Linked list is 100->101->102. The new node 1000 needs to be inserted next to the head node, then the function called with parameters as insertAfter(head->next, 1000). Hence, after adding the node, the linked list is 100->1000->101->102.
The time complexity for insertAfter() is O(1).
Add a node
at the end:
The new node can be at the end of the linked list. It is added such a way that, it traversed to the last node and added. The time complexity for adding the node at the end is O(n). If the linked list has a tail pointer, then the complexity of adding a node at the end is same as adding the node at the front which is O(1).
Since we always represent the Linked List by the head of it, we have to traverse the list till end and then change the next of the last node to new node.
As per the above figure,
Let us call the function which adds the node at the end as append() function. The append() function must receive two arguments namely, head reference pointer and the new node data.
Example
void append(struct Node **head_ref, int new_data)
{
struct Node *new_node = (struct Node*)malloc(sizeof(struct Node*));
struct Node *last = *head_ref; //temporary node
new_node->data = new_data;
new_node->next = NULL;
/* If the new node is empty, then make the new node as head */
if(*head_ref == NULL)
{
*head_ref = new_node;
return;
}
/* Traverse till last to append the new node at the end */
while(last->next != NULL)
last = last->next;
last->next = new_node;
return;
}
In the above method, we use append function to add the new node at the end of the Linked list. We pass two arguments for the function, namely, pointer reference (*head_ref) and new data. Traverse the last pointer (temporary pointer) till last and append the new node next to the last node.
The time complexity for the above program is O(n).
Linked List
Deletion
The element in linked list is deleted using “key”. Given a “key” to delete the first occurrence of this key in linked list. To delete a node from the linked list, we follow the below steps.
1. Find the previous node of the node to be deleted.
2. Change the next of the previous node to the next of the key node.
3. Free the memory for the node to be deleted.
As per the above figure,
Let us call the function deleteNode() to delete the particular node from the Linked list. Here we pass two arguments, namely head_ref and the key.
Example
void deleteNode(struct Node **head_ref, int key)
{
struct Node *temp = *head_ref, *prev;
//If head node itself hold the key to be deleted
if(temp != NULL && temp->data == NULL)
{
*head_ref = temp->next;
free(temp);
return;
}
//Search for the key to be deleted and also keep track of the
//previous node
while(temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
//If key is not present in linked list
if(temp == NULL)
return;
//Unlink the node from linked list
prev->next = temp->next;
free(temp); //Free memory
}
In the above function, the few use cases are handled such as,
