How to Sort Linked List in C++

1. List in C++
2. Implement a Linked List in C++
3. Sort a Linked List in C++

This trivial programming tutorial demonstrates the implementation of the sort operation on a Linked List data structure in C++.

List in C++

List or Linked List is a linear data structure that can serve as a data container and store the data in the memory. Unlike vectors or arrays, data in the list do not require consecutive memory locations; instead, the data can dynamically be grown and allocated to arbitrary heap memory locations.

Each element in the list is called a node. Each node in a list contains a pointer pointing to the very next node of the list.

Including the pointer to the next element in each node can facilitate linear chaining where every next element can be accessed through the previous node. This linear chaining among the nodes is the main reason for giving this structure the name of Linked List.

Several ADT (Abstract Data Type) operations can be performed on the Linked List like insertion, deletion, searching, and even sorting. We will start with the basic structural implementation of the linked list and then implement the sorting algorithm in that class.

Implement a Linked List in C++

Now, we will start the implementation of the Linked List. For that, first, we need to create a class for Node like this:

template <class T>
class Node {
 public:
  T data;
  Node<T>* next;
  Node() { next = 0; }
};

In this class, there are two members, one for storing data, i.e., info, and the other is the class’s pointer for storing the next node’s address. The class is made templated so that a list of any data type can be created.

Now, we will create a Linked List class like this:

template <class T>
class LSLL {
 private:
  Node<T>* head;

 public:
  LSLL() { head = 0; }
  void insertAtHead(T val) {
    Node<T>* x = new Node<T>(val);
    x->next = head;
    head = x;
  }
  void displayAll() {
    Node<T>* x = head;
    {
      while (x != 0) {
        cout << x->info << endl;
        x = x->next;
      }
    }
  }
};

In this class, there is a constructor and two other member functions to insert and display the list nodes.

Sort a Linked List in C++

We will be implementing the simplest sorting algorithm, Bubble Sort, to sort the Linked List in increasing order. This sorting algorithm repeatedly swaps adjacent elements if placed in an unsorted order.

This operation is performed repeatedly until all the elements are at their correct sorted position. This will be implemented as follows:

void sortLinkedList() {
  Node<T> *curr = head, *temp = NULL;
  int t;
  if (head == NULL) {
    return;
  } else {
    while (curr != NULL) {
      temp = curr->next;
      while (temp != NULL) {
        if (curr->info > temp->info) {
          t = curr->info;
          curr->info = temp->info;
          temp->info = t;
        }
        temp = temp->next;
      }
      curr = curr->next;
    }
  }
}

The driver program will be:

int main() {
  LSLL<int> list;
  list.insertAtHead(50);
  list.insertAtHead(45);
  list.insertAtHead(16);
  cout << "Before sorting" << endl;
  list.displayAll();
  cout << "After Sorting: " << endl;
  list.sortLinkedList();
  list.displayAll();
  return 0;
}

Output:

Before sorting
43
65
13
After Sorting:
13
43
65