sort() for double linked list

[vbx_wx]

Hello,can anybody help me implement the sort() function of a double linked list. The node`s of the list contains objects of type Person:

class Person {
   int age;
   string name;
   string adress;
};

And i want to sort all the Person`s by age.I tried implementing bubble sort,but I dont think i did it good:

void sort()
	{
		Person* pp;

		for(int i = 0; i < (nr - 1); i++)
		{
			for(int j = 1; j < nr; j++)
			{
				if(pp[j].getAge() > pp[j + 1].getAge() )
				{
					Person temp;
					temp = pp[j];
					pp[j] = pp[j + 1];
					pp[j + 1] = temp;
				}
			}
		}
	}

[Ancient Dragon]

What you posted is not a double linked list but just an array of People classes. Post the node structure of the linked list you are using.

The j loop starting on line 7 should start at (i+1), not 1. There is no reason to compare anything from 0 up to and including the value of i because they have already been sorted

for(int i = 0; i < (nr-1); i++)
{
   for(int j = i+1; j < nr; j++)
   {
      // etc
   }
}

The way I sort linked lists is to swap just the data, not the entire nodes, so that the link pointers remain in tact. It becomes even easier if you put the data in a structure so that you can just swap structures instead of individual data members.

The swap algorithm needs to iterate through the linked list.

struct node
{
   node* next;
   node* prev;
   Person p;
};

void sort(node* head)
{
   node* n1;
   node* n2;
   for(n1 = head; n1->next != NULL; n1 = n1->next)
   {
       for( n2 = n1->next; n2 != NULL; n2 = n2->next)
       {
          // swap data here if necessary
       }
   }
}

[Taywin]

Doubly linked list should never point to a NULL. The sort method above needs a little modification.

struct node {
  node* next;
  node* prev;
  Person p;
};

void sort(node* head) {
  node* n1;
  node* n2;
  for(n1 = head; n1->next != head; n1 = n1->next) {
    for( n2 = n1->next; n2 != head; n2 = n2->next) {
          // swap data here if necessary
    }
  }
}

For swapping, it is tricky. You could do somewhat like this...

X1 = currPtr->previoius;
  X2 = currPtr->next->next;
  currNext = currPtr->next;
  currNext->previous = currPtr->previous;
  currPtr->previous = currPtr->next;
  currPtr->next = currNext->next;
  currNext->next = currPtr;
  X1->next = currPtr->previous;
  X2->previous = currPtr;

// graphical explanation is below...
// original state
//     X1-> <-curr-> <-currNext-> <-X2
// currNext->previous = currPtr->previous;
//     X1-> <-curr----,           <-X2
//       \             \         /
//        '-------------currNext->
// currPtr->previous = currPtr->next;
//     X1-> ,-curr--------,        <-X2
//       \   \..........,  \      /
//        '-------------currNext->
// currPtr->next = currNext->next;
//     X1->  -curr---------------> <-X2
//       \   \..........,         /
//        '-------------currNext->
// currNext->next = currPtr;
//         /''''''''''''\
//     X1-' <-currNext-> <-curr-> .-X2
//                     \........./
// X1->next = currPtr->previous;
//     X1-> <-currNext-> <-curr-> .-X2
//                     \........./
// X2->previous = currPtr;
//     X1-> <-currNext-> <-curr-> <-X2

Hope this help...

[dusktreader]

Doubly linked list should never point to a NULL.

That's not true. The HEAD node of a doubly linked list (DLL) should have its PREV pointer set to NULL. The TAIL node of a DLL should have its NEXT pointer set to NULL. Otherwise, how could you determine if you were at the head or tail when you were traversing the list.

[Taywin]

Hmm... I may be thinking about circular doubly linked list. I implemented only that kind of doubly linked list because I don't need to carry 2 nodes (head or tail). Also, it is very simple how to find out when you are at the end is that when your next node is 'head'. Nothing magical there.

[dusktreader]

Hmm... I may be thinking about circular doubly linked list. I implemented only that kind of doubly linked list because I don't need to carry 2 nodes (head or tail). Also, it is very simple how to find out when you are at the end is that when your next node is 'head'. Nothing magical there.

Doubly linked rings also have the advantage in that you don't need any special cases for insertion or deletion. It is always the same mechanics regardless of where it takes place. The only thing you have to manage is the head pointer.

However, academic exercises commonly call for lists over rings to inflict additional suffering upon the students.