Thread: single linked list to double linked list (help)

In the code I provided in the zip file, I already have this prototype for a double linked list.

Code:

struct listNode {
	char data;
	struct listNode *nextPtr;
	struct listNode *prevPtr;

Now lets take the Insert function.

Code:

void insert( ListNodePtr *sPtr, char value )
{
	ListNodePtr newPtr;
    ListNodePtr previousPtr;
    ListNodePtr currentPtr;

	newPtr = malloc(sizeof( ListNode ) );

	if ( newPtr != NULL ) {
		newPtr->data = value;
		newPtr->nextPtr = NULL;

		previousPtr = NULL;
		currentPtr = *sPtr;

		while ( currentPtr != NULL && value > currentPtr-> data) {
			previousPtr = currentPtr;
			currentPtr = currentPtr-> nextPtr;
		}
		if ( previousPtr == NULL ) {
			newPtr->nextPtr = *sPtr;
			*sPtr = newPtr;
		}
		else {
			previousPtr-> nextPtr = newPtr;
			newPtr->nextPtr = currentPtr;
		}
	}
	else {
		printf( "%c not inserted. No memory available.|n", value );
	}
}

Its very obvious to me that this is the part I have to change, and yet this is the part that I dont understand. I understand the rest of the program and the rest of the function insert, but please explain to me what the heck is going on in the following code. It seems weird to think about memory locations pointing to memory locations of memory locations and etc.
Very confusing to me.

Code:

previousPtr = NULL;
		currentPtr = *sPtr;

		while ( currentPtr != NULL && value > currentPtr-> data) {
			previousPtr = currentPtr;
			currentPtr = currentPtr-> nextPtr;
		}
		if ( previousPtr == NULL ) {
			newPtr->nextPtr = *sPtr;
			*sPtr = newPtr;
		}
		else {
			previousPtr-> nextPtr = newPtr;
			newPtr->nextPtr = currentPtr;
		}

I'm guessing the point here is to insert things in sorted order.

Originally Posted by Countfog

Code:

previousPtr = NULL;
		currentPtr = *sPtr; /* start here */

		while ( currentPtr != NULL && value > currentPtr-> data) {
			/* if value is larger, we need to be further along */
			previousPtr = currentPtr; /* walk forward */
			currentPtr = currentPtr-> nextPtr;
		}
/* When we get here, we want to insert the node between previous and current.*/
		if ( previousPtr == NULL ) {
			/* If the first element, make this node the head */
			newPtr->nextPtr = *sPtr;
			*sPtr = newPtr;
		}
		else {
			/* Make the back one point to the new one and the new one point to the next one */
			previousPtr-> nextPtr = newPtr;
			newPtr->nextPtr = currentPtr;
		}

The node contains: data and links. There's a pointer (two, in a doubly linked list) inside the node, but they are not the same thing.

Somewhere in your book, there is a picture with a lot of arrows in it, which I will try to emulate with ASCII art; but I will fail. Once you see the picture, you will know what to do.

Code:

1 -> 2 <-> 3 <-> 5

              4

becomes

Code:

1 -> 2 <-> 3 <-| |-> 5
               | |
               v v
                4

You need to destroy two links and set four links.