Doubly linked lists

Hi all,
I've been having some difficulty with understanding doubly linked lists. I looked at the FAQ and the tutorial about doubly linked lists(which is very short by the way), and think I have a basic understanding. My problem is that I've been given some code, and been asked to tweak the singly linked list into a doubly linked list. So the following is the example provided in the tutorial:

Code:

---

n->prev = item; /* n's prev pointer */
 n->next = item->next; /* n's next pointer */
 n->next->prev = n; /* n's next->prev pointer */
 n->prev->next = n; /* n's prev->next pointer */

---

My understanding is that you must have both the previous pointer and the next pointer point to the value input by the user. If I'm wrong in the assumption, please correct me. This is a sample of the code I've been given:

Code:

---

void insert(listnodeptr *startptr, char value)
{
        listnodeptr newptr;          /*pointer to new node*/
        listnodeptr previousptr; /*pointer to previous node in list*/
        listnodeptr currentptr;  /*pointer to current node in list*/

        newptr = malloc(sizeof(listnode)); /*allocate new space*/

        if(newptr != NULL){ /*is space available*/
                newptr->data = value; /*place choice in node*/
                newptr->nextptr = NULL; /*New node points to NULL*/
                previousptr = NULL;
                currentptr = *startptr;
               
                /*loop to find correct location in list*/
                while(currentptr != NULL && value > currentptr->data){
                        previousptr = currentptr; /*walk through list*/
                        currentptr = currentptr->nextptr;
                }/*end while*/

                /*insert new node at start of list*/
                if(previousptr == NULL){
                        newptr->nextptr = *startptr;
                        *startptr = newptr;
               
                }/*end if*/
                else{
                        previousptr->nextptr = newptr;
                        newptr->nextptr = currentptr;
                }/*end else*/
        }/*end if*/
        else{
                printf("%c not inserted. No memory available.\n", value);
        }
}/*end function insert*/

---

How is this not a doubly linked list? After malloc is used to create a new node, both the previous and next pointers are initialized to NULL, then inserted into the list. Then, both previous and next pointers are set to the value.

Any help would be greatly appreciated!

Since "prevptr" doesn't appear anywhere in the sample code, I'm curious as to how you think the previous pointers are getting set.

Hi thanks. Sorry about that, maybe I should have posted all the code in the first place.
Here is the code that I have manipulated so far:

Code:

---

#include <stdio.h>
#include <stdlib.h>

/*self referential structure*/
struct listnode{
        char data;
        struct listnode *prevptr, *nextptr; /*"prevptr" was not part of the original code, I had to make this program a doubly linked list.*/
};
typedef struct listnode listnode; /*synonym for struct listnode*/
typedef listnode *listnodeptr; /*synonym for listnode* */

/*prototypes*/
void insert(listnodeptr *sptr, char value);
char delete(listnodeptr *sptr, char value);
int isEmpty(listnodeptr sptr);
void printlist(listnodeptr currentptr);
void printreverse(listnodeptr currentptr);/*basically a copy of the original "printlist" but in reverse.
void instructions(void);
int main(void)
{
        listnodeptr startptr = NULL; /*no initial nodes*/
        int choice; /*user choice*/
        char item;  /*entered by user*/

        instructions(); /*display menu*/
        printf("? ");
        scanf("%d", &choice);
        /*loop for user choice*/
        while(choice != 3){

                switch(choice){
                       
case 1:

        printf("Enter a character: ");
        scanf("\n%c", &item);

        insert(&startptr, item); /*enter item into linked list*/

        printlist(startptr);
        printreverse(startptr);

        break;

case 2: /*delete an element*/
        /*check list, if not empty*/
        if(!isEmpty(startptr)){
                printf("Enter character to be deleted: ");
                scanf("\n%c", &item);

                /*if character is found, delete*/
                if(delete(&startptr, item)){
                        printf("%c deleted.\n", item);
                        printlist(startptr);
                        printreverse(startptr);
                }
                else{
                        printf("%c not found.\n\n", item);
                }
        }
        else{
                printf("List is empty.\n\n");
                instructions();
        }
        break;
default:
        printf("Invalid choice.\n\n");
        instructions();
        break;
                }/*end switch*/

                printf("? ");
                scanf("%d", &choice);
        }/*end while*/
        printf("End of run.\n");

        system("pause");

        return 0;
}

void instructions(void)
{
        printf("Enter your choice:\n"
                "  1 to insert an element into the list.\n"
                "  2 to delete an element from the list.\n"
                "  3 to end.\n");
}/*end instructions*/

/*Insert a new element and sort*/
void insert(listnodeptr *sptr, char value)
{
        listnodeptr newptr;          /*pointer to new node*/
        listnodeptr currentptr;  /*pointer to current node in list*/
/*"listnode previousptr" was declared here, but I removed it since it was declared earlier on*/

        newptr = malloc(sizeof(listnode)); /*allocate new space*/

        if(newptr != NULL){ /*is space available*/
                newptr->data = value; /*place choice in node*/
                newptr->nextptr = NULL; /*New node points to NULL*/
                newptr->prevptr = NULL;/*this replaced "previousptr"*/
                currentptr = *sptr;
               
                /*loop to find correct location in list*/
                while(currentptr != NULL && value > currentptr->data){
                        newptr->prevptr = currentptr; /*walk through list*//*this replaced "previousptr"*/
                        currentptr = currentptr->nextptr;
                }/*end while*/

                /*insert new node at start of list*/
                if(currentptr->prevptr == NULL){/*was "previousptr"*/
                        newptr->nextptr = *sptr;
                        if(*sptr != NULL){
                                (*sptr)->prevptr = newptr;  /*new code*/
                        }
                        *sptr = newptr;
               
                }/*end if*/
                else{
                        newptr->nextptr->prevptr = newptr;
                        newptr->prevptr->nextptr = newptr;
                        newptr->nextptr = currentptr;
                        if (currentptr != NULL){           
                                currentptr->prevptr = newptr;
                        } 
                }/*end else*/
        }/*end if*/
        else{
                printf("%c not inserted. No memory available.\n", value);
        }
}/*end function insert*/

char delete(listnodeptr *sptr, char value)
{
        listnodeptr currentptr;  /*pointer to current element in list*/
        listnodeptr tempptr;          /*temporary pointer*/
/*"listnode previousptr" was declared here, but I removed it since it was declared earlier on*/

        if(value == (*sptr)->data){
                tempptr = *sptr; /*place element in temp location*/
                *sptr = (*sptr)->nextptr; /*take element out of list*/
                free(tempptr);        /*remove element from memory*/
                return value;
        }/*end if*/
        else{
                *sptr = (*sptr)->prevptr;
                currentptr = (*sptr)->nextptr;  /*I changed this, but it didn't work*/

                /*loop to find correct location in list*/
                while(currentptr != NULL && currentptr->data != value){
                        (*sptr)->prevptr = currentptr; /*go through list*/
                        currentptr = currentptr->nextptr;  /*this didn't work either*/
                }/*end while*/

                /*insert element at start of list*/
                if(currentptr == NULL){
                        tempptr = currentptr;
                        currentptr->prevptr = currentptr->nextptr;/*again, didn't work*/
                        free(tempptr);
                        return value;
                }/*end if*/
        }/*end else*/
        return '\0';
}/*end function delete*/

/*return 1 if the list is empty*/
int isEmpty(listnodeptr sptr)
{
        return sptr == NULL;

}/*end function isEmpty*/

/*print function*/
void printlist(listnodeptr currentptr)
{
        /*if list is empty*/
        if(currentptr == NULL){
                printf("List is empty.\n\n");
        }/*end if*/
        else{
               
                printf("The list is:\n");

                /*run through list*/
                while(currentptr != NULL){
                        printf("%c --> ", currentptr->data);
                        currentptr = currentptr->nextptr;
                }/*end while*/
                printf("NULL\n\n");
        }/*end else*/

}/*end function printlist*/
void printreverse (listnodeptr currentptr)
{
    listnodeptr temp = NULL;
 
          while (currentptr != NULL ) {
                temp = currentptr;
                currentptr = currentptr->nextptr;
               
                }
               
      printf( "\nThe list in reverse is:\n" );
      printf( "NULL" );
 
                currentptr = temp;
                while ( currentptr !=  NULL) {
                printf( " <-- %c", currentptr->data );
                currentptr = currentptr->prevptr;
                }
               
                printf("\n\n");
               
}

---

I've highlighted the changes. I hope it makes it easier to read.

All those things you removed because you seemed to think were declared earlier on -- aren't declared earlier on. You need to still have them.

Think about it with index cards or something for a minute: to insert into a doubly linked list, you'll need to set two pointers -- two on the new node itself, one coming forward from the previous node, one coming backward from the next node.

Thanks for the help. I'm still learning this concept, so the execution is still a little difficult for me. If I can ask, why do you need to have "prevptr" declared in struct listnode at the beginning of the code, and then "previousptr" in the function prototypes?

Because previousptr is a node, not a piece of a node. (And it was a node in your original code too.)

OK. I put back in all the code I deleted, and I'm working on it. I think I understand, but I'm not sure. Please take a look at the following code, and correct me if I'm wrong.

Code:

---

void insert(listnodeptr *sptr, char value)
{
        listnodeptr newptr;          /*pointer to new element*/
        listnodeptr previousptr; /*pointer to previous element in list*/
        listnodeptr currentptr;  /*pointer to current element in list*/

        newptr = malloc(sizeof(listnode)); /*create new space*/

        if(newptr != NULL){ /*is space available*/
                newptr->data = value; /*place choice in element*/
                newptr->nextptr = NULL; /*New element pointers to NULL*/
                newptr->prevptr = NULL;

                previousptr = NULL;
                currentptr = *sptr;

                /*loop to find correct location in list*/
                while(currentptr != NULL && value > currentptr->data){
                        previousptr = currentptr; /*go through list*/
                        currentptr = currentptr->nextptr;
                        newptr->prevptr = previousptr;
                        newptr->nextptr = currentptr;
                }/*end while*/

                /*insert element at start of list*/
                if(previousptr == NULL){
                        newptr->nextptr = *sptr;
                        *sptr = newptr;
                        newptr->nextptr = currentptr-prevptr;
                }/*end if*/
                else{
                        previousptr->nextptr = newptr;
                        newptr->nextptr = currentptr;
                }/*end else*/
        }/*end if*/
        else{
                printf("%c not inserted. No memory available.\n", value);
        }
}/*end insert*/

---

I understand that you need to have two pointers coming into the new node, and two pointers going out of the new node. The above code is how I'm trying to execute that.

I don't know why you have all those pointers declared.

Code:

---

struct dll {
    struct dll *prev;
    struct dll *next;
    int data;
};

...

struct dll *list; /* your list, some place */

void insert( struct dll **ourlist, int value )
{
    struct dll *nn = malloc( sizeof *nn );
    if( nn == NULL )
    {
        return; /* you probably want to do something more than just return if malloc fails */
    }
    else
    {
        nn->prev = nn->next == NULL;
        nn->data = value;
    }

    /* decide how you want to insert it, let's go with acending order /
    if( ourlist )
    {
        if( *ourlist )
        {
            struct dll *n = *ourlist;
            while( nn->data > n->data && n->next )
            {
                n = n->next;
            }

            if( n->next )
            {
                nn->prev = n->prev;
                nn->next = n;
                n->prev = nn;
            }
            else
            {
                nn->prev = n;
                n->next = nn;
            }
        }
        else
        {
            *ourlist = nn;
        }
    }
}

...

insert( &list, 10 );

---

Something like that. Haven't tested it, but it looks pretty good. I just woke up though, so something might be off slightly.


Quzah.

I am trying to develope a double linked list with the following structure that allows you to add, delete, move and sort using a selection sort.

This is the structure I use:

Code:

---

typedef struct people
{
char chfname[10];{I am having a problem with adding these into the list
char chlname[10];{""                                                                              "
struct people *pSNextPerson;
struct people *pSPreviousPerson;
}

---

selection sort algorithm:

Code:

---

selectionsort(int a[], int N)
{

int i,j,min,t;
for (i=1;i<N;i++)
{
  min=i;
    for (j=i+1;j<=N;j++)
      {
        if (a[j]<a[min])) min=j;
        {
            t=a[j];a[min]=a[i]; a[i]=t;<how do this with character pointers?
          }
        }
}

---

Could someone please show complete code?
thank you very much, John