Insert before *this realocation.

[Whorse]

I've been struggling for hours to implement this correctly but I'm assuming it's beyond my skill level at the moment. I'm attempting to insert a node into a linked list and then reassign that linked list's *this pointer to the new node so that if I print out the list, it will start by printing out the new value, not start by printing out the old value with the new value simply stored in that values previous node pointer.

Here is an example of my code:

	void Insert(ListElement temp)
	{
		ListElement *newNode = new ListElement;
		*newNode = temp;

		//Assert if the node we are trying to insert into is empty.
		assert(this != NULL);

		//Are we inserting before the first node?
		if(this == First())
		{
			newNode->mPrev = NULL;
			ListElement *first = First();
			first = newNode;
		}
		//If it's not the first, link it in before our current node.
		else
		{
			//New node's previous node is the current node's previous.
			newNode->mPrev = this->Previous();
			//Our current node is now our new node.
			this->Previous()->mNext = newNode;
		}
		//Make our new node's next node the current node.
		newNode->mNext = this;
		//Make our current node's previous node the new node.
		this->mPrev = newNode;
	}

[hamsterman]

Firstly, this will never be null, and you cannot assign to it.
To insert Node a before Node b,

a->prev = b->prev;
a->next = b;
if(b->prev) b->prev->next = a;
b->prev = a;

This code will work no matter where you want to insert the node (except the end, since then b would be null).
In your case a is newNode, and b is this.

If b was the first node, you need assign a to the pointer which pointed to b. I can't tell you how to do that without more information about the structure of your list.

Another, silly method is to insert a after b, and then swap their data. Don't do that..

[simeonz]

You can not do this so easily.

I posted some code in response to one of your questions that I realize was somewhat of an overkill and used templates (http://www.cplusplus.com/forum/general/33947/), but it gives you the starting point for a node based list that can insert at the beginning and end.

You can not modify the this pointer to point to another location. First, because it is not an lvalue (variable) and second, because the client code does not necessarily call the method through a pointer. It may call the node's method from an object allocated on the stack (using the dot notation.) Even though you may know that the client holds a pointer to the object (the node) and calls your methods through the pointer, you can not alter the pointer variable that the client holds using the this value on the left side of some assignment expression in the called method.

Let me again explain the dummy/sentinel node approach.

Your problem is:
Someone holds reference/pointer to the first and/or last nodes and you wish that their references will never be invalidated. Even when you insert at the beginning/end.

Possible solution:
Make the first and last nodes dummies.

Solution details:
- Whenever someone asks you to give them the previous/last node, first check if it is not a dummy node. You will know, because the dummy nodes are at the ends and therefore have no preceding/following node. If you see that the client has reached one of the two dummy nodes in the list during traversal, then pretend that there is nothing there and behave as if you reached the end of the list already. Basically, you hide the dummy nodes, as if they are some kind of spies or something.

- You should probably offer a procedure for creating an empty list. The empty list contains only the two dummy nodes linked to each other. In the code I posted previously (the one with templates) this role is played by the List class. I know this makes the architecture appear as not entirely node-based, but it is simply a class that captures the logic of creating an empty list with the two dummy nodes and offers access to the first and last actual nodes in the list (to skip over the dummies - see below). Nothing else. You don't want to involve the user with the construction of dummy nodes, the obligation to link them manually, and the knowledge of how to use them to acquire the first actual node during traversal.

- You should have a procedure, which given the starting dummy node, returns pointer to the first actual node. This is simply the node that follows the starting dummy node in your internal chain of nodes. I have provided this function as method in the List class which I posted, because thus the logic is best encapsulated.

- You should have a procedure, which given the ending dummy node, returns pointer to the last actual node. This is simply the node that precedes the ending dummy node. This I have also implemented in the List class.

Note: Whether you use a special List class to hold the two dummy nodes and manage their lifetime or you make this responsibility of the user code, you still have a node-based solution. The idea of a node based solution is that you can insert/remove from the collection without ever referring to container objects. You don't need the List class in order to insert and remove nodes. You need it only to acquire the first and last nodes from the list in the event that you want to traverse the nodes end to end.

Solution advantages:
When you insert at the beginning/end of the list as the client sees it, you insert at the second/next to last position of your internal chain. The new node will be linked in between the former first/last actual node in the list and the corresponding dummy node (for that end). The clients can keep their references to the dummy nodes, because they are never relocated by your code. Not until the list is destroyed.

Solution deficiencies:
You can not safely keep references to arbitrary positions in this "augmented" list. Only to the dummy nodes, and indirectly through them to the first and last position. References to intermediate positions are invalidated as always.

Regards

[Whorse]

This helped a lot, I see now where I was going wrong. The responses were informative, and more than anything I had hoped for. As for handling insertion at the first and last elements, that shouldn't be hard to implement at all.

***edit***

I've attempted implementing your example hamsterman, but I still get the same results. newNode still gets linked as the previous node of the list and is the beginning, but the list still only prints out from the previously first node.

[hamsterman]

I wrote:

If b was the first node, you need assign a to the pointer which pointed to b.

It seems to me that you didn't do this.
If you're trying to write a linked list without a List class, you should, as simeonz suggested, use dummy nodes.

[Whorse]

This is what I attempted at the moment:

	ListElement *Insert(ListElement temp)
	{
		ListElement *newNode = new ListElement;
		ListElement *current = new ListElement;
		ListElement *holder = new ListElement;
		*newNode = temp;
		current = this;

		//Assert if the node we are trying to insert into is empty.
		assert(current != NULL);

		newNode->mPrev = current->Previous();
		newNode->mNext = current;
		
		if(current->mPrev) 
			current->mPrev->mNext = newNode;
		current->mPrev = newNode;
		
		holder = newNode;
		newNode = current;
		current = holder;

		return current;
	}

However I still get the same issue even now that I've swapped the values around. Is there any possible solution that doesn't involve dummy nodes?

Basically my list is self contained, and has the payload, a before pointer and next pointer.

[hamsterman]

Firstly,

some_class* ptr = new some_class;
ptr = some_other pointer;

is a memory leak, and you have two of those.

Secondly, this will never be null, so you don't have to assert it.

Lastly, what this function does depends not only on it's contents, but also how you call it. In your main() you have some ListElement* head. The code you wrote has to be called like t his : head = head->insert(some_list_element);

What do you have against dummy nodes? (or dummy node. I don't think you really need two..)

If you find it difficult to understand your code, it may be a good idea to visualize it. Have several circles for ListElements, mark local variables somehow, then connect them all with arrows, depicting, what points to what. Then read your code line by line and see, how the arrows change.

[Whorse]

You are correct, that's how the function is called in main(). If I were to use dummy nodes, how would I implement them correctly with my kind of self contained list?

[Whorse]

I'm using pointers for the first, last, beginning and end nodes. However, I'm getting an error in the constructor, because when I attempt to assign

mFirst->mPrev = NULL;
        mFirst->mNext = mLast;
        mLast->mPrev = mFirst;
        mLast->mNext = NULL;

There is nothing to assign. How would I work around this? Simonez, your explanation of dummy nodes has been absolutely invaluable, I had no idea about them prior.

[naraku9333]

Have mFirst and mLast been allocated with new?

[Whorse]

****EDIT****

As I realised earlier my mistake is actually in my constructor. I need to assign values for mFirst, mLast, mPrev and mNext with support for dummy nodes. I'm having a hard time visualising the pointer assignment so I can link everything up appropriately and push new objects on. As you can see by my previous post, I'm having difficulty implementing this.

[simeonz]

Inserting is absolutely the same as without dummies.
The problem is to have the function Previous() defined like this:

ListElement *Previous()
{
    if (mPrev->mPrev)
    {
        return mPrev;
    } else {
        return NULL;
    }
}

Which basically says: if the previous node has no previous node, than the previous node is the first node, than the previous node is the dummy node, and than I will report NULL. (no previous node)

I agree that you should probably use only a starting dummy node as hamsterman suggested. It is enough for your purposes.

So the story is: To create a list create a single node. This is the dummy node itself. Keep references to it. When you want to process the list, start processing from Dummy.Next(). At this point, no one will know that Dummy even exists, because Dummy.Next()->Previous() is NULL. This is not the most elegant solution, but the one I proposed here - http://www.cplusplus.com/forum/general/33947/ - is complex and does not fit your current strategy or requirements.

Regards

[Whorse]

Thanks again for the informative response. How would you recommend keeping track of some sort of current node?

At the moment I'm attempting to create my Push function from the bottom up to suit my needs. At the moment I have no issue attempting to set a newly appended nodes next value because it's always NULL, however the trouble comes when I try to set it a previous node. I cannot use *this after the first append because *this always remains as the root node (I obviously have the same issue setting the next node because I'm unable to set *this next node as the new value.

After much thought and contemplation, it appears understanding how to avoid this issue (no pun intended) is my main hurdle.

[naraku9333]

Whorse wrote

How would you recommend keeping track of some sort of current node?

In the Linked list I wrote last semester I use Node* current;

At the moment I have no issue attempting to set a newly appended nodes next value because it's always NULL, however the trouble comes when I try to set it a previous node.

Not sure what you mean. Are you trying to set the new nodes prev to the actual previous node?

[Whorse]

I only need to keep track of it in my append function really. While it's quite obvious using Node* current to keep track of the current node, I'm having difficulties in setting it if the list is self contained. Like I said previously, it's easy if I'm appending to a new list, because current can just be set to *this, but after if appending to the list again how can I set current to the new value instead of *this again?

[naraku9333]

I have no clue what you mean by the list being "self contained".
Is append supposed to just add a node to the end of the list? If not can explain its intended function?

Would you be able to post your code? Im a student myself and its easier if I can see it.
If you would like me to post my list I have no problem with it.

[Whorse]

The list and the node are one and the same.

[Whorse]

I've found the solution to my issue. Appending can be done in this way by using a last pointer and appending around that.

[simeonz]

Whorse, I seem to fail to see the core of your problem. I'm glad you managed.

[Whorse]

At the moment I insert a new value before the nth position (my nth function works correctly) and inserts the said value before the position, however when I attempt to insert again, the nth value remains as the previous nth value. This is my main issue. At the moment this is what my insert function looks like:

	void Insert(ListElement &temp)
	{
		ListElement* newNode = &temp;

		newNode->mPrev = Previous();
		newNode->mNext = this;
		
		if(Previous())
			Previous()->mNext = newNode;
			
		mPrev = newNode;
	}

That is how I'm doing things at the moment. The only issue like I said before is getting the nth value to update. When I was debugging, I noticed that even though the nth value hasn't been updated (it still remains as the prior one) the nth->previous is the new value as it's supposed to be.

This is and has remained the main issue, I realise now that at the beginning of this post, no one understood the node context (the class being the manager and node itself) which complicates things.