Doubly linked list: swap two adjacent nodes without a temp variable

201 views Asked by At

This code is C++ - in so much as it uses classes/objects. In reality it is all just C, since I was playing around, implementing a doubly linked list without using the STL.

The language shouldn't matter. What is bothering me is that I used a temporary variable.

Can anyone improve this code so that no temporary variable is needed? It is a simple bubble sort, but what concerns me is swapping two adjacent nodes of a doubly linked list.

class LinkedListItem *linkedListItem;
bool swapped;

do
{
  swapped = false;

  for (linkedListItem = uniqueWords.GetHead();
       linkedListItem != NULL;
       linkedListItem = linkedListItem->GetNext())
  {
     if (linkedListItem->GetNext() != NULL)
     {
         if (linkedListItem->GetWordCount() < linkedListItem->GetNext()->GetWordCount())
         {
            // Swap items to bubble smaller value up.

            // Rats!! I can't seem to do it by juggling pointers without a temp variable :-(
            // ToDo: figure out how!
            class LinkedListItem *itemAfterNext;
            if (linkedListItem->GetNext() == NULL)
               itemAfterNext = NULL;
            else
               itemAfterNext = linkedListItem->GetNext()->GetNext();

            if (uniqueWords.GetHead() == linkedListItem)
               uniqueWords.SetHead(linkedListItem->GetNext());

            if (uniqueWords.GetTail() == linkedListItem->GetNext())
               uniqueWords.SetTail(linkedListItem);

////--------- start swap -----------  
            if (linkedListItem->GetPrev() != NULL)
                linkedListItem->GetPrev()->SetNext(linkedListItem->GetNext());

            if (linkedListItem->GetNext()->GetNext() != NULL)
                linkedListItem->GetNext()->GetNext()->SetPrev(linkedListItem);

                 linkedListItem->GetNext()->SetPrev(linkedListItem->GetPrev());
            linkedListItem->GetNext()->SetNext(linkedListItem);

            linkedListItem->SetPrev(linkedListItem->GetNext());
            linkedListItem->SetNext(itemAfterNext);
////--------- end swap -----------

            swapped = true;
         }
     }
   }
} while (swapped == true);
0

There are 0 answers