1.
Introduction
2.
Problem Statement
3.
Solution
4.
4.1.
How is a Doubly Linked List different than a Singly Linked List?
4.2.
What is the worst-case time complexity of the QuickSort algorithm?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# QuickSort on a Doubly Linked List

GAZAL ARORA
0 upvote

## Introduction

Linked Lists are one of the most fundamental data structures having a wide range of applications across various fields, Quicksort is one of the major elementary sorting algorithms. Although it does not fare well for large data sets, for smaller data sets QuickSort is extremely fast and optimal in nature. Let us take a look at how to implement that algorithm on a Doubly Linked List.

## Problem Statement

Implement QuickSort on a Doubly Linked List.

If you're unfamiliar with QuickSort's Array Implementation, I recommend you to look at it before continuing with this post.

Alert Ninjas: Don't stop now! Enroll in the Competitive Programming course today and start coding. Learn the art of writing time and space-efficient code and compete in code competitions worldwide.

For example,

15  12  8  4  2

2  4  8  12  15

Also see, Data Structures and Rabin Karp Algorithm

## Solution

Recommended: Please try to solve it yourself first before moving on to the solution.

The idea is simple:

• We will first find the pointer to the last node of the Linked List.
• We can recursively sort the Linked List using pointers to the first and last nodes of a linked list, similar to the recursive method where we pass indexes of first and last array elements.
• A linked list's partition function is similar to that of an array's partition function. It will return a pointer to the pivot element instead of the index of the pivot element.

Below is the C++ implementation of QuickSort on a Doubly Linked List:

``````// QuickSort on a Doubly Linked List

#include <bits/stdc++.h>
using namespace std;
// a node of a doubly linked list.
class Node
{
public:
int data;
Node *next;
Node *prev;
};

/* A helper function to swap elements. */
void swap ( int* x, int* y ) {

int temp = *x;
*x = *y;
*y = temp;
}

// A helper function to find the last node of the linked list.
{
while (root && root->next)
root = root->next;
return root;
}

//Consider the last element as pivot.
Node* partition(Node *start, Node *end)
{
// set pivot as end element.
int pivot = end->data;

// similar to i = l-1 for array implementation.
Node *i = start->prev;

for (Node *temp = start; temp != end; temp = temp->next)
{
if (temp->data <= pivot)
{

if ( i == NULL)
i = start;
else
i = i->next;

swap(&(i->data), &(temp->data));
}
}

if ( i == NULL)
i = start;
else
i = i->next;

swap(&(i->data), &(end->data));
return i;
}

// implementation of quicksort.
void _quickSort(Node *start, Node *end)
{
if (end != NULL && start != end && start != end->next)
{
Node *pivot = partition(start, end);
_quickSort(start, pivot->prev);
_quickSort(pivot->next, end);
}
}

void quickSort(Node *root)
{

Node *end = lastNode(root);
}

// A helper function to print contents of arr.
void printList(Node *root)
{
while (root)
{
cout << root->data <<  " ";
root = root->next;
}
cout << endl;
}

//helper function to insert a node in the beginning.
{
Node* node = new Node;
node->data = data;

node->prev = NULL;

}

/* Driver code */
int main()
{
Node *root = NULL;
push(&root, 2);
push(&root, 4);
push(&root, 8);
push(&root, 12);
push(&root, 15);

cout <<  "Linked List before sorting \n";
printList(root);

quickSort(root);

cout <<  "Linked List after sorting \n";
printList(root);
return 0;
}``````

Output

Time Complexity

The above implementation is the same as QuickSort for arrays. Therefore time complexity is also the same as that of the time complexity of QuickSort for an array.

In the worst case, it takes O(n2) time, whereas, in the average and best cases, it takes O(NLogN). When the linked list is already sorted, the worst case occurs.

### How is a Doubly Linked List different than a Singly Linked List?

The nodes of Doubly Linked Lists have pointers to their previous nodes as well as their next nodes in them. Whereas the nodes of a singly Linked List only have pointers to the next node.

### What is the worst-case time complexity of the QuickSort algorithm?

QuickSort algorithm has a worst-case time complexity of O(N*N) where N is the size of the data set and the next case time complexity is O(NlogN).

## Conclusion

Here we saw how to implement QuickSort on a Doubly Linked List. Join this Master Class on DP by Coding Ninjas and become a Ninja coder.

Challenge: Can you implement random QuickSort for a linked list?
Random QuickSort is when we choose pivot randomly. We can only implement Quicksort for Linked List when we can choose a fixed point as the pivot (like the last element in the above implementation). Therefore, Random QuickSort cannot be implemented for Linked Lists.

Recommended Problems -

Recommended Articles

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Happy Coding!