Infinite Ammunition Posted April 22, 2008 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) 0 Share this post Link to post
Remilia Scarlet Posted April 22, 2008 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 :) 0 Share this post Link to post
Infinite Ammunition Posted April 22, 2008 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? 0 Share this post Link to post
Remilia Scarlet Posted April 22, 2008 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 thisI 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. 0 Share this post Link to post
Infinite Ammunition Posted April 22, 2008 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 0 Share this post Link to post
Jodwin Posted April 22, 2008 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. 0 Share this post Link to post
Remilia Scarlet Posted April 22, 2008 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. 0 Share this post Link to post
Infinite Ammunition Posted April 22, 2008 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) 0 Share this post Link to post
Remilia Scarlet Posted April 22, 2008 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). 0 Share this post Link to post
Jodwin Posted April 22, 2008 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. 0 Share this post Link to post