Do you think IIT Guwahati certified course can help you in your career?
No
Introduction
A singly linked list is a type of linked list in which each node is connected to its next node via pointer and the last node consists of a null address to mark the end of the list. Elements are not stored in a continuous memory location. The first node is connected to the next node using the address of the node.
In this article, we will discuss the singly linked list algorithm. We will start with an introduction and later look at the algorithm and operations that can be performed on a singly linked list. In the end, we will discuss the advantages, disadvantages, and applications of singly linked lists.
What is a Singly Linked List?
Singly linked list is a type of linked list that has a sequence of nodes connected to each other. It has two parts. The first part is the data node that stores the actual information, the second part is the address node that stores the address for the next node. The last node second part stores null as the address.
In a singly linked list you can only traverse in a single direction which means reverse traversal in a singly linked list is not possible as each node has the address of the immediate successor.
The image given above is an example in which the numerical value is the score obtained by players. These score values are the data part and the arrow pointing towards the right has the address of the next node. The last node has null as the address.
Unlike in an array, the singly linked list is dynamically created and is connected to each other through pointers. Addition and deletion of elements can be performed on any element in the linked list.
Example of Singly Linked List
There are a few examples in which a singly linked list algorithm is used. The music playlist, Train coaches, Image viewer, Customer service call queue and many others. If you closely observe the music playlist you can navigate from one song to another because songs are stored sequentially. The first node, the data node, can contain the name or duration, and the next node has the address of the other song. in this way, it gets easy for us to go from one song to another.
How to define a node in the Singly Linked List?
A node in a singly linked list consists of two parts. A data part and a pointer that points towards the next node. This structure helps to dynamically create nodes and form a chain-like structure.
Given below is the implementation of defining a node in the singly linked list in C++, C, Java, Python, and Javascript programming languages.
Create a new node with two elements. Data and next. The next will store the address for the next node.
Create two pointers as head and tail.
Call the addNode() function that will add the new node in the linked list. If the head pointer is null, that means the list is empty, and the first node will be created. Since the list is empty tail will be also null.
If the list is empty, a new node will be created and the first node will be inserted making the head and tail point to the first node.
If the list is non-empty, the tail next pointer will point towards the new node that will be added.
In the first node, both head and tail will point towards the same address.
To display the node data values create a new pointer as current and traverse till it reaches the null pointer. Print the data value of the current pointer and move the current to its next.
Operations on Singly Linked List in Data Structure
There are various operations that can be performed on a singly linked list. Some of them are insertion, deletion, traversing, searching, and many more. There are multiple ways to perform these operations on the singly linked list. Let’s look at some of the ways below :
1. Insertion of a Node
Insertion of a new node can be done in multiple ways. A node can be inserted at the front of the node, before or after a given node, and also at the end of the list.
Below is the implementation of inserting a node.
Insertion at the Beginning of Node: If the list is empty, head and tail both will point towards the null. If the list is not null, will make head point towards the new node and new node next to the previous first node.
Algorithm to insert at the beginning of a linked list.
Create a new node with a value.
Set the new node's next pointer as the current head.
Update the head pointer to point towards the new node.
Return the new head of the linked list.
Code
void insert_beginning(Node*head, int value) {
//create a new Node
Node* NewNode = new Node(value);
//assign new node next as address of head
NewNode->next = head;
//assign head as new node address.
head= NewNode;
}
Insertion at the end of node : An element can be inserted in a singly linked list at the end of the list. To insert a node to the end of the list, traverse the list till the last node. Change the last node's next pointer to point towards the new node and make the new node's next pointer null to mark the end of the list.
Algorithm to insert at the end of a linked list:
Create a new node with a value.
Check if the list is empty. If the list is empty create this as the first and last node.
If the list is not empty, create a temporary pointer that points to the head of the linked list.
Traverse the temporary pointer till it reaches the end of the list.
Set the last pointer next to the new node.
Code
Node* insertAtEnd(Node*head, int value){
//create a new Node
Node* newNode = new Node(value);
//check if head is null
if (head == nullptr)
return newNode;
//assign head address to temp pointer
Node* temp = *head;
//traverse till last node
while (temp->next != nullptr) {
temp = temp->next;
}
//assign last node next pointer to new node
temp->next = newNode;
//return head pointer
return head;
}
Insertion after a Given Node: An element can be inserted in a singly linked list at any given position in the list. Traverse the list till you find the element after which you want to insert the new element and update the address of the nodes accordingly.
Algorithm to insert after a given node:
Create a variable and traverse it till the position -1 node.
Store the address of the node next in the variable.
Now store the position -1 next node points to the new element.
Store the curr variable next value to the new element next.
Code
void insertAfterNode(Node* givenNode, int x)
{
Node* newNode = new Node(x);
newNode->next = givenNode->next;
givenNode->next = newNode;
}
Deletion of a Node in the Linked list
A node can be deleted from the singly linked list. There are multiple ways to delete a node in the linked list. Node can be deleted from the beginning, middle, and end of the linked list.
Delete the First Node: To delete the first node, we check if the linked list is not empty. If not we create a temporary pointer that stores the head address and makes the head point to next and deletes the original start head.
Algorithm
Check if the list is empty or not. If the list is empty, return the underflow statement.
If the list is non-empty, create a temporary node that stores the first node address.
Update the head to point towards its next.
Delete the temporary node.
Return the new head of the linked list.
Code
Node* DeleteNodeBeg() {
//check if the linked list is empty
if (start == nullptr)
cout << ”Underflow” << ”\n”;
//assign head value to temp pointer and change head point to the next node
else {
Node * ptr = start;
start = start -> next; //statement-2
delete ptr;
}
return start;
}
Delete Specific Node: To delete a specific node traverse to the previous node to be deleted. Now change the next pointer of the previous node to skip the node to be deleted and point to the following node.
Later delete the node that needs to be removed.
Algorithm
Check if the list is empty. If the list is empty then return null.
Check if the node given is the first node of the linked list. If yes, move the head to point to the next node and return the new head.
Traverse the list till you find the just previous node from the node to be deleted.
If the node is found, create a temp pointer that stores the head address. Traverse till the node just before to the position to be deleted.
Update the temp next to the position to be deleted node next address.
If node is not found return the head as no changes required.
Code
Node deleteNode(Node* head, Node* toBeDeleted)
{
if(head == nullptr)
{
return nullptr;
}
// If the node to be deleted is the head node
if(head == toBeDeleted)
{
return head.next;
}
// temp is the traversing node.
Node* temp = head;
while( temp->next != nullptr )
{
// Searching for the previous node of the node to be deleted.
if(temp->next == toBeDeleted)
{
temp->next = temp->next->next;
// Freeing up the memory of the node to be deleted.
return head;
}
temp = temp->next;
}
// If no node matches in the Linked List.
return head;
}
Delete at the end of node: An element from a linked list can be deleted from the end of the linked list. Traverse the linked list till you get the null address. Delete that node and store null address in the previous node.
Algorithm
1. If the first node is null or there is only one node, then return null. 2. Find Second last node.
Delete last node.
Change next of second last in NULL.
void DeleteLastNode() {
if (start == nullptr) {
cout << "Underflow: List is empty" << "\n"; // List is empty
return;
}
if (start->next == nullptr) {
delete start; // If there's only one node
start = nullptr; // Update start to null
return;
}
// Find the second last node
Node* second_last = start;
while (second_last->next->next != nullptr) {
second_last = second_last->next;
}
// Delete the last node
delete(second_last->next);
// Change next of second last to null
second_last->next = nullptr;
cout << "Last node deleted\n";
}
3. Searching
Searching on a linked list can be performed in multiple ways. Search can be done from the beginning, end, or anywhere in the list.
Search an element: To search an element in the linked list traverse the linked list till you find the element. If a null value is received, the element is not present in the linked list. The time complexity for searching an element in a singly linked list average and worst case is the same as to find a similar element, you need to iterate through the complete list.
Algorithm
Create a temp pointer that stores the head address.
Iterate till the temp pointer to the null address.
In each iteration, check if the temp data matches the element given. If yes return 1 and if no data is found till the end of the list return 0.
Code
int searchElement(Node*head, int element ){
Node* temp= head;
while(temp!= nullptr)
{
if(temp->data == element)
{
return 1;
}
temp =temp->next;
}
return 0;
}
Traversing
Traversing in a singly linked list can only be done in a single direction. It displays the data node values in the singly linked list.
Print list
To display the value in the list we traverse the list till we reach the null value.
Algorithm
Traverse the list. Iterate till the head pointer reaches the null address.
In each iteration, print the data value of the element.
Once the head reaches null, return from the function.
// Function to create a new linked list struct LinkedList* createList() { struct LinkedList* list = (struct LinkedList*)malloc(sizeof(struct LinkedList)); list->head = NULL; return list; }
// Function to add a new node at the beginning void addNode(struct LinkedList* list, int value) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = value; newNode->next = list->head; list->head = newNode; }
// Function to insert a node at the beginning void insertAtBeginning(struct LinkedList* list, int value) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = value; newNode->next = list->head; list->head = newNode; }
// Function to insert a node at the end void insertAtEnd(struct LinkedList* list, int value) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = value; newNode->next = NULL;
if (list->head == NULL) { list->head = newNode; return; }
// Function to delete the head node void deleteNodeBeg(struct LinkedList* list) { if (list->head == NULL) { printf("Underflow - The list is empty.\n"); return; } struct Node* temp = list->head; list->head = list->head->next; free(temp); }
// Function to delete a specific node void deleteNode(struct LinkedList* list, struct Node* toBeDeleted) { if (list->head == NULL) return; if (list->head == toBeDeleted) { list->head = list->head->next; free(toBeDeleted); return; } struct Node* temp = list->head; while (temp->next != NULL) { if (temp->next == toBeDeleted) { temp->next = temp->next->next; free(toBeDeleted); return; } temp = temp->next; } }
// Function to traverse and print the linked list void traverse(struct LinkedList* list) { printf("Displaying singly linked list: "); struct Node* current = list->head; while (current != NULL) { printf("%d ", current->data); current = current->next; } printf("\n"); }
int main() { struct LinkedList* singlyLinkedList = createList();
// Adding nodes to the linked list addNode(singlyLinkedList, 5); addNode(singlyLinkedList, 32); addNode(singlyLinkedList, 18);
// Inserting at the beginning insertAtBeginning(singlyLinkedList, 10); insertAtBeginning(singlyLinkedList, 20); insertAtBeginning(singlyLinkedList, 30);
// Inserting at the end insertAtEnd(singlyLinkedList, 100);
// Display the list traverse(singlyLinkedList);
// Deleting the head of the linked list deleteNodeBeg(singlyLinkedList); printf("After deleting the head of the linked list:\n"); traverse(singlyLinkedList);
// Deleting a specific node struct Node* toDelete = singlyLinkedList->head->next; deleteNode(singlyLinkedList, toDelete); printf("After deleting a specific node:\n"); traverse(singlyLinkedList);
// Node definition struct Node { int data; Node* next;
Node(int value = 0) : data(value), next(nullptr) {} };
// Creating a Linked List class LinkedList { private: Node* head;
public: LinkedList() : head(nullptr) {}
// Function to create a new node in a linked list void AddNode(int value) { Node* newNode = new Node(value); if (head == nullptr) { head = newNode; } else { newNode->next = head; head = newNode; } }
// Function to insert a node at the beginning of the linked list void insertAtBeginning(int value) { Node* newNode = new Node(value); newNode->next = head; head = newNode; }
// Function to insert a node at the end of the linked list void insertAtEnd(int value) { Node* newNode = new Node(value); if (head == nullptr) { head = newNode; return; } Node* temp = head; while (temp->next != nullptr) { temp = temp->next; } temp->next = newNode; }
// Function to delete the head node Node* deleteNodeBeg() { if (head == nullptr) { cout << "Underflow - The list is empty." << endl; return head; } else { Node* temp = head; head = head->next; delete temp; return head; } }
// Function to delete a specific node Node* deleteNode(Node* toBeDeleted) { if (head == nullptr) { return nullptr; } if (head == toBeDeleted) { head = head->next; delete toBeDeleted; return head; } Node* temp = head; while (temp->next != nullptr) { if (temp->next == toBeDeleted) { temp->next = temp->next->next; delete toBeDeleted; return head; } temp = temp->next; } return head; }
// Function to traverse and print the linked list void traverse() { cout << "Displaying singly linked list: "; Node* current = head; while (current != nullptr) { cout << current->data << " "; current = current->next; } cout << endl; }
// Function to get the head node Node* getHead() { return head; } };
int main() { LinkedList singlyLinkedList;
// Adding nodes to the linked list singlyLinkedList.AddNode(5); singlyLinkedList.AddNode(32); singlyLinkedList.AddNode(18);
// Inserting at the beginning singlyLinkedList.insertAtBeginning(10); singlyLinkedList.insertAtBeginning(20); singlyLinkedList.insertAtBeginning(30);
// Inserting at the end singlyLinkedList.insertAtEnd(100);
// Display the list singlyLinkedList.traverse();
// Deleting the head of the linked list singlyLinkedList.deleteNodeBeg(); cout << "After deleting the head of the linked list:" << endl; singlyLinkedList.traverse();
// Deleting a specific node Node* toDelete = singlyLinkedList.getHead()->next; singlyLinkedList.deleteNode(toDelete); cout << "After deleting a specific node:" << endl; singlyLinkedList.traverse();
return 0; }
You can also try this code with Online C++ Compiler
// Function to add a new node at the beginning void addNode(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; } else { newNode.next = head; head = newNode; } }
// Function to insert a node at the beginning void insertAtBeginning(int value) { Node newNode = new Node(value); newNode.next = head; head = newNode; }
// Function to insert a node at the end void insertAtEnd(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; return; } Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = newNode; }
// Function to delete the head node void deleteNodeBeg() { if (head == null) { System.out.println("Underflow - The list is empty."); return; } Node temp = head; head = head.next; temp = null; // Allow garbage collection }
// Function to delete a specific node void deleteNode(Node toBeDeleted) { if (head == null) return; if (head == toBeDeleted) { head = head.next; toBeDeleted = null; // Allow garbage collection return; } Node temp = head; while (temp.next != null) { if (temp.next == toBeDeleted) { temp.next = temp.next.next; toBeDeleted = null; // Allow garbage collection return; } temp = temp.next; } }
// Function to traverse and print the linked list void traverse() { System.out.print("Displaying singly linked list: "); Node current = head; while (current != null) { System.out.print(current.data + " "); current = current.next; } System.out.println(); }
public static void main(String[] args) { LinkedList singlyLinkedList = new LinkedList();
// Adding nodes to the linked list singlyLinkedList.addNode(5); singlyLinkedList.addNode(32); singlyLinkedList.addNode(18);
// Inserting at the beginning singlyLinkedList.insertAtBeginning(10); singlyLinkedList.insertAtBeginning(20); singlyLinkedList.insertAtBeginning(30);
// Inserting at the end singlyLinkedList.insertAtEnd(100);
// Display the list singlyLinkedList.traverse();
// Deleting the head of the linked list singlyLinkedList.deleteNodeBeg(); System.out.println("After deleting the head of the linked list:"); singlyLinkedList.traverse();
// Deleting a specific node Node toDelete = singlyLinkedList.head.next; singlyLinkedList.deleteNode(toDelete); System.out.println("After deleting a specific node:"); singlyLinkedList.traverse(); } }
You can also try this code with Online Java Compiler
class Node: def __init__(self, value=0): self.data = value self.next = None
class LinkedList: def __init__(self): self.head = None
# Function to add a new node at the beginning def add_node(self, value): new_node = Node(value) if self.head is None: self.head = new_node else: new_node.next = self.head self.head = new_node
# Function to insert a node at the beginning def insert_at_beginning(self, value): new_node = Node(value) new_node.next = self.head self.head = new_node
# Function to insert a node at the end def insert_at_end(self, value): new_node = Node(value) if self.head is None: self.head = new_node return temp = self.head while temp.next is not None: temp = temp.next temp.next = new_node
# Function to delete the head node def delete_node_beg(self): if self.head is None: print("Underflow - The list is empty.") return temp = self.head self.head = self.head.next del temp
# Function to delete a specific node def delete_node(self, to_be_deleted): if self.head is None: return if self.head == to_be_deleted: self.head = self.head.next del to_be_deleted return temp = self.head while temp.next is not None: if temp.next == to_be_deleted: temp.next = temp.next.next del to_be_deleted return temp = temp.next
# Function to traverse and print the linked list def traverse(self): print("Displaying singly linked list: ", end="") current = self.head while current is not None: print(current.data, end=" ") current = current.next print()
if __name__ == "__main__": singly_linked_list = LinkedList()
# Adding nodes to the linked list singly_linked_list.add_node(5) singly_linked_list.add_node(32) singly_linked_list.add_node(18)
# Inserting at the beginning singly_linked_list.insert_at_beginning(10) singly_linked_list.insert_at_beginning(20) singly_linked_list.insert_at_beginning(30)
# Inserting at the end singly_linked_list.insert_at_end(100)
# Display the list singly_linked_list.traverse()
# Deleting the head of the linked list singly_linked_list.delete_node_beg() print("After deleting the head of the linked list:") singly_linked_list.traverse()
# Deleting a specific node to_delete = singly_linked_list.head.next singly_linked_list.delete_node(to_delete) print("After deleting a specific node:") singly_linked_list.traverse()
You can also try this code with Online Python Compiler
class LinkedList { constructor() { this.head = null; }
// Function to add a new node at the beginning addNode(value) { const newNode = new Node(value); if (this.head === null) { this.head = newNode; } else { newNode.next = this.head; this.head = newNode; } }
// Function to insert a node at the beginning insertAtBeginning(value) { const newNode = new Node(value); newNode.next = this.head; this.head = newNode; }
// Function to insert a node at the end insertAtEnd(value) { const newNode = new Node(value); if (this.head === null) { this.head = newNode; return; } let temp = this.head; while (temp.next !== null) { temp = temp.next; } temp.next = newNode; }
// Function to delete the head node deleteNodeBeg() { if (this.head === null) { console.log("Underflow - The list is empty."); return; } const temp = this.head; // Get the current head this.head = this.head.next; // Move head to the next node // No need to set temp to null, JavaScript garbage collector will take care of it }
// Function to delete a specific node deleteNode(toBeDeleted) { if (this.head === null) return; if (this.head === toBeDeleted) { this.head = this.head.next; return; } let temp = this.head; while (temp.next !== null) { if (temp.next === toBeDeleted) { temp.next = temp.next.next; return; } temp = temp.next; } }
// Function to traverse and print the linked list traverse() { let current = this.head; const listElements = []; while (current !== null) { listElements.push(current.data); current = current.next; } console.log("Displaying singly linked list: " + listElements.join(" ")); } }
// Usage example const singlyLinkedList = new LinkedList();
// Adding nodes to the linked list singlyLinkedList.addNode(5); singlyLinkedList.addNode(32); singlyLinkedList.addNode(18);
// Inserting at the beginning singlyLinkedList.insertAtBeginning(10); singlyLinkedList.insertAtBeginning(20); singlyLinkedList.insertAtBeginning(30);
// Inserting at the end singlyLinkedList.insertAtEnd(100);
// Display the list singlyLinkedList.traverse();
// Deleting the head of the linked list singlyLinkedList.deleteNodeBeg(); console.log("After deleting the head of the linked list:"); singlyLinkedList.traverse();
// Deleting a specific node const toDelete = singlyLinkedList.head.next; singlyLinkedList.deleteNode(toDelete); console.log("After deleting a specific node:"); singlyLinkedList.traverse();
You can also try this code with Online Javascript Compiler
Displaying singly linked list: 30 20 10 18 32 5 100
After deleting the head of the linked list:
Displaying singly linked list: 20 10 18 32 5 100
After deleting a specific node:
Displaying singly linked list: 20 18 32 5 100
Advantages of Singly Linked List
Singly Linked List works dynamically which means the size of a singly linked list can be increased and decreased as per the requirement.
Singly-linked lists are efficient in many applications and have many advantages when compared to an array.
Memory utilization is better in a singly linked list because only those data values that are in use occupy memory space, unlike arrays where a pre-defined allocation of space is required.
Adding or removing an element from a singly linked list is easy and convenient as only shifting of pointers is needed.
Time and space complexity both are less when compared to an array data structure.
Disadvantages of Singly Linked List
Traversal in a singly linked list can only be done in a single direction. Backward accessing of an element is not supported by a singly linked list.
The usage of a pointer makes it complicated to understand and debug the errors.
Extra space allocation is required because of the use of pointers.
Issues like memory leaks can occur because of garbage collection, especially in programming languages like C++ and C.
Head pointer in a singly linked list needs to be taken care of as it can lead to data loss. Also when multiple operations are performed and if the head pointer is not handled carefully, it may lead to inaccessibility to the list.
Memory management and null pointer dereference must be handled properly as it may lead to runtime errors and bugs.
Applications of Singly Linked List
Implementation of stack and queue: A singly-linked list is used to implement stack and queue data structures. Operations like addition and deletion can be easily performed.
Operating System: Singly linked list is used by the operating system to manage memory. It helps to keep track of free and allocated memory.
File Handling: File systems use singly linked lists to manage directories and files. This usage helps to traverse between multiple files and subdirectories.
DFS and BFS: A single linked list can be used to implement depth-first search and breadth-first search algorithms.
Frequently Asked Questions
What is the difference between singly linked list and doubly linked list?
The major difference between singly linked list and doubly linked list is the number of pointers each linked list. A singly linked list only stores the address of the next node whereas the doubly linked list has two pointers. The first pointer stores the address of the previous node and the second pointer stores the address of the next node.
What are the main operations that can be performed on a singly linked list?
There are multiple operations that can be performed on a singly linked list. Some of them are insertion, deletion, traversing, searching, and many others. Insertion can also be done in multiple ways like insertion at the beginning, insertion at the end, insertion at a given position, and others.
How do you reverse a singly linked list?
To reverse a singly linked list you mainly need three pointers. Traverse the linked list till the curr pointer reaches the null address and update the address for each of the nodes.
Can a singly linked list be implemented without a head pointer?
A singly-linked list can be implemented without a head pointer but it complicates the operations. You can create a singly linked list using the pointers instead of the head pointer to directly point toward the nodes.
How is a singly linked list different from an array?
An array and a singly linked list differ in terms of flexibility and storage of data. Array stores data with continuous memory allocation, with fixed size and faster access to data. A singly linked list does not store the data in continuous memory allocation but provides the flexibility to allow dynamic resizing and efficient operations.
Conclusion
A singly linked list is a versatile and efficient data structure used in various applications like memory management, file handling, and algorithm implementation. Understanding its structure, operations, and implementations helps optimize tasks requiring dynamic memory allocation and traversal, making it a valuable tool for developers and programmers.