Bubble Sort on Doubly Linked List

Yogesh Kumar
Last Updated: May 13, 2022

Problem Statement

Given a doubly-linked list, then using the bubble sorting algorithm, we have to sort the unsorted given doubly-linked list.

We have to use one of the sorting algorithms, Bubble sort, to sort the doubly linked list.

Eg: Input: 5<->1<->4<->3<->2<->9<->8

    Output: 1<->2<->3<->4<->5<->8<->9

  1. In the Linked List, we have given an unsorted element.
  2. We have to arrange the elements in ascending order with the help of a sorting algorithm.
  3. Here we are using a bubble sorting algorithm to reach the output for the problem statement.

Approach for Solving

We are using the same approach for what we use for Array data structure; we are going to keep track of adjacent elements; if it's found to be less than the present element then we have to swap both the elements. We will repeat the above approach until we arrange all the elements in the form of ascending order.

 

Code

/*
The steps we followed in writing the code for the idea.
1. Create the function that will help us make a doubly-linked list (addNode).
2. Now, we create a function for the print the doubly linked list to see whether it's created or not.
3. Now, create the sorting function to sort the doubly Linked List.
4. Now, at last call print_DLL function to print the sorted doubly linked list.
*/
public class bubble_sort_DLL {
  class Node{
      int data;
      Node next;
      Node prev;
      public Node(int data){
          this.data=data;
      }
  }
  Node head=null;
  Node tail=null;
  public  void addNode(int data){
      Node newNode=new Node(data);
      if(head==null){
          head=tail=newNode;
          head.prev=null;
          tail.next=null;
      }
      else{
          tail.next=newNode;
          newNode.prev=tail;
          tail=newNode;
          tail.next=null;
      }
  }
  public void print_DLL(){
      Node curr=head;
      if(curr==null){
          System.out.println("The Linked list is found to empty, Please add some data.");
      }
      while(curr!=null)
      {
          System.out.print(curr.data+" ");
          curr=curr.next;
      }
  }
  public  void bubble(){
      int f;
      Node ptr1;
      Node ptr2=null;
      if(head==null){
          return;
      }
      do{
          f=0;
          ptr1=head;
          while (ptr1.next!=ptr2){
              if(ptr1.data>ptr1.next.data){
                  int t=ptr1.data;
                  ptr1.data=ptr1.next.data;
                  ptr1.next.data=t;
                  f=1;
              }
              ptr1=ptr1.next;
          }
          ptr2=ptr1;
      }while (f!=0);
  }
  public static void main(String[] args){
      bubble_sort_DLL dll=new bubble_sort_DLL();
      dll.addNode(5);
      dll.addNode(1);
      dll.addNode(4);
      dll.addNode(3);
      dll.addNode(2);
      dll.addNode(9);
      dll.addNode(8);
      System.out.println("The given doubly linked list which we have to sort : ");
      dll.print_DLL();
      dll.bubble();
      System.out.println();
      System.out.println("The given doubly linked list after the sorting: ");
      dll.print_DLL();
  }
}

 

Dry-Run

For better understanding just take an example for detailed knowledge for working code.

Eg:

Input: 5<->1<->4<->3<->2<->9<->8

  1. Firstly, we are creating the linked list by calling the addNode function bypassing the data into it.
  2. Secondly, after completion of the Doubly Linked List.
  3. Thirdly, we call the print_DLL function to show the created Doubly Linked List.
  4. Fourthly, we call the bubble function for sorting the given Linked List.
    1. If head==null, then we have nothing to do, just return directly.
    2. If head!=null, we have to run a do-while loop until we have encountered the value of f==0 in the while check, which indicates that we have sorted all the elements.
    3. In the do-while loop, we declare two nodes ptr1 and ptr2, ptr1 assigned with head node, then ptr2 assigned as null, under do-while we have to iterate all the Linked List with conditional statements.
    4. Here ptr1 is used to transverse the linked list, and ptr2 is used to keep track until we move.
    5. In the condition statement if we find ptr1.data>ptr1.next.data, then we have to swap the element.
  5. At last, we have to call the print_DLL function to print the sorted, Doubly linked list.

Implementation example

Input: 5<->1<->4<->3<->2<->9<->8

  1. For the first we initialized f=0 and ptr1=head=1 and ptr2=null and ptr1.next=1!=null then we find ptr1.data>ptr1.next.data , then we swap the element, and also update the value of f=1, then shift ptr1.
    1. 1<->5<->4<->3<->2<->9<->8 '
  2. In the next step , we repeat step -1 ,ptr1=5 and ptr2=null , 5!=null ,then ptr1.data>ptr1.next.data then we swap , f=1 and shift ptr1.
    1. 1<->4<->5<->3<->2<->9<->8
  3. In the next step , we repeat step -1 , ptr1=5 and ptr2=null , 5!=null ,then ptr1.data>ptr1.next.data then we swap  ,f=1 and shift ptr1.
    1. 1<->4<->3<->5<->2<->9<->8
    2. 1<->4<->3<->2<->5<->9<->8
  4. Now we have ptr1.data<ptr1.next.data, we shift ptr1 
  5. Now we have ptr1=9 and pt2=null , f=1 , now ptr1.data>ptr1.next.data , then we shift the element.
    1. 1<->4<->3<->2<->5<->8<->9
  6. Now we have ptr1=9 and ptr1.next==ptr2.data==null , then we change ptr2=9 for the next iteration.
  7. This step-1 to 6 goes on repeat mode till we reach the value of f==0.
  8. We perform n-1+n-2+n-3+.......+3+2+1 total iteration to perform the bubble sort.

1<->2<->3<->4<->5<->8<->9

Note: - The main idea behind the value of f is that in bubble sort we have total n-1 passes for sorting the element, we are changing the value of f to 0 at the start as everything is sorted, but when we encounter some disorder, then we change it to 1. When at the end of n-1 the value of f remains to 0 after complete transversal then, in the last check while(f!=0) termination condition found where the value of f comes to 0, we go out of do-while and just done with our task for bubble sorting application over the doubly linked list.

Complexity

Taking about the Time Complexity of the code is O(N^2) because for the first time we are performing n-1 iteration, in next we have n-2 iteration, we have n-3 iteration, we proceed (n-1)+(n-2)+(n-3)+....+3+2+1, total iteration, we have (n-1)*(n-1+1)/2 =(n-1)*n/2=n^2 times we have to iterate, where n is the number of nodes in the Linked List. 

Now about Space Complexity, we are not using any other space other than constant time-space. We are doing operations on the same linked list. We are just using a constant variable of O(1) times for swapping elements. The Space Complexity is O(1).

Frequently Asked Question

  1. What is the Time Complexity and Space Complexity?
    Time Complexity is O(N^2), and Space Complexity is O(1).
  2. What is Sorting?
    Order data in an increasing or decreasing fashion according to some linear relationship among the data items.
  3. What is Bubble Sorting?
    Bubble Sort is the most straightforward sorting algorithm that works by repeatedly swapping the adjacent elements.
  4. What is the Time and Space Complexity of the Bubble sort?
    Best Time Complexity O(n), Average Time Complexity O(n^2), Worst Time Complexity O(n^2), Space Complexity O(1).
  5. When does Bubble sort have Time Complexity of O(n) and Space Complexity O(1)?
    When the list is already sorted, we have a Time Complexity of O(n) on performing Bubble sort.

Key Takeaways

In this blog, we discuss the sorting algorithm; in the doubly linked list data structure, we understand the concept using the code and the Dry-Run. We came up with Bubble Sort complexity in different cases as Best Time Complexity O(n), Average Time Complexity O(n^2), Worst Time Complexity O(n^2), Space Complexity O(1). We discuss the Time and Space Complexity of sorting the doubly linked list as O(N^2) and O(1), respectively.

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think