Double Linked List Add Function

[gameboy1995]

I am writing a program that implements doubly linked lists and am required to add to the front, back, and in between any node in the list. I receive an error stating that I have an invalid null pointer and am confused on where I have made this error for each function.

void GroceryList::addToFront(string itemName, double quantity)
{
	ItemType * ptr=new ItemType;
	ItemType * front=head, *after;

	ptr->name=itemName;
	ptr->qty=quantity;
	
	
	if(isEmpty())
	{
		front=ptr;

		ptr->prev=front;
		ptr->next=NULL;
	}
	else
	{
		after=front->next;

		front=ptr;

		ptr->prev=front;
		ptr->next=after;
	}

	itemCount+=quantity;

	ptr=front=after=NULL;
	
	cout << "Adding an item via addToFront..." << endl;
	printForward();
}

void GroceryList::addToBack(string itemName, double quantity)
{
	ItemType *ptr=new ItemType;
	ItemType *rear=tail;

	ptr->name=itemName;
	ptr->qty=quantity;

	if(isEmpty())
	{
		rear=head;
		
		rear->next=ptr;
		ptr->next=NULL;
	}
	else
	{
		rear->next=ptr;
		ptr->next=NULL;
	}

	itemCount+=quantity;

	delete rear;
	delete ptr;

	ptr=rear=NULL;

	cout << "Adding an item via addToBack..." << endl;
	printForward();
}

void GroceryList::add(string itemName, double quantity, int pos)
{
	ItemType *ptr=new ItemType;
	ItemType *current=head, *after;

	ptr->name=itemName;
	ptr->qty=quantity;

	if(isEmpty())
	{
		current->next=ptr;
		ptr->next=NULL;
	}
	else if(pos==itemCount)
	{
		current=tail;

		current->next=ptr;
		ptr->next=NULL;
	}
	else
	{
		for(int i=0; i<pos; i++)
		{goNext(current);}

		after=current->next;

		current->next=ptr;
		ptr->next=after;
	}

	itemCount+=quantity;

	delete ptr;
	delete current;

	ptr=current=after=NULL;

	cout << "Adding an item via add at position " << pos << "..." << endl;
	printForward();
}

[dhayden]

The tough part here is that any time you add a node, you have to worry about adjusting all the affected prev and next pointers, and the head and tail pointers too. I suggest that you add a private method:

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

Notice here that link is a reference to a next pointer or to head. That way, when change link, you'll be changing the actual link. With this method (and a constructor in ItemType), the rest of it gets easy. For example:

void
GroceryList::addToFront(string itemName, double quantity)
{
    ItemType *ptr = new ItemType(itemName, quantity);
    addAfter(head, ptr);
    cout << "Adding an item via addToFront..." << endl;
    printForward();
}

void
GroceryList::addToBack(string itemName, double quantity)
{
    ItemType *ptr = new ItemType(itemName, quantity);
    if (isEmpty()) {
	addAfter(head, ptr);
    } else {
	addAfter(tail->next, ptr);
    }
    cout << "Adding an item via addToBack..." << endl;
    printForward();
}

[gameboy1995]

Thank you very much. That helped a lot, but is there any way to use this if I am just using the add function which can go to different nodes?

[gameboy1995]

Also when I was testing the addToBack function, I received an access violation error. I wrote the addAfter function as so:

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

Is this where my error is?

[dhayden]

Is this where my error is?

Quite possibly. In your version, line 3 changes link to point to newNode. Then line 4 changes newNode->prev to link, which is now newNode. The effect is the same as newNode->prev = newNode.

Link might point to an existing node. So as a first cut you want to do this:
newNode->next = link;
link = newNode;

Now:
- what should newNode->prev point to?
- Some node's prev pointer might have to change to point to newNode
- What if newNode is the new tail of the list. You'll have to adjust tail.
- What if newNode is the first item in the list (note that in this case link is head).