Help With Doubly-Linked Lists

[alanthreonus]

In the test case I'm using, I'm inserting 3 and a 5 into my list, and then I remove both of them. If I use the method removeFront both times, everything goes fine, but if I use removeFront and then removeBack, I get a memory error.

I think what's happening is that when removeBack is called on a list with one element, the list loses track of its first element, causing the destructor to delete things twice, but my efforts to fix this have proved futile, so I'm not sure if that's what's actually happening. Could someone help me out? Here's my code:

[content removed]

[jfosizzle]

alanthreonus,
the problem i see with your code is that, when inserting a node, you only set one of next or prev.
void Dlist<T>::insertFront(T *o)
{
node *np = new node;
np->o = o;
np->prev = NULL;
np->next = first;

if (isEmpty())
first = last = np;

else
{
first->prev = np;
//here you should be setting (np->next = first;)
first = np;
}
}
the comment in the code shows what needs to be done.
you are only enabling a singly-linked list, and with your code you are inconsistent in which (next or prev) will be the link. you should also apply a similar fix in insertBack().

[alanthreonus]

I already set np->next = first at the the top, so why would I have to set it again?

[jfosizzle]

the way i did it is i established at the top that np->next = NULL, as an invariant. then down in the else block i set my np->next. if that's not working, idk...

[alanthreonus]

The constructor sets first as NULL, so np->next = first at the top should set the correct value regardless of whether the list is empty or not.

I actually got this to work by making removeAll() use removeBack() instead of removeFront(), but I'm not exactly sure why that makes a difference.

[D80DSL3A]

Is your test case working? I see some errors in your removeFront() and removeBack()
In removeFront() line 53 is good but first->prev would then still be pointing to the node being deleted. You need to assign first->prev = NULL there.
Similarly, last->next = NULL; belongs in removeBack()

Why do the remove functions return a pointer to the data just deleted? Have you tried de-referencing the return value? I think maybe go BOOM!

[alanthreonus]

I thought it was working, but apparently it isn't, and even after I added the lines you suggested, it still doesn't work. Now I'm more confused than ever.

And the remove functions return a pointer so I can insert the data into another list if need be.

[jfosizzle]

you're right, fun2code, but i had to do
"if(first)first->prev=NULL;"
due to the fact that if first is set to the next, which is null, it will not have a prev to set to null.

[D80DSL3A]

@alanthreonus. I didn't look carefully enough at what your node structure is doing. The data isn't stored in the node, only a pointer to it is. Therefore the data isn't being deleted along with the node in a remove function, so it's OK after all.
I'm used to building lists where the data IS stored in the list, not outside of it.

@jfosizzle: Good point. Similarly you would need if(last)last->next = NULL; in removeBack()

EDIT: More details come to mind now. When the last node is removed in either remove function, the pointer to the other end must = NULL too.
Actually looking at the code for my own list now (instead of going off the top of my head), I have:
In removeFront():

if( head )
	head->prev = NULL;
else
	tail = NULL;// when last node popped 

In removeBack():

if( tail )
	tail->next = NULL;
else
	head = NULL;// when last node popped 

A question for the experts here.
We're building a doubly linked list with functions to add or remove nodes at either end here.
Doesn't that make it a deque (double ended queue) container?

[alanthreonus]

I think that last bit of code was just what I needed, and it seems so obvious now. Thanks!