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

1. 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”.
2. 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).