Hey Ninjas! The linked list is one of the most essential concepts and data structures to comprehend when preparing for interviews. An advantage in a coding interview may be having a firm grasp of linked lists. The best use of linked lists is for adding and removing nodes from the list as it is easier. The list's insertion and deletion operations take a consistent amount of time, unlike the dynamic array.

In this blog, we will now learn about the bubble sort with swapping nodes on linked lists in this blog post, but first, let's briefly go over the problem statement once more.

Given a singly linked list and our task is to sort this linked list using a Bubble Sort algorithm by swapping nodes.

Note: We need to swap the actual nodes of the linked list instead of the values.

For Example,

Input:

Number of Nodes in Linked List: 3

Nodes in Linked List: 3 -> 2 -> 1

Output:

1 -> 2 -> 3

Explanation

Letâ€™s Begin by understanding what is Bubble Sort and how Bubble Sort functions.

Bubble Sort

The simplest sorting algorithm is known as bubble sort, and it works by frequently exchanging close elements if they are out of order. If you are not familiar with Bubble sort, we suggest that you read this article Bubble Sort. When sorting, each item is examined individually, compared to the subsequent component, and exchanged as necessary.

Here the algorithm for bubble sort remains the same, the only change that will affect the linked list is how are we performing the swap of two nodes since we need to swap actual nodes, not just the values. Now that we know what bubble sort is letâ€™s focus on how to swap the two nodes actually and not by their value.

Swapping Two Nodes

This is the most tricky part here because we have to swap the nodes themselves, not the values of the nodes. Swapping two nodes requires creating a temporary pointer temp which points to the next node which is to be swapped.

Later on, swapping can be achieved by simply changing the links of the nodeâ€™s next pointer and the corresponding nodes are swapped. To better comprehend the solution, let's take a look at the entire algorithm.

Algorithm

Run an outer loop for bubble sort comparisons starting from the first node of the linked list.

Check for the neighboring two nodes' values,

Adjacent nodes are switched if the value of the first node exceeds the value of the second node.. Letâ€™s take a look at how to swap the adjacent two nodes:

Let the current node be â€˜jâ€™ and the previous node be â€˜prevâ€™.

Now, Create a temporary pointer â€˜tempâ€™ which will point to the next pointer of the jth node.

Now we will perform 3 exchanges which will be:

Change the next pointer of j->next to temp->next.

Change the next pointer of temp->next to j.

Change the next pointer prev->next to temp.

Following the above-mentioned steps, the two neighboring nodes will get swapped.

Else if the value of the first node's value is less than or equal to the value of the second node, no swapping of nodes takes place.

This process goes on till there is no valid pair of adjacent nodes that are to be swapped. If there is no valid pair of adjacent nodes that means our list is sorted.

At last, the linked list is sorted in ascending order and it is displayed as the output.

Dry Run

Our initial linked list

First pass: As the first node has the value greater than the value of the second node they will get swapped.

Now, we will see the process of swapping 1st and 2nd node.

Our current node j which has value 3 and our next node temp which has value 2. Here, we have not considered a previous node â€˜prevâ€™ as our current node is the head of the linked list.

At first, we will change the link of our current node j to the next of the second node and our first node will be swapped to the right.

Now, our second node must be swapped to the left and its next pointer must point to the first node. Hence, our second nodeâ€™s next pointer will point to the the first node. Finally, after successfully swapping the first and second node our linked list looks like:

In our next iteration, next two nodes will be compared and their corresponding values will be checked.

Now, as we can see the first node's value is greater than the value of the second node. Hence, they have to be swapped similarly as the previous two nodes were swapped. Our current node j which has a value 3, our next node temp which has value 1 and our previous node prev which has a value 2. Here, we have not considered a previous node prev as our current node is the head of the linked list.

At first, we will change the link of our current node j to the next of the second node and our first node will be swapped to the right.

Now, our second node must be swapped to the left and its next pointer must point to the first node. Hence, our second nodeâ€™s next pointer will point to the the first node.

Now, our prev pointer must point to the temp pointer as the next nodes have been swapped. Finally, after successfully swapping the first and second node our linked list looks like:

2nd pass:

Now, as we can see the first node's value is greater than the value of the second node. Hence, they have to be swapped similarly to the previous two nodes were swapped. At first, we will change the link of our current node j to the next of the second node and our first node will be swapped to the right.

Now, our second node must be swapped to the left and its next pointer must point to the first node. Hence, our second nodeâ€™s next pointer will point to the first node.

Now, our prev pointer must point to the temp pointer as the next nodes have been swapped. Finally, after successfully swapping the first and second node our linked list looks like:

Now, the next nodes will be compared and their corresponding values will be checked.

Now, as we can see the first node's value is smaller than the value of the second node. Hence, there is no need to swap these two nodes.

Final linked list:

Implementation in C++

#include <iostream>
using namespace std;
// Node structure in linked list.
struct node{
int data;
struct node *next;
};
// For creating a new node for a number.
node* createnode(int value){
node* new_node = new node();
new_node->data = value;
new_node->next = nullptr;
return new_node;
}
// Function to push nodes into the list.
void push(struct node** tail, int newval){
struct node* newnode= createnode(newval);
(*tail)->next = newnode;
*tail= newnode;
}
// Function to print the Linked List
void print(node *head){
node *temp = head;
cout<<"Resultant Linked List: ";
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Function to calculate the length of the Linked List
int length(node* head){
node* temp = head ;
int len = 0 ;
while(temp!=NULL)
{
len++;
temp=temp->next ;
}
return len;
}
// Function to perform Bubble Sort on Linked List
node* bubble_sort(node* head){
node * i=head;
int len=length(head);
int itr=0;
// Iterating over the whole linked list
while(itr<len)
{
node *j=head;
node *prev=head;
while(j->next)
{
// Temporary pointer to store the next pointer of j
node* temp=j->next;
if(j->data>temp->data)
{
if(j==head)
{
// Performing swap operations and updating the head of the linked list
j->next=temp->next;
temp->next=j;
prev=temp;
head=prev;
}
else
{
// Performing swap operation
j->next=temp->next;
temp->next=j;
prev->next=temp;
prev=temp;
}
continue;
}
prev=j;
j=j->next;
}
++itr;
}
// Returning the head of the linked list
return head;
}
// Driver function.
int main(){
node* ref_head = createnode(0);
node* tail = ref_head;
// Linkedlist elements
push(&tail,3);
push(&tail,2);
push(&tail,1);
// Resultant linked list= 3 -> 2 -> 1
node *res=nullptr;
res=bubble_sort(ref_head->next);
print(res);
return 0;
}

Output

Implementation in Java

// Class for Node
class Node{
int data;
Node next;
// constructor
Node(int d)
{
data = d;
next = null;
}
}
// Class for LinkedList
class LinkedList{
Node head;
Node tail;
// Helper function to Print
void Print(Node head){
System.out.print("Resultant Linked List: ");
while(head != null)
{
System.out.print(head.data+" ");
head = head.next;
}
}
// Function to add data in the linked list
void insert(int x){
Node temp = new Node(x);
if(head == null){
head = temp;
tail = temp;
}
else
{
tail.next = temp;
tail = temp;
}
}
// Function to perform Bubble Sort on Linked List
public void bubble_sort(){
Node i=head;
int len=0;
while(i!=null)
{
i=i.next;
++len;
}
int itr=0;
// Iterating over the whole linked list
while(itr<len)
{
Node j=head;
Node prev=head;
while(j.next!=null)
{
// Temporary pointer to store the next pointer of j
Node temp=j.next;
if(j.data>temp.data)
{
if(j==head)
{
// Performing swap operations and updating the head of the linked list
j.next=temp.next;
temp.next=j;
prev=temp;
head=prev;
}
else
{
// Performing swap operation
j.next=temp.next;
temp.next=j;
prev.next=temp;
prev=temp;
}
continue;
}
prev=j;
j=j.next;
}
++itr;
}
}
}
// Driver Main Class
public class Solution
{
public static void main(String[] args) {
// Linkedlist elements
LinkedList li = new LinkedList();
li.insert(3);
li.insert(2);
li.insert(1);
li.bubble_sort();
li.Print(li.head);
}
}

Output

Complexity Analysis

Time Complexity

O(N^{2})

Explanation: In Bubble Sort, the iterations and the number of comparisons in them are listed as follows:

1st iteration: n - 1

2nd iteration: n - 2

3rd iteration: n - 3 and so on,

So the summation of the total number of comparisons in different iterations,

summation of (N-1) + (N-2) + (N-3) + ..... + 3 + 2 + 1 which is equivalent to N* (N - 1) / 2, i.e., O(N^{2})

Space Complexity

O(1)

Explanation: The algorithm only requires auxiliary variables for flags and temporary variables, and thus, the space complexity is O(1).

Frequently Asked Questions

What is the time complexity of swapping two adjacent nodes in a linked list?

Swapping the two neighboring nodes in a linked list is a constant time operation only thus itâ€™s a constant time complexity function which is O(1).

Do linked lists need pre-allocated memory-like arrays?

No, linked lists don't need pre-allocated memory during declaration. Rather we use dynamic memory location in the case of linked lists.

How to insert operations in an array is different from the insert operation in a linked list.

Insert operation in an array might need to shift a few elements to make space for the new element, as the memory allocation is contiguous in arrays. In contrast, in a linked list, a new node can be inserted in the linked list without shifting any element.

Mention a few applications on the linked list.

Applications of linked lists involve the implementation of stacks and queues and storing adjacency lists in case of implementation of graphs.

What is the best and worst time complexity of the bubble sort algorithm?

Best Time Complexity: O(N)

Worst Time Complexity: O(N^{2})

What are the benefits of using a linked list?

a) Linked list is dynamic in nature

b) Deletion and insertion are very fast in the linked list.

Conclusion

This blog discussed the detailed approach to performing the Bubble Sort algorithm on Linked Lists. We have discussed the problem statement with the help of a visual demonstration. We have also implemented the problem in two coding languages (C++ and Java).