# 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 tail
• Inserting after a node
• Inserting before a node
• Delete the tail node
• Search and Delete a node

Here’s an example of a linked list with four nodes.

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)
else:
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)
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)
```

## 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)
```

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 ):
free( temp )
```

## 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 ):
```

## 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 :
```

## 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 ):
print the value of the head
```

## Example of Singly Linked List in C++

```#include<iostream>
using namespace std;
struct Node{
int data;
struct Node *next;
};
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
}
}
}
Node* newNode = new Node();
newNode->data = value;
newNode->next = NULL;
while(temp->next!=NULL){
temp = temp->next;
}
temp->next = newNode;
}
Node *temp = new Node();
free(temp);
}else{
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;
}
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;
}
cout<<"Inserted "<<value<<" before node\t"<<searchItem<<endl;
}
Node* tempNode = new Node();
while(tempNode !=NULL){
cout<<tempNode->data;
if(tempNode->next)
cout<<" --> ";
tempNode = tempNode ->next;
}
cout<<endl;
}
int main(){
}
```

Output:

```Added 5 at the front
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
def __init__(self):
newNode = Node(data=value)
return
def insertAtEnd(self,value):
newNode = Node(value)
while temp.next is not None:
temp = temp.next
temp.next = newNode
def searchAndDelete(self,searchItem):
temp = Node()
else:
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)
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)
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):
while temp:
print("{}\t".format(temp.data),end="")
temp = temp.next
print()
```

Output:

```Added 5 at the front.
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).