Bubble Sort On Doubly Linked List | CPP program to sort a doubly linked list using bubble sort ; structure of a node ; Function to insert a node at the beginning of a linked list ; Function to print nodes in a given linked list ; Bubble sort the given linked list ; Checking for empty list ; Driver code ; start with empty linked list ; Create linked list from the array arr [ ] . Created linked list will be 1 -> 11 -> 2 -> 56 -> 12 ; print list before sorting ; sort the linked list ; print list after sorting
#include <iostream> NEW_LINE 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 printList ( struct Node * start ) { struct Node * temp = start ; cout << endl ; while ( temp != NULL ) { cout << temp -> data << " ▁ " ; temp = temp -> next ; } } void bubbleSort ( struct Node * start ) { int swapped , i ; struct Node * ptr1 ; struct Node * lptr = NULL ; if ( start == NULL ) return ; do { swapped = 0 ; ptr1 = start ; while ( ptr1 -> next != lptr ) { if ( ptr1 -> data > ptr1 -> next -> data ) { swap ( ptr1 -> data , ptr1 -> next -> data ) ; swapped = 1 ; } ptr1 = ptr1 -> next ; } lptr = ptr1 ; } while ( swapped ) ; } int main ( ) { int arr [ ] = { 12 , 56 , 2 , 11 , 1 , 90 } ; int list_size , i ; struct Node * start = NULL ; for ( i = 0 ; i < 6 ; i ++ ) insertAtTheBegin ( & start , arr [ i ] ) ; printf ( " Linked list before sorting " printList ( start ) ; bubbleSort ( start ) ; printf ( " Linked list after sorting " printList ( start ) ; return 0 ; }