Printing a double linked list backwards

[gameboy1995]

Hello everybody, I am trying to write a function to print my list backwards yet my compiler is giving me errors about accessing the memory or that there is nothing for it to access. I am able to have the compiler print the title part of the function and the empty case, but not the case when the list has nodes.

 void GroceryList::printBackward() const
 {
	ItemType *rear=tail;
	int count=1;

	cout << "------ Grocery List (item:quantity) ------" << endl;
	if(isEmpty()) cout << "You do not have any item.";

	while(rear!= head)
	{
		cout << count << ") " << rear->name << ": " << rear->qty << endl;
		goPrevious(rear);
		count++;
	}
	cout << endl;
 }

[kevinkjt2000]

More of the code will be needed to answer your question. I definitely would like to see goPrevious
If it is not too large, can you copy and paste the errors that you see to here?

[gameboy1995]

Here is the code for goPrevious:

void GroceryList::goPrevious(ItemType * & curr) const
{curr=curr->prev;}

my error is as follows:

Unhandled exception at 0x011B7018 in CPSC 131 Project 1.exe: 0xC0000005: Access violation reading location 0x00000020.

I am prompted to break the program or continue.

[kevinkjt2000]

I would say your error lies somewhere else in class GroceryList printBackward looks fine except for skipping the head element of every list on a backwards traversal.
The error is most likely somewhere in one of addItem, removeItem, or the constructor. It seems as if tail has an invalid memory address for some reason.
If the whole code is not too large, I would be happy to look through it to see if I can spot where this error might be.

[gameboy1995]

Here is a Microsoft word file link to see the code for the whole program. You will be able to see the code but not edit it on there. If you would like to edit on there, then please let me know.

https://drive.google.com/file/d/0BzQExfglA9-mTExwdHg0a2pTWjg/view?usp=sharing

[kevinkjt2000]

From what little I read, I believe the linked list is circular. Meaning that tail->next == head should always be true. Correct me if I am wrong on that.

GroceryList::addAfter looks very suspicious to me.
if(link==head||link==tail->next) == if(link==head)???

1 2 3

link=newNode; newNode->prev=link; newNode->next=NULL;

link would now be == to newNode and so would head because link is passed by reference now newNode->prev is == to newNode newNode->next is set to NULL

This code would create a one element list everytime if head is the first parameter.

Usually, when I help students with a similar program at my university, I draw pictures of what the linked list looks like after every step of the code. The visuals are very helpful in debugging this type of code. I suggest that you draw some pictures of what is currently happening in GroceryList::addAfter, and also draw pictures of what you would like to happen instead. If you need example pictures showing what I mean, I can dig out my tablet and upload some images for you. Just let me know :)

[gameboy1995]

The list is not supposed to be circular at least to my knowledge from what the instructions that were provided state.

[kevinkjt2000]

GroceryList::addAfter is still a suspicious fellow even if his world is not circular. How are those pictures going?

[gameboy1995]

They are helping me understand how the function groceryList::addAfter is moving through the list but at the same time I don't necessarily see an error there but my compiler states that the error occurs when I try to use addAfter for addToBack.

[cire]

addAfter never updates tail under any circumstance where tail is not fed to the function. Does that seem right to you?

[kevinkjt2000]

The list is becoming invalid after a call to groceryList::addAfter when the first argument is head

head is the pointer to the start of your linked list. head->prev should always be NULL since the list is not circular. head->next is always the second node in the list, which might be NULL if there is one element. If there were zero elements head would be NULL, NULL->anything leads to catastrophe (null pointer runtime related errors).
For some reason it helps me to list laws that I know should hold true. (Probably because I like proofs, but I digress).
head is crucial to the class groceryList.

Here is what I think the function might should look like based on what you have said so far:

void GroceryList::addAfter(ItemType *& link, ItemType *newNode)
{ 
    if(link==NULL) 
    { //if the link passed in is NULL, an error should probably be thrown
     //or maybe the newNode should be added just before head
     //but I am going to just assume that the list is empty
        head=newNode;
        tail=newNode;
        newNode->prev=NULL;
        newNode->next=NULL; 

    } 
    else 
    { 
        newNode->prev=link;
        newNode->next=link->next; 
        link->next=newNode;
        if(tail == link)
        {
            tail = newNode;
        }
    }
}

Edit: As a side note I would like to say that pointers passed by reference is a bit of a headache.

[gameboy1995]

What you provided helped to add the item to the back of the list but now the actual print backward function skips the head just as you had said it would. It also has an issue with the add function itself, but for that I may be able to fix it myself. Thank you very much for your help!

[gameboy1995]

Actually the print backword function continues to skip the head and I have tried changing the conditions for the loop to fix this but that does not help. It has only caused the program to either print nothing or only print one item.

[Gamer2015]

First off I'm glad to see the "const" decleration here :)

Actually the print backword function continues to skip the head

you might want to print as long as rear != head->prev
I wonder why this topic is marked solved when this problem is not solved?

void GroceryList::printBackward() const
{
	ItemType *rear=tail;
	int count=1;

	cout << "------ Grocery List (item:quantity) ------" << endl;
	if(isEmpty()) cout << "You do not have any item.";

	while(rear != nullptr)
	{
		cout << count << ") " << rear->name << ": " << rear->qty << endl;
		goPrevious(rear);
		count++;
	}
	cout << endl;
}

It's funny to see 2 guys who take the same course posting questions about the double linked list :b
http://www.cplusplus.com/forum/general/161368/ - split

[dhayden]

Let's look at addAfter() again. Remember, here's what I said in another thread about what it should do:

// Add newNode after link, which is either head or an item's next pointer
void GroceryList::addAfter(ItemType *&link, ItemType *newNode)

It's perfectly valid for link to be NULL. That just means that you're inserting at the end of the list.

Here is your implementation of addLink:

void GroceryList::addAfter(ItemType *& link, ItemType *newNode)
{ 
if(link==head||link==tail->next) {
    link=newNode; 
    newNode->prev=link; 
    newNode->next=NULL; 
} else { 
    newNode->next=link->next->next; 
    newNode->prev=link;
    link->next=newNode;
}
}

After line 5, newNode->prev == newNode. That's not what you want.
Suppose you insert a new item at the head of an existing list of 10 items. Line 4 will point head to the new node and poof! You've dropped all 10 existing items.

Here is what I had in mind for addAfter:
// Add newNode after link, which is either head or an item's next pointer
void

GroceryList::addAfter(ItemType *&link, ItemType *newNode)
{
    if (link) {
        // adding at the beginning or middle of the list.
        newNode->next = link;
        newNode->prev = link->prev;  // newNode now points forward and back correctly
        link->prev = newNode;
        link = newNode;  // remember, link is a reference to head or a "next" pointer.
    } else {
        // link was null. That means we're adding a new tail.
        newNode->next = link;
        newNode->prev = tail;  // works whether tail is NULL or a node.
        tail = link = newNode;
    }   
    itemCount += newNode->qty;
}