The code below works to sort a singly linked list using class functions.It takes user input into an array, turns that array into a linked list, and then sorts it. I am uncertain on what changes I should make where to have it work for a Double Link List. I know the struct will need a new prev pointer but I don't know how to work that into the bubble sort algorithm This code functions normally to bubble largest down, I'm not so much worried about efficiency right now as seeing the practicality of the sorting. The conversion to double link should only be a few new -> links as far as I am aware and I would like to see what those should be to better understand the fundamentals of bubble sorting and double linked list.
#include <bits/stdc++.h>
using namespace std;
struct Node{
int val;
Node* prev;
Node* next;
Node(int x){
val = x;
prev = NULL;
next = NULL;
}
};
class DoubleLink{
public:
Node* head;
void push(int x){
Node* newnode = new Node(x);
newnode->next = head;
if(head != NULL){
head->prev = newnode;
}
head = newnode;
}
void printList(Node* head){
Node* current = head;
cout<<endl;
while(current != NULL){
cout<<current->val<<" ";
current = current->next;
}
}
int getSize(Node* headref){
int count =0;
while(headref != NULL){
count++;
headref = headref->next;
}
return count;
}
void bubbleSort(Node* headref){
Node* lswap = NULL;
int sz = getSize(headref);
while(sz--){
Node* current = headref;
Node* prv = NULL;
Node* cswap = NULL;
while(current->next != lswap){
Node* after = current->next;
if(current->val > after->val){
current->next = after->next;
after->next = current;
if(prv == NULL)
current=after;
else
prv->next=after;
prv=after;
cswap = current;
}
else{
prv = current;
current=current->next;
}
}
if(cswap==NULL)
break;
else
lswap = cswap;
}
}
};
int main(){
DoubleLink list;
int size;
cout<<"How many numbers"<<endl;
cin>>size;
int numbers[size];
cout<<"Enter numbers"<<endl;
for(int i=0;i<size;i++){
cin>>numbers[i];
}
for(int i=0;i<size;i++){
list.push(numbers[i]);
}
cout<<"first"<<endl;
list.printList(list.head);
cout<<"second"<<endl;
list.bubbleSort(list.head);
list.printList(list.head);
cout<<endl;
}