Double ended linked list remove node

[Whorse]

I'm attempting to add a Remove(Class position); function to my double ended linked list, however I'm struggling. Could anyone provide any tips or code to get me started? It's my last function before finishing and it's doing my head in!

[ne555]

[A] <-> [B] <-> [C]
[A] <-> [C]  [B]

Suppose that you got a pointer to the cell you want to delete (by instance B).
You need to adjust the links, from the previous and next cell.

A = p->prev;
C = p->next;
A->next = C;
C->prev = A;

[Whorse]

...

[PiMaster]

Sort of, but remove line 4 and use position instead of temp. You might also want to keep track of a size variable.

Also, when is this ever equal to NULL?

[Whorse]

...

[simeonz]

If you initialize in the constructor of ListElement the links to the next and previous node with NULL, which is a good idea, then you can apply the following.

~ListElement ()
{
	if ( Previous() ) // guarding
		Previous()->mNext = Next();
	if ( Next() ) // guarding
		Next()->mPrev = Previous();
}

EDIT: Copy pasted some of your code and forgot to correct my version for use in class scope.
Then simply:

void Remove(ListElement *position)
{
	delete position;
}

No matter how you choose to implement the method Remove, don't forget the guarding conditions or you will end up with seg. faults.

Regards

EDIT: The above is ok, but add the conditions that guard against NULL and skip the position = NULL part. It does nothing, because it only assigns to a local variable. The destructor method IMHO is still somewhat preferable, because it guarantees that a node is unlinked from the list before it is destroyed. It is more robust.

[Whorse]

What exactly is temp in the destructor and where is it created?

[simeonz]

Made a mistake, but apparently corrected it too late.

[Whorse]

Thank you simeonz, that was exactly what I was looking for!

[Whorse]

Hey everyone, I've finally reached the end of this assignment, and would like one last additional piece of information.

At the moment, I'm using these functions but with different guarding nodes due to runtime errors I get. It's working well, but at the moment I'm need to work on a function to remove my self contained node class from main.

It needs to remove nodes from the entire list then deallocate itself.

At the moment my remove function looks like this:

	void DestroyList()
	{
		ListElement *iter = this;

		for ( ; iter->mNext != NULL; iter = iter->mNext)
		{
			if(mPrev && mNext)
			{
				mPrev->mNext = mNext;
				mNext->mPrev = mPrev;
			}
		}

		for ( ; iter->mPrev != NULL; iter = iter->mPrev)
		{
			if(mPrev && mNext)
			{
				mPrev->mNext = mNext;
				mNext->mPrev = mPrev;
			}
		}
                delete this;
	}

I'm attempting to remove all the nodes on the right, then all the nodes on the left, and then delete the list itself since it was assigned with new in main(). Any hints where I'm going wrong?

Cheers!

[ne555]

	void DestroyList()
	{
		ListElement *iter = this;

		for ( ; iter->mNext != NULL; iter = iter->mNext)
		{
			if(mPrev && mNext) //you never change mPrev or mNext
			{
				mPrev->mNext = mNext;
				mNext->mPrev = mPrev;
			}
		}

		for (/*iter = this*/ ; iter->mPrev != NULL; iter = iter->mPrev) //so you don't go back unnecessary
		{
			if(mPrev && mNext)
			{
				mPrev->mNext = mNext;
				mNext->mPrev = mPrev;
			}
		}
                delete this; //dangerous
	}

You don't delete anything except the caller node (and if it was not dynamic allocated, crash).

Stop erasing your posts. Others could learn from that.

Edit: it is the last statement, but I don't know if it is safe to explicit destroy you.

[Whorse]

It does unfortunately crash. How else will I be able to remove from within the function though? Aside from that, I see when I was editing the function I forgot to add another iterator again, thanks for pointing that out...

As for never changing mPrev or mNext, if I remove the guards, it fails due to either not having a next or prev node...

***EDIT***

I also felt it necessary to include the fact that my destructor already contains:

	~ListElement()
	{
		//Guarding if statement.
		if(mPrev && mNext)
		{
			mPrev->mNext = mNext;
			mNext->mPrev = mPrev;
		}
	}

[naraku9333]

ne555 wrote

Stop erasing your posts. Others could learn from that.

Agreed, it also makes it easier to help when I can see more code as I'm only 2 semesters into c++.

I dont understand why you delete one half then the other, doesnt seem tree structured. I'd
just set a "current" pointer to the first node and iterate through deleting.

My destructor

//destructor
//delete all Nodes
template <class T>
DoublyLinkedList<T>::~DoublyLinkedList()
{
	GoFirst();
	while(current->next != last)
	{
		current = current->next;
		DeleteCurrent();
	}

	delete first;
	delete last;
}

//sets current to the previous node
//then deletes the current node
template <class T>
void DoublyLinkedList<T>::DeleteCurrent()
{
	//error if list is empty and if
	//attempt to delete first or last
	if(first->next == last || current == last)
		throw Error(3);
	else if (current == first)
		throw Error(2);
	else
	{
		//set temp pointers 
		//and set temp as new current
		Node* temp = current->prev;
		temp->next = current->next;
		current->next->prev = temp;
		delete current;
		current = temp;
	}
}

[Whorse]

Managed to solve my own problem. This is how I destroyed my entire list. Since it's self contained this suits my purposes. I then deleted in main() to get rid of the main pointer since you are unable to delete *this.

	void DestroyList()
	{
		ListNode *iter = this, *temp;

		while(iter != NULL) //while the list is not empty
		{
			temp = iter; //store the current node.
			iter = iter->next; //visit the next node
			
			if(temp->prev)
				temp->prev = NULL;
			if(temp->next)
				temp->next = NULL;
		}
	}

[ne555]

That seems a memory leak. You are making your nodes inaccessible and you are not deleting them.
If you are having a main pointer, from which you handle everything, why don't just make a separate class list?
And if the nodes are encapsulated, you will no have the problem of delete or not delete.