double linked lists

[Deliverance]

Hey guys, I'm trying to write a double linked class, and am having some troubles on operations that I can do to it.

So far I have implemented the following:
-output contents of list from both the head and tail of list
-add at head of list

-AddinOrder (having some problems)
If it is the first element, I can add it at the head, if it's greater than the element at the tail, I can add it there, but when adding in the middle somewhere, I am getting an unexpected result. I am trying to test this by adding in order exclusively (i never call AddatHead from the switch) and then plugging in a series of strings (in order).

Now, when i try to add a string that's not the first, but before the last, I get the following: As soon as I display the addinorder string, it is displaying me the contents of the list over and over again.

I'm sure it's a logic error that I'm overlooking, i'm going to see what I can do in the meantime with it, perhaps someone might point me in the right direction...

here is my listnode declaration

class DListNode 
{
	friend class DList; // List needs to access private data
	private:
		string sWord;
		DListNode* plnNext;
		DListNode* plnPrev;
	public:
		DListNode() : sWord(""), plnNext(NULL), plnPrev(NULL) { }
		DListNode(string &rsData ) : sWord(rsData ), plnNext(NULL), plnPrev(NULL) { }
};

and my list class:

class DList {
	private:
		int nNumItems;
		DListNode* plnHead;
		DListNode* plnTail;
	public:
		DList()  {   nNumItems= 0; plnHead = NULL; plnTail = NULL; }
		void AddAtHead(string &rsNewData );
		void OutputAllRecordsHead(); 
		void OutputAllRecordsTail();
		void AddInOrder (string & rsNewData);
};

Descoped methods of listclass:

void DList::AddAtHead(string& rsNewData) {
	DListNode* plnNew = new DListNode(rsNewData);
	plnNew-> plnNext = plnHead;
	if (plnHead != NULL) 
		plnHead-> plnPrev= plnNew;
	else plnTail = plnNew;
	plnHead= plnNew;
	++nNumItems ;
}

void DList::AddInOrder (string & rsNewData) 
{
	if (plnHead == NULL || rsNewData > plnHead->sWord)
	{
		AddAtHead(rsNewData);
		return;
	}
	if(rsNewData > plnTail->sWord)
	{
		plnTail->plnNext = plnNew;
		plnNew->plnNext = NULL;
		plnNew->plnPrev = plnTail;
		++nNumItems;                        
	}
	else
	{
		DListNode* plnCurr = plnHead;
		DListNode* plnNew = new DListNode(rsNewData);
	
		while(rsNewData < plnCurr->sWord)
			plnCurr = plnCurr->plnNext;
		
		plnNew->plnPrev = plnCurr;
		plnCurr->plnNext = plnNew;
	
		//now to assing the next value to plnNew
		plnCurr = plnTail;
		while(rsNewData > plnCurr->sWord)
			plnCurr = plnCurr->plnPrev;
		plnNew->plnNext = plnCurr;
		plnCurr->plnPrev = plnNew;
		++nNumItems;
	}
}

void DList:: OutputAllRecordsHead() {
	DListNode * plnCurrent = plnHead;
	while (plnCurrent != NULL) {
		cout << plnCurrent-> sWord << endl;
		plnCurrent = plnCurrent->plnNext;
	}
	cout << "Total number of items : " << nNumItems << endl;
}

void DList:: OutputAllRecordsTail() {
	DListNode * plnCurrent = plnTail;
	while (plnCurrent != NULL) {
		cout << plnCurrent-> sWord << endl;
		plnCurrent = plnCurrent->plnPrev;
	}
	cout << "Total number of items : " << nNumItems << endl;
}

I have a feeling that by re-declaring plnCurr to point to tail, I might be mixing up a couple of things, but from my understanding, plnCurr is pointing to a data block which already has a pointer to it, so I am just accessing that data through plnCurr, change the values, and then I can move around with plnCurr and the changes at the data block that plnCurr was pointing to is kept.

Am I way off on this one? Any help is appreciated.

[teknomage1]

I think you made it a bit too complicated. The only case you have to handle explicitly is adding a node to the end. A simple while loop should take care of the rest.

while( plnCurr->sWord < newWord ){
    if( plnCurr->plnNext = NULL ){ //handle case of last node
         break;
    }
    plnCurr = plnCurr->plnNext;
}
DListNode* plnNew = new DListNode(rsNewData);
plnNew->plnPrev = plnCurr;
plnNew->plnNext = plnCurr->next;
plnCurr->plnNext = plnNew;

EDIT:Arg, I was off by one!

[teknomage1]

Alright so obviously the last one didn't work since it always added the new item one node to the right of where it should have gone. I think this one has all the right moves. And yeah I guess inserting at the front is a special case as well as inserting at the back.

//okay so I guess you can run off the left side...
if( plnHead == NULL || rsNewData > plnHead->sWord ){
    AddAtHead(rsNewData);
    return;
}
bool finalNode = 0; //this will test for the null case on the right
while( plnCurr->sWord < newWord ){
    if( plnCurr->plnNext = NULL ){ //handle case of last node
         finalNode = 1;
         break;
    }
    plnCurr = plnCurr->plnNext;
}
//avoid the off by one error by shifting left one unless 
//it should be the last item
if(!finalNode){
  plnCurr = plnCurr->plnPrev;
}
DListNode* plnNew = new DListNode(rsNewData);
plnNew->plnPrev = plnCurr;
plnNew->plnNext = plnCurr->next;
plnCurr->plnNext = plnNew;

[Deliverance]

Originally Posted by teknomage1

if( plnHead == NULL || rsNewData > plnHead->sWord ){
AddAtHead(rsNewData);
return;
}
bool finalNode = 0; //this will test for the null case on the right
while( plnCurr->sWord < newWord ){
if( plnCurr->plnNext = NULL ){ //handle case of last node
finalNode = 1;
break;
}
plnCurr = plnCurr->plnNext;
}
//avoid the off by one error by shifting left one unless
//it should be the last item
if(!finalNode){
plnCurr = plnCurr->plnPrev;
}
DListNode* plnNew = new DListNode(rsNewData);
plnNew->plnPrev = plnCurr;
plnNew->plnNext = plnCurr->next;
plnCurr->plnNext = plnNew;[/code]

1. I may not have been clear as to what I wish to do with this function, AddInOrder is to keep adding a listnode every time it is invoked, and place the listnode in aplhabetical order based on the contents of it's sWord.

example:
input 1: apple
input 2: banana
input 3: dog
input 4: cake

OutputAllRecordsHead (sample output):
apple
banana
cake
dog

2. Those three lines (quoted in bold) seem a little off to me....so what we're saying is new's previous is current (true if new is greater than every other string in the list)...
New's next is current's next....current's next is new?

that doesn't make much sense to me....New's next if it is the largest should be NULL, current's next is pointing to new...

I think the way you envisioned it, AddinOrder was adding at the tail of the list so my output would be in order inputted, partially true, but it's being added based on the string value...

I was thinking something like this would work, but when I try to place a listnode item in the middle, it crashes out on me.

Here is an update of what I have so far, i think it's getting closer but i still have a logic error that I'm not catching:

#include <iostream>
#include <math.h>
#include <string>
using namespace std;

class DList;			// forward declaration

class DListNode 
{
	friend class DList; // List needs to access private data
	private:
		string sWord;
		DListNode* plnNext;
		DListNode* plnPrev;
	public:
		DListNode() : sWord(""), plnNext(NULL), plnPrev(NULL) { }
		DListNode(string &rsData ) : sWord(rsData ), plnNext(NULL), plnPrev(NULL) { }
};


class DList {
	private:
		int nNumItems;
		DListNode* plnHead;
		DListNode* plnTail;
	public:
		DList()  {   nNumItems= 0; plnHead = NULL; plnTail = NULL; }
		void AddAtHead(string &rsNewData );
		void OutputAllRecordsHead(); 
		void OutputAllRecordsTail();
		void AddInOrder (string & rsNewData);
};

void DList::AddAtHead(string& rsNewData) {
	DListNode* plnNew = new DListNode(rsNewData);
	plnNew-> plnNext = plnHead;
	if (plnHead != NULL) 
		plnHead-> plnPrev= plnNew;
	else plnTail = plnNew;
	plnHead= plnNew;
	++nNumItems ;
}

void DList::AddInOrder (string & rsNewData) 
{
	DListNode * plnCurr = plnHead;

	if (plnHead == NULL || rsNewData > plnHead->sWord)
	{
		AddAtHead(rsNewData);
		return;
	}
	bool finalNode = 0; //this will test for the null case on the right
	while( plnCurr->sWord < rsNewData )
	{
	    if( plnCurr->plnNext = NULL )
		{ //handle case of last node
			finalNode = 1;
			break;
		}
    plnCurr = plnCurr->plnNext;
	}
	if(!finalNode)
		plnCurr = plnCurr->plnPrev;
	DListNode* plnNew = new DListNode(rsNewData);
	plnNew->plnPrev = plnCurr;
	plnCurr->plnNext = plnNew;
	plnNew->plnNext = plnCurr->plnNext->plnNext;
}

void DList:: OutputAllRecordsHead() {
	DListNode * plnCurrent = plnHead;
	while (plnCurrent != NULL) {
		cout << plnCurrent-> sWord << endl;
		plnCurrent = plnCurrent->plnNext;
	}
	cout << "Total number of items : " << nNumItems << endl;
}

void DList:: OutputAllRecordsTail() {
	DListNode * plnCurrent = plnTail;
	while (plnCurrent != NULL) {
		cout << plnCurrent-> sWord << endl;
		plnCurrent = plnCurrent->plnPrev;
	}
	cout << "Total number of items : " << nNumItems << endl;
}

void main (void) {

	DList  MyWords;
	string word;
	char choice = '1';

	while (choice != '5') {
		cout << "\nChoose 1 to add string to head of list - deprecated once addinorder is complete";
		cout << "\nChoose 2 to display from head of list";
		cout << "\nChoose 3 to display from tail of list";
		cout << "\nChoose 4 to delete from list";
		cout << "\nChoose 5 to add string in order ";
		cout << "\nChoose 6 to quit:  ";
		cin >> choice;

		switch (choice) {
			case '1':	cout << "\nEnter string to insert: ";
						cin >> word;
						MyWords.AddAtHead(word);
						break;
			case '2':   MyWords.OutputAllRecordsHead();
				        break;
			case '3':   MyWords.OutputAllRecordsTail();
				        break;
                                      case '4':   cout <<"Not written yet..." << endl; break;
			case '5':   cout << "\nEnter string to insert: ";
						cin >> word;
						MyWords.AddInOrder(word);
						break;
			case '6':	cout <<"Goodbye";
						break;
			default:	cout << "\nInvalid selection........try again......";
		}
	}
}

[Deliverance]

...Just a little snippet to my last post: I would need 3 cases to make this work:

1. If the word is less than the word at plnHead addatHead
2. If the word is larger than the word at plnTail addatTail
3. If it is in between....plug it in and adjust the pointers to add this guy somewhere in our list

[teknomage1]

Originally Posted by deliverance

New's next is current's next....current's next is new?

that doesn't make much sense to me....New's next if it is the largest should be NULL, current's next is pointing to new...

Remember that current's next is NULL if currentis the last, so if new goes after current, it inherits current's NULL next value, making it properly the end of the list. If it goes in the middle it's properly inserted into the chain.

If the list is:
 apple
 banana
 dog

And we want to insert cat it looks like this:
 is apple > cat? no
  next node (banana)
 is banana > cat? no
  next node (dog)
 is dog > cat? yes

 previous node (banana)

 cat previous = banana
 cat next = banana's next (dog)
 banana's next = cat

List:
 apple
 banana
 cat
 dog

[Deliverance]

I understand what you're saying now, had to write it down on paper and go through it...Your solution works nicely, I just had to switch the if comparison around, I kept getting an execution error because plnCurr was being assigned to plnCurr->plnNext even if Next was NULL. Thanks for the help techno

void DList::AddInOrder (string & rsNewData) 
{
	DListNode* plnCurr = plnHead;
	DListNode* plnNew = new DListNode(rsNewData);

	if (plnHead == NULL || rsNewData < plnHead->sWord)
	{
		AddAtHead(rsNewData);
		return;
	}
	bool finalNode = 0; //this will test for the null case on plnCurr->plnNext
	while( plnCurr->sWord < rsNewData)
	{
	    if( plnCurr->plnNext != NULL )
			plnCurr = plnCurr->plnNext;
		else
		{
			finalNode = 1;
			break;
		}
	}

	if(!finalNode)
		plnCurr = plnCurr->plnPrev;

	plnNew->plnPrev = plnCurr;
	plnNew->plnNext = plnCurr->plnNext;
	plnCurr->plnNext = plnNew;
}

[teknomage1]

No prob, I had to work it out on paper too!