single linked list to double linked list (help)

I'm telling you I can't stand online programming courses in college, but what choice do I have? I have no live instructor. Its very difficult.

I have an assignment. Convert a linked list to a double linked list. Nothing in my book on how to do this. I'm supposed to research how myself.

The list I have to convert is pretty long, but I pray that there is someone out there with the patience to help me. I'm desperate.

Here is the single linked list I need to convert. Too long to paste here.

URL deleted. The list in question is Fig 12.3 in Chapter 12 of C How to Program 5th edition by Deitel.

The only thing I understand is that the double linked list should be able to go forward and backward. What exactly does that mean in my case? When I insert a character into the list, I go forward, when I delete a character, I go backward. What would a double linked list do different?

This is the only clue my professor gave me.

Code:

---

You should add a print backwards to prove that the list works in reverse.

You must remove the previous node in the insert and delete routines and use the previous pointer instead.

A node structure for a doubly linked list is:


struct Node{  int data;/ this can be any type data  Node *next;  Node *prev; }

---

Can someone please explain this to me?

There's something weird: the code sample you provided is already a double linked list
as proved by the node definition:

Code:

---

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

---

However the insert/delete and dump routines are using the list as
a single linked list indeed (the whole list is walked each time a value
is inserted, etc.) so the only thing you have to do is to adapt those
routines: instead of walking the whole list, keep a record of the last
node inserted and add/delete each new node from here.

A double linked list is no different of a single linked list for the 'external'
user (the interface is identical) but the insertion/deletion cost are much
less expensive as there is no loop (assuming you simply add and delete
from the end of the list).

> The only thing I understand is that the double linked list should be able to go forward and backward.

That's a pretty big hint though. Take this excerpt from a lengthly article on the subject:

Quote:

---

Double Linked Lists

So far, we've been looking at a linked list with one link to the next node. This is known technically as a single linked list, and it's certainly not the only option. In fact, another named variation uses two links: one to the next node and one to the previous node. This variation is known as the double linked list, and it's only slightly more difficult than the single linked list. Graphically, I would represent a double linked list like so:

~ <- 1 <-> 2 <-> 3 <-> 4 <-> 5 -> ~

Notice how the links now go both ways, so any node can link to the previous and next nodes. This means quite a few things to us. It means that we can traverse a list in either direction or even change directions and go back if we missed something. It means that we don't need to traverse the list to find the previous node for insertion or deletion because the pos node can now give us that information directly. And of course, it means that we have to work harder to maintain links. ;-)

---

> What exactly does that mean in my case? When I insert a character into the list, I go forward,
> when I delete a character, I go backward. What would a double linked list do different?

Nothing necessarily - there are prepend operations that make as much sense for doubly linked lists as for singly linked ones. The key difference with a double linked list is that you have to take the other link into account, the logic is basically the same.

> This is the only clue my professor gave me.

It sounds like your professor wants something very specific, so I would just do what he says. Looking at the code, the only thing you would need to do is change the printList, delete, and insert functions to work with the prev pointer instead of the next pointer, so that you build, print, and delete the list backwards, going from tail to head, instead of from head to tail.

Thanks a lot citizen, your explanation does make sense. There is one thing I probably still don't get about nodes themselves. Remember I have only my book to explain things to me, and you know how books are.

According to my understanding a node is a struct, where one of the members of the struct points back to the memory location of the struct.

Code:

---

struct node {    /* a structure called node*/

char data;      /* first member of the struct*/

struct node *nextPtr;  /* second member of the struct which points back to the struct*/

};

---

So what I don't understand is where exactly are there any other node structs in a linked list? Are they all created by malloc?

The linked list according to my understanding is a bunch of lists linked together. The lists in this case being structs. So a new struct gets created every time?

Am I correct there?

I'm trying to understand exactly how this program works, I have only the book to teach me. Because if I don't understand how a single linked list works, I won't know what to change to make it doubly linked. ;)

Quote:

---

According to my understanding a node is a struct, where one of the members of the struct points back to the memory location of the struct.

---

With a singly linked list, a node is a struct, where one of the members holds the data to be recorded and the other member points to the previous or next node in the list (depending on the direction from which you add nodes). If the member is called nextPtr, it makes senses to have it point to the next node in the list. For a doubly linked list, there is an additional member so that a pointer points to the next node and another points to the previous node in the list (hence the two pointers nextPtr and prevPtr).

Examples:
Singly linked list: [a]->[b]->[c] (notice you cannot access [a] starting from [c])
Doubly linked list: [a]<->[b]<->[c] (here you can access [a] from [c])

Quote:

---

The linked list according to my understanding is a bunch of lists linked together

---

No...a linked list is a 'simple' list, not 2D.

In the code you provided, remove each occurence of the member prevPtr in the code and you get
a single linked list (the member is not really used in the code). Once you understand how it works, put back prevPtr and try to use it to make the things more efficiently, if you understood how a single list work, it should be pretty obvious.

> Because if I don't understand how a single linked list works, I won't know
> what to change to make it doubly linked. ;)

Precisely. :)

> So what I don't understand is where exactly are there any other node
> structs in a linked list? Are they all created by malloc?

In C, singly linked lists are build out of nodes linked together through the next pointer. You create a new node when you have more data. Most of the time the memory for the new node comes from malloc, but it doesn't /have/ to. In your case, using malloc would be easiest.

> The linked list according to my understanding is a bunch of lists linked
> together. The lists in this case being structs. So a new struct gets created
> every time?

If you have A <-> B <-> C, to create D, you would need to either have a variable declared on the stack that will be linked to the rest of the list, or you can use malloc to create D at run time. Part of what makes a linked list useful is that they can grow naturally as the program runs.

Maintaining links is what can make linked lists difficult. Even after you create D with malloc, you have to link it into the list you want.

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.

Quote:

---

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.