Sorting a linked list using bubble sort

How do we sort a linked list?
In this post, we see one such method using bubble sort algorithm.

We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.

We first find the length of the linked list (len). The outer loop iterates for (len-1) times and the inner loop iterates for (len-1-i) times.

Since we cannot access the linked list elements by their indices, we use two pointers to keep track of the current node and the next node which will be compared and swapped in each iteration.

Here is the Object Oriented C++ implementation.

	#include <iostream>

	using namespace std;
	class SLLNode
	{
	private:
	int data;
	SLLNode *nextPtr;

	public:
	SLLNode(int d):data(d),nextPtr(NULL)
	{
	}
	SLLNode(int d,SLLNode* next):data(d),nextPtr(next)
	{
	}

	int getData()
	{
	return data;
	}

	void setData(int d)
	{
	this->data = d;
	}

	SLLNode* getNext()
	{
	return this->nextPtr;
	}

	void setNext(SLLNode *ptr)
	{
	this->nextPtr = ptr;
	}
	};

	//defines the actual single linked list
	class SinglyLinkedList
	{
	private:
	//maintain two pointers to the start and the end
	//so that we can append at the end easily (constant time complexity)
	SLLNode * head;
	SLLNode * tail;
	public:
	SinglyLinkedList()
	{
	head = NULL;
	tail = NULL;
	}
	//adds the node to the end of the list
	void appendNode(SLLNode* ptr)
	{
	//check if list is empty
	if( head == NULL)
	{
	//update both the pointers
	head = tail = ptr;
	}
	else //simply append at the end, and move the tail pointer
	{
	tail->setNext(ptr);
	tail = tail->getNext();
	}
	}

	//gets the length of the list
	int getLength()
	{
	int length = 0;

	SLLNode* ptr = head;

	while ( ptr != NULL )
	{
	length++;
	ptr = ptr->getNext();
	}
	return length;
	}

	//Sort the given linked list
	void sort()
	{
	int len = getLength();
	if( len > 1)
	{
	int i,j;

	for( i = 0; i < len-1; i++ )
	{
	SLLNode * current = head;
	SLLNode * next = head->getNext();
	for( j = 0; j < len-i-1; j++ )
	{
	if( current->getData() > next->getData() )
	{
	int temp = current->getData();
	current->setData(next->getData());
	next->setData(temp);
	}
	current = next;
	next = next->getNext();
	}
	}
	}
	}
	void print()
	{
	SLLNode *ptr = head;
	while( ptr )
	{
	cout<< ptr->getData() <<" ";
	ptr = ptr->getNext();
	}
	cout<<endl;
	}
	};
	int main()
	{
	SinglyLinkedList list;
	list.appendNode(new SLLNode(3));
	list.appendNode(new SLLNode(6));
	list.appendNode(new SLLNode(1));
	list.appendNode(new SLLNode(9));
	list.appendNode(new SLLNode(5));
	list.appendNode(new SLLNode(2));
	list.appendNode(new SLLNode(8));
	list.appendNode(new SLLNode(4));
	list.appendNode(new SLLNode(7));

	list.sort();

	list.print();

	return 0;
	}

view raw SortLinkedList.cpp hosted with

by GitHub

Leave a Reply Cancel reply