Bubble Sort On Doubly Linked List

Sorting a linked list can be troublesome sometimes, but there are multiple algorithms to do so easily. A bubble sort might not be the most efficient one for sorting a Linked List but it does give us one of the most simple solutions to the problem.
Bubble sort for the doubly linked list is similar to single list just we also have to update the previous pointer.
Suppose we have a doubly-linked list as 3 4 5 2 1
Then after bubble sort, we will have 1 2 3 4 5

Approach

The idea is similar to what we do in arrays, we keep on checking the adjacent elements and swap the elements if the first element is greater than the next element. We keep on doing this till all the elements are arranged in ascending order.

Algorithm

  • We use a do-while loop and a swap variable to denote if we want to swap the elements or not
  • Traverse the Doubly Linked List and if for a current element if the next element is greater than the current element then swap the two nodes by changing their pointers and mark swap = 1
  • We keep on doing this till we get all the elements in the list in sorted order.
  • Finally, we return the head of the doubly linked list.

Code Implementation

Bubble Sort On Doubly Linked List

#include 
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
void insertAtTheBegin(struct Node **start_ref, int data)
{
    struct Node *ptr1 = new Node;
    ptr1->data = data;
    ptr1->next = *start_ref;
    if (*start_ref != NULL)
    (*start_ref)->prev = ptr1;
    *start_ref = ptr1;
}
void display(struct Node *start)
{
    struct Node *temp = start;
    cout << endl;
    while (temp!=NULL)
    {
        cout << temp->data << " ";
        temp = temp->next;
    }
}
void bubbleSort(struct Node *start)
{
    int swapp, i;
    struct Node *ptr1;
    struct Node *lptr = NULL;
    if (start == NULL)
        return;

    do
    {
        swapp = 0;
        ptr1 = start;

        while (ptr1->next != lptr)
        {
            if (ptr1->data > ptr1->next->data)
            {
                swap(ptr1->data, ptr1->next->data);
                swapp = 1;
            }
            ptr1 = ptr1->next;
        }
        lptr = ptr1;
    }
    while (swapp);
}

int main()
{
    int arr[] = {3, 4, 5, 2, 1};
    int list_size, i;
    list_size = sizeof(arr)/sizeof(arr[0]);
    struct Node *start = NULL;
    for (i = 0; i< list_size; i++)
        insertAtTheBegin(&start, arr[i]);
    bubbleSort(start);
    display(start); 
    return 0;
}
class PrepBytes
{
static class Node
{
    int data;
    Node prev;
    Node next;
};
static Node pushatbegin( Node start_ref, int data)
{
    Node ptr1 = new Node();
    ptr1.data = data;
    ptr1.next = start_ref;
    if (start_ref != null)
    (start_ref).prev = ptr1;
    start_ref = ptr1;
    return start_ref;
}
static void display( Node start)
{
    Node temp = start;
    System.out.println();
    while (temp != null)
    {
        System.out.print( temp.data + " ");
        temp = temp.next;
    }
}
static Node bubbleSort( Node start)
{
    int swapp, i;
    Node ptr1;
    Node lptr = null;
    if (start == null)
        return null;

    do
    {
        swapp = 0;
        ptr1 = start;

        while (ptr1.next != lptr)
        {
            if (ptr1.data > ptr1.next.data)
            {
                int t = ptr1.data;
                ptr1.data = ptr1.next.data;
                ptr1.next.data = t;
                swapp = 1;
            }
            ptr1 = ptr1.next;
        }
        lptr = ptr1;
    }
    while (swapp != 0);
        return start;
}
public static void main(String args[])
{
    int arr[] = {3, 4, 5 ,2 ,1};
    int i;
    Node start = null;
    for (i = 0; i < 5; i++)
        start=pushatbegin(start, arr[i]);
    start = bubbleSort(start);
    display(start);
}
}

Output: 1 2 3 4 5

Space Complexity: O(1), no extra space is used.

This blog tried to explain the bubble sort algorithm on a doubly-linked list by modifying the node pointer and walkthrough the approach and algorithm along with the code implementation in various languages. To practice more such problems on Linked List you can check out PrepBytes - Linked-list

Previous post Top 30 Java Programming interview questions
Next post Find the length of a loop in the linked list

Leave a Reply

Your email address will not be published. Required fields are marked *