Bubble Sort On Doubly Linked List

Last Updated on November 16, 2022 by Prepbytes

Sorting is one of the famous techniques used to rearrange the array or the list of elements. In this article, we will learn how to sort a doubly linked list using bubble sort.

Sorting a linked list can be troublesome sometimes, but there are multiple algorithms to do so easily. A bubble sort on doubly linked list might not be the most efficient one for sorting a doubly linked List but it does give us one of the simple solutions to the problem.

Bubble sort on doubly linked list is similar to a 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 sorting, we will have 1 2 3 4 5

Approach on how to sort a doubly linked list

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 for doing bubble sort on doubly linked list.

Algorithm for bubble sort on doubly linked list

• 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 doing this until we get all the elements in the list in sorted order.
• Finally, we return the head of the doubly linked list for doing bubble sort on 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.

Conclusion:

In this article, we tried to explain the bubble sort on a doubly linked list by modifying the node pointer and walkthrough the approach and algorithm along with the code implementation in various languages.

FAQs on how to sort a doubly linked list

1. What is bubble sort?
   Bubble sort is a sorting technique that works frequently by swapping the adjacent elements if they are not in the correct order.

2. What is a doubly linked list?
   A doubly linked list is a data structure which contains nodes with points to the previous node as well to the next node.

3. What is the space and time complexity of bubble sort?
   The time complexity for bubble sort is O(N^2) and space complexity is O(1)