CODEWITHSUNDEEP
c++sortinglinked-listbubble-sortdoubly-linked-list
121212
121212

Reputation: 9

How to create a bubble sort for a doubly linked list with a swap function?

I'm trying to figure out how to write a member function for DNode called DNode *DNode::bubble() for a DNode *head which can bubble-sort the linked list and return the new head. I want to use a member function void swap(DNode *that) to swap two nodes.

Here's what I have so far regarding the .h and .cpp files:

#ifndef DNODE_H
#define DNODE_H
class DNode {

public:

int key;
DNode *next;
DNode *prev;

void add(int key);
void print();
DNode();
DNode *bubble();
void swap(Dnode *that);
};

#endif

#include "DNode.h"
#include <cstdlib>
#include <iostream>
using namespace std;

void DNode::swap(DNode *that){
DNode *temp = this;
DNode *R1, *L1, *R2, *L2;

}

Dnode *Dnode::bubble(){
DNode *temp = this;
int count = 0;
while(start != NULL){
count++;
start = start->next;
}

for(int i = 0; i < count; i++){

}
}

What I'm having a problem with is the swap function to swap the nodes in the list with just that one parameter.

Upvotes: 0

Views: 712

Answers (1)

user268396
user268396

Reputation: 11996

Well all you need to do is adjust the next and prev members of both, as well as sync up the links from previous & next elements of those:

void DNode::swap(DNode *that) 
{
  // this->prev->next points back to 'this' should become 'that'
  if(this->prev) {
    this->prev->next = that;
  }
  // this->next->prev points back to 'this' should become 'that'
  if(this->next) {
    this->next->prev = that;
  }
  // that->prev->next points back to 'that' should become 'this'
  if(that->prev) {
     that->prev->next = this;
  }
  // that->next->prev points back to 'that' should become 'this'
  if(that->next) {
     that->next->prev = this; 
  }
  // remember whatever 'this' ->next and ->prev point to
  DNode * n1 = this->next, * p1 = this->prev;
  // let 'this' take the position of 'that in the list
  this->prev = that->prev;
  this->next = that->next;
  // let 'that' take the position of the original 'this' in the list.
  that->prev = p1;
  that->next = n1;
}

Alternatively: if you simply want to swap values at a particular logical position in the list then you can also simply exchange the values:

void swap(DNode* that)
{
  int old = this->key;
  this->key = that->key;
  that->key = old;
}

Upvotes: 1

Related Questions