Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
Sign in to follow this  
Infinite Ammunition

A simple problem with C++ linked lists

Recommended Posts

okay now, for the past week i've been stumped by what should be a very simple college assignment, writing a doubly-linked list class in C++ that has functions for 1) swapping the positions of any two given nodes in a list, and 2) rearranging the nodes so that the list's order is reversed (head becomes foot, etc), with the condition that i may not add nodes, remove nodes or create a temporary list to accomplish this.

i've probably just created the problem by overcomplicating the code for these tasks, but since i'm still not quite sure where i went wrong myself, feel free to be the judge of that in these code samples:

// swap the order of two given nodes in the list
// should handle empty/one-element lists
// and cases involving the head or foot
void dualLinkList::swapNodes(dualLinkNode *node1, dualLinkNode *node2)
{
    dualLinkNode *temp;
    
    // case for an empty list or invalid arguments
    if (isEmpty() || node1 == NULL || node2 == NULL)
    {
        cerr << "ERROR: Null or invalid pointer(s) passed to swapNodes()!";
        cerr.flush(); // ensure immediate error output
        exit(1);
        return;
    }
    
    // case for a one-element list or attempt to swap a node with itself
    else if (hasOneNode() || node1 == node2) return;
    
    // multi-element list case
    // place node 2 in node 1's position
    if (node1->getPrev() == NULL) // head
    {
        node1->getNext()->setPrev(node2);
        head = node2;
    }
    else if (node1->getNext() == NULL) // foot
    {
        node1->getPrev()->setNext(node2);
    }
    else // neither end of the list
    {
        node1->getPrev()->setNext(node2);
        node1->getNext()->setPrev(node2);
    }
    
    // place node 1 in node 2's position
    if (node2->getPrev() == NULL) // head
    {
        node2->getNext()->setPrev(node1);
        head = node1;
    }
    else if (node2->getNext() == NULL) // foot
    {
        node2->getPrev()->setNext(node1);
    }
    else // neither end of the list
    {
        node2->getPrev()->setNext(node1);
        node2->getNext()->setPrev(node1);
    }
    
    // swap the "previous" pointers
    temp = node1->getPrev();
    node1->setPrev(node2->getPrev());
    node2->setPrev(temp);
    
    // swap the "next" pointers
    temp = node1->getNext();
    node1->setNext(node2->getNext());
    node2->setNext(temp);
    
    updateFoot();
}


// swap the order of elements in the list;
// head is swapped with foot,
// head->next is swapped with foot->prev, etc
void dualLinkList::reverseOrder()
{
    updateFoot();
    dualLinkNode *node1 = head, *node2 = foot;
    swapNodes(node1, node2);
    
    while ((node1 != node2) && (node1->getPrev() != node2))
    {        
        if (node1->getNext() != NULL && node2->getPrev() != NULL)
        {
            node1 = node1->getNext();
            node2 = node2->getPrev();
            
            swapNodes(node1, node2);
        }
        else break;
    }
}


// update the address of the foot pointer
void dualLinkList::updateFoot()
{
    // empty list case
    if (isEmpty())
        return;
    
    // multi-element list case
    else if (head->getNext() != NULL)
    {
        foot = head->getNext();
        
        //cout << "\nheh"; // debug
        
        while (foot->getNext() != NULL)
        {
            foot = foot->getNext();
            //cout << "\nheh2 " << foot->getData() << " " << foot; // debug
        }
    }
    
    // one-element list case
    else
        foot = head;
}


// return whether the list has only one node in it
bool dualLinkList::hasOneNode()
{
    // list has only one node, which is head
    if (head->getNext() == NULL)
    {
        foot = head;
        return true;
    }
    
    // list has one or more nodes following head
    else
    {
        updateFoot();
        return false;
    }
}


// return whether the list has no nodes at all
bool dualLinkList::isEmpty() { return (head == NULL); }
here's the code for the node class if you need it too:
// generic class for a node in a doubly-linked list,
// nodes containing 1 item of integer data
class dualLinkNode
{
    public:
        // constructors
        dualLinkNode()
            : prev(NULL), next(NULL), data(0) { }
        dualLinkNode(dualLinkNode* newPrev,
            dualLinkNode* newNext, int newData)
            : prev(newPrev), next(newNext), data(newData) { }
        
        // accessor functions
        dualLinkNode* getPrev() { return prev; }
        dualLinkNode* getNext() { return next; }
        int getData() { return data; }
        
        // mutator functions
        void setPrev(dualLinkNode* newPrev) { prev = newPrev; }
        void setNext(dualLinkNode* newNext) { next = newNext; }
        void setData(int newData)           { data = newData; }
        
        friend class dualLinkList;
        
    private:
        dualLinkNode* prev; // node prior to this node
        dualLinkNode* next; // node following this node
        int data;           // data in this node
};
and for completeness, here is a zip with all the code files for the project (contains some dev-C++ generated stuff, also feel free to ignore untitled2.cpp since it's just blank functions for now)

Share this post


Link to post

Looks like you're getting your pointers confused. What I usually did was grab a clean sheet of paper, write out sample nodes (try using four here), and write a H and a F on them (head and foot). Then step through your code line-by-line and as you do, draw arrows on the sheet of paper.

EDIT:
This is the basic idea:

node1->setNext(node2->getNext());
node2->setPrev(node1->getPrev());
node1->setPrev(node2);
node2->setNext(node1);
node2->getPrev()->setNext(node2);
node1->getNext()->setPrev(node1);

That swaps node1 and node2. Double checked it twice on paper to make sure you don't lose a reference and I can't see anything. I didn't code it, though...too lazy to build a double-linked list or convert your makefile to run right on my box tonight :)

Share this post


Link to post

node1->setPrev(node2);
node2->setNext(node1);


are you sure about doing these two lines? it sounds like you'd always end up with the two swapped nodes being right next to each other and their old links being messed up if you do this

that is the general gist of how swapNodes() works though, granted the way i wrote it it's also supposed to handle cases where one/both of the nodes are at the head or foot (eg. avoids running node1->getPrev()->setNext() if node1 is the head), perhaps there's some issue in the way i approached these checks?

Share this post


Link to post
Infinite Ammunition said:

are you sure about doing these two lines? it sounds like you'd always end up with the two swapped nodes being right next to each other and their old links being messed up if you do this

I suppose I'm assuming nodes will be next to one another, in which case my bad; that code is fishy.

Again, try drawing it out and going for the base case (two nodes not on the end). Then attack the special cases (nodes on the end, only one node in the list, etc). I think I have a fixed solution, but I'm so dang tired right now I won't risk giving it to you.

Share this post


Link to post

In

        if (node1->getNext() != NULL && node2->getPrev() != NULL)
        {
            node1 = node1->getNext();
            node2 = node2->getPrev();
            
            swapNodes(node1, node2);
        }
shouldn't you be assigning node1 from node2->getNext() and node2 from node1->getPrev()? Since you are swapping their next/prev references in the swapNodes() function, getNext() of the previous head and getPrev() of the previous foot will point to null.

Share this post


Link to post
Infinite Ammunition said:

anything's a step in the right direction at this point, i'm sure if your suggestion doesn't work i'll find out the hard way and be ready to yell :p

Yeah, I've been there before too. My other idea was to use two temporary nodes to hold the prev and next of the original two nodes, then do the swapping since you should then have handles on all six nodes that need updating (node1, node2, node1's prev, node1's next, node2's prev, node2's next).

It's been a very long time since I've used double linked lists.

Share this post


Link to post

i'm not quite sure what you mean by "assigning from" there jodwin (if you mean "assign to" or "set to" then do tell) but the idea behind node1 and node2 in reverseOrder() is basically:

1) node1 is an iterator going from the head of the list to the foot
2) node2 is the same, but iterating from the foot to the head
3) if they collide (in a list with an odd number of elements) or cross each other (in a list with an even number of elements) the function stops

just tried the change i think you were suggesting though, changing that code to this:

        if (node1->getNext() != NULL && node2->getPrev() != NULL)
        {
            node1 = node2->getNext();
            node2 = node1->getPrev();
            
            swapNodes(node1, node2);
        }
the results seem to be exactly the same after compiling and running with this change (still swaps only the head and foot)

Share this post


Link to post

Are you required to use "swapNodes" to reverse it? If not, here's a working version that doesn't need that function that I whipped up for you (I purposely did it in C so that it'll hopefully get you to examine it).

Share this post


Link to post
Infinite Ammunition said:

i'm not quite sure what you mean by "assigning from" there jodwin (if you mean "assign to" or "set to" then do tell) but the idea behind node1 and node2 in reverseOrder() is basically:

1) node1 is an iterator going from the head of the list to the foot
2) node2 is the same, but iterating from the foot to the head
3) if they collide (in a list with an odd number of elements) or cross each other (in a list with an even number of elements) the function stops

just tried the change i think you were suggesting though, changing that code to this:

        if (node1->getNext() != NULL && node2->getPrev() != NULL)
        {
            node1 = node2->getNext();
            node2 = node1->getPrev();
            
            swapNodes(node1, node2);
        }
the results seem to be exactly the same after compiling and running with this change (still swaps only the head and foot)

You also have to change them around in the if-clause: node2->getNext() and node1->getPrev(). The reason is in the swapNodes()-function: You first change node1 and node2 in swapNodes around so that the previous head (node1) becomes tail and foot (2) becomes head. After switching them around, you also change their previous and next node references:

    // swap the "previous" pointers
    temp = node1->getPrev();
    node1->setPrev(node2->getPrev());
    node2->setPrev(temp);
    
    // swap the "next" pointers
    temp = node1->getNext();
    node1->setNext(node2->getNext());
    node2->setNext(temp);
So now the node1 in reverseOrder() points to the tail node and node2 to the head node. Obviously changing the "next" and "previous" pointers affects the node1 and node2 in reverseOrder() too, so you have node1, the new foot, pointing to the "next", which is null, and node2, the new head, pointing the the "prev", which is also null. That is why you have to switch them around, so that when you get the new node1, it's the next of node2, your new head.

edit: If it's still unclear what I'm saying, think of it this way: Both nodes 1 and 2 are containers for data X (data X being "node->data" or equivalent). In the swapNodes you are swapping around these containers for data in the list, so where ever you refer to the container you need to take that into account. If you swapped only the data inside the container, you wouldn't have to do the change I mentioned, because node1 would still be the container in the head and node2 still the container in the foot, only the data they refer to would have been swapped.

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  
×