Singly Linked List in Data Structures
What is a Singly Linked List?
Singly Linked List is a linear and unidirectional data structure, where data is saved on the nodes, and each node is connected via a link to its next node. Each node contains a data field and a link to the next node. Singly Linked Lists can be traversed in only one direction, whereas Doubly Linked List can be traversed in both directions.
Here’s a node structure of a Singly Linked List:
Why use linked list over array?
There’re several cases when it’s better to use the Linked List rather than the Array. Here’re some scenarios:
- Unknown number of elements: When you don’t know how many elements you need to store during the program runtime, you can use the Linked List. Memory is allocated dynamically as you add elements to the linked lists.
- Random access: In a scenario, where you don’t need to use the random access from the elements, you can use the Linked List.
- Insertion in the middle: Insertion in the middle of an array is a complex task. Because you need to push other elements to the right. However, a linked List allows you to add an element to any position you want.
Operations of Singly Linked List
Singly Linked List is good for dynamically allocating memory. It provides all the basic operations of the linked list, i.e., insertion, deletion, searching, updating, merging two linked lists, traversing, etc.
Here we’ll discuss the following operation of the linked list:
- Inserting at head
- Inserting at tail
- Inserting after a node
- Inserting before a node
- Delete the head node
- Delete the tail node
- Search and Delete a node
- Traversing the Linked List
Here’s an example of a linked list with four nodes.
Insertion at the head of a Singly Linked List
This is a simple operation. Generally, it’s known as pushing a singly linked list. You need to create a new node and place this at the head of the linked list.
To perform this operation, we need to follow two important conditions. They’re
- If the list is empty, then the newly created node will be the head node, and the next node of the head will be ”NULL”.
- If the list is not empty, the new node will be the head node, and the next will point to the previous head node.
Here’s the pseudo-code for inserting a node at the head of a linked list:
function insertAtHead( head, value ): newNode = Node(value) if head is NULL: head = newNode return head else: newNode.next = head return newNode
Insertion at the end of a Singly Linked List
Inserting a node at the end of a linked list has some similarities with inserting in the head. All you need to do is, traverse to the end node or the tail node. Then point the “next” node of the end node to the newly created node. If the head node is null, the new node will be the head node.
Here’re the steps:
Step 1) Traverse until the “next” node of the current node becomes null.
Step 2) Create a new node with the specified value.
Step 3) Assign the new node as the next node of the tail node.
The pseudo-code for inserting a node at the tail of a singly list:
function insertAtEnd( head, value ): newNode = Node(value) if head is NULL: head = newNode return head while head.next is not NULL: then head = head.next head.next = newNode newNode.next = NULL
Insertion after a node in a Singly Linked List
Inserting after a node has two parts: Search for the node and attach after the searched node. We need to traverse all the nodes. For each node, we need to match with the search element. If there’s a match, then we will add the new node after the searched node.
Here’re the steps:
Step 1) Traverse the next node until the value of the current node equals the search item.
Step 2) New node’s next pointer will be the current node’s next pointer.
Step 3) Current node’s next node will be the new node.
Here’s the pseudo-code for inserting a node after a node:
function insertAfter( head, value, searchItem ): newNode = Node(value) while head.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Insertion before a node in a Singly Linked List
This function is much similar to the insertion after a node. We must create a new node and traverse the linked list until the current node matches the search node. After that, we will add the new node as the previous node of the current node.
Here’re the steps:
Step 1) Traverse until the next node’s value equals the search item.
Step 2) Create a new node and assign the node’s “next” with the next to the next node of the current node.
Step 3) Assign the new node as the next node of the current node.
Here’s the pseudo-code:
function insertBefore( head, value, searchItem ): newNode = Node(value) while head.next.value equals searchItem: then head = head.next newNode.next = head.next.next head.next = newNode
Delete the head of the singly linked list
In every function of the linked list, the head pointer is provided as the parameter. You need to delete the head node and make the next node of the head node as the new head of the linked list. We also need to free the memory of the deleted node. Otherwise, the memory will be marked as occupied when another program tries to access it.
Here’re the steps for deleting the head of the singly linked list:
Step 1) Assign the next node of the head node as the new head.
Step 2) Free the allocated memory by the previous head node.
Step 3) Return the new head node.
The pseudo-code for deleting the head node:
function deleteHead( head ): temp = head head = head.next free( temp ) return head
Delete the tail of the singly linked list
Deleting the tail node is more familiar with deleting the head node. The difference is that we need to traverse to the end of the linked list and delete it. In the singly linked list, the node with the next node as “NULL” is the tail node.
Here’re the steps for deleting the tail node of the linked list:
Step 1) Traverse before the tail node. Save the current node.
Step 2) Free the memory of the next node of the current node.
Step 3) Set the next node of the current node as NULL.
Here’s the pseudo-code for deleting the tail node:
function deleteTail( head ): while head.next.next is not NULL: head = head.next free( head.next ) head.next = NULL
Search and delete a node from a singly linked list
This function has two tasks, search and delete. We need to search until the end of the singly linked lists. If we find any similar node, we will delete that one. After that, we need to merge or link the left and right nodes of the deleted node. Here’re the steps for doing this:
Step 1) Traverse until the end of the linked list. Check if the current node is equal to the search node or not.
Step 2) If any node matches, store the node pointer to the current node.
Step 3) The “next” of the previous node will be the next node of the current node.
Step 4) Delete and free the memory of the current node.
Pseudo-code for search and delete a node from a singly linked list:
function searchAndDelete( head, searchItem ): while head.next.next is not NULL and head.next.value is not equals searchItem : head = head.next head.next = head.next.next delete(head.next)
Traverse a singly linked list
Singly linked list only has the functionality for traversing head to tail. There are no pointer points to the previous node; that’s why we can’t traverse the Singly Linked List in reverse order. We will traverse each node and print the current node’s value until we get null.
Here’re the steps:
Step 1) Traverse each node until we get null as the next node.
Step 2) Print the value of the current node.
Pseudo-code for traversing a singly linked list:
function traverse( head ): while head.next is not NULL: print the value of the head head = head.next
Example of Singly Linked List in C++
#include<iostream> using namespace std; struct Node{ int data; struct Node *next; }; void insertAtHead(Node* &head, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; if(head!=NULL){ newNode->next = head; } head = newNode; cout<<"Added "<<newNode->data<<" at the front"<<endl; } void insertEnd(Node* &head, int value){ if(head==NULL){ insertAtHead(head,value); } Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *temp = head; while(temp->next!=NULL){ temp = temp->next; } temp->next = newNode; cout<<"Added "<<newNode->data<<" at the end"<<endl; } void searchAndDelete(Node **headPtr, int searchItem){ Node *temp = new Node(); if( (*headPtr)->data == searchItem ){ temp = *headPtr; *headPtr = (*headPtr)->next; free(temp); }else{ Node *currentNode = *headPtr; while(currentNode->next != NULL){ if(currentNode->next->data == searchItem){ temp = currentNode->next; currentNode->next = currentNode->next->next; free(temp); }else{ currentNode = currentNode->next; } } } cout<<"Deleted Node\t"<<searchItem<<endl; return; } void insertAfter(Node * &headPtr, int searchItem, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *head = headPtr; while(head->next!=NULL && head->data!=searchItem){ head = head->next; } newNode->next = head->next; head->next = newNode; cout<<"Inserted "<<value<<" after node\t"<<searchItem<<endl; } void insertBefore(Node * &headPtr, int searchItem, int value){ Node* newNode = new Node(); newNode->data = value; newNode->next = NULL; Node *head = headPtr; while(head->next!=NULL && head->next->data!=searchItem){ head = head->next; } newNode->next = head->next; head->next = newNode; cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl; } void traverse(Node *headPointer){ Node* tempNode = new Node(); tempNode = headPointer; cout<<"Traversal from head:\t"; while(tempNode !=NULL){ cout<<tempNode->data; if(tempNode->next) cout<<" --> "; tempNode = tempNode ->next; } cout<<endl; } int main(){ Node *head = NULL; insertAtHead(head,5); insertAtHead(head,6); insertAtHead(head,7); insertEnd(head,9); traverse(head); searchAndDelete(&head,6); traverse(head); insertAfter(head,7,10); insertBefore(head,9,11); traverse(head); }
Output:
Added 5 at the front Added 6 at the front Added 7 at the front Added 9 at the end Traversal from head: 7 → 6 → 5 → 9 Deleted Node 6 Traversal from head: 7 → 5 → 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversal from head: 7 → 10 → 5 → 11 → 9
Example of Singly Linked List in Python Program
class Node: def __init__(self,data = None, next = None): self.data = data self.next = next class SinglyLinkedList: def __init__(self): self.head = None def insertAtHead(self, value): newNode = Node(data=value) if self.head is not None: newNode.next = self.head self.head = newNode print(f'Added {newNode.data} at the front.') return def insertAtEnd(self,value): if self.head is None: self.insertAtHead(value) newNode = Node(value) temp = self.head while temp.next is not None: temp = temp.next temp.next = newNode print(f'Added {newNode.data} at the end.') def searchAndDelete(self,searchItem): temp = Node() if self.head is searchItem: temp = self.head self.head = self.head.next else: currentNode = self.head while currentNode.next is not None: if currentNode.next.data is searchItem: temp = currentNode.next currentNode.next = currentNode.next.next else: currentNode = currentNode.next print(f'Deleted node\t{searchItem}') return def insertAfter(self,searchItem,value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.data is not searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode print(f'Inserted {value} after node\t{searchItem}') return def insertbefore(self,searchItem,value): newNode = Node(data=value) temp = self.head while temp.next is not None and temp.next.data is not searchItem: temp = temp.next newNode.next = temp.next temp.next = newNode print(f'Inserted {value} before node\t{searchItem}') return def traverse(self): temp = self.head print("Traversing from head:\t",end="") while temp: print("{}\t".format(temp.data),end="") temp = temp.next print() SinglyLinkedList = SinglyLinkedList() SinglyLinkedList.insertAtHead(5) SinglyLinkedList.insertAtHead(6) SinglyLinkedList.insertAtHead(7) SinglyLinkedList.insertAtEnd(9) SinglyLinkedList.traverse() SinglyLinkedList.searchAndDelete(6) SinglyLinkedList.traverse() SinglyLinkedList.insertAfter(7,10) SinglyLinkedList.insertbefore(9, 11) SinglyLinkedList.traverse()
Output:
Added 5 at the front. Added 6 at the front. Added 7 at the front. Added 9 at the end. Traversing from head: 7 6 5 9 Deleted node 6 Traversing from head: 7 5 9 Inserted 10 after node 7 Inserted 11 before node 9 Traversing from head: 7 10 5 11 9
Complexity of Singly Linked List
There are two kinds of complexity: time complexity and space complexity. The worst and average case time complexity is the same for the Singly Linked List.
The time complexity for the best case:
- Insertion in the head can be done in O(1). As we don’t need to traverse inside of the linked list.
- Search and delete operation can be done in O(1) if the search element is present in the head node.
The time complexity for the average case:
- Insertion inside a linked list will take O(n) if “n” elements are present in the Singly Linked List.
- Search and delete can take O(n) too, as the search element can be present in the tail node. In that case, you should traverse the whole list.
Space Complexity of Singly Linked List
Singly Linked List dynamically allocates memory. If we want to store n elements, it will allocate n memory unit. So, the space complexity is O(n).