Understanding double pointer in doubly linked list in C

Question

Hi,

I have an exam tomorrow and I was trying to understand this doubly linked list example that the instructor placed on the class website but I'm having a hard time understanding a bit of it...

Here's the code:

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

typedef struct dl {
    int key;
    float value;
    struct dl *next;
    struct dl *prev;
} DL;

DL *insert(int c, float f, DL *l) {
    DL *new = (DL*) malloc(sizeof(DL));
    if (new == NULL) exit(-1);
    new->key=c; new->value=f; 
    if (l==NULL) {
     new->next=NULL; new->prev=NULL;
    }
    else if (l->key < c) {
     while((l->next != NULL) && (l->next->key < c)) { l=l->next; }
     new->next=l->next; l->next=new; new->prev=l;
     if (new->next != NULL) {
      new->next->prev=new;
     }
    }
    else {
     while((l->prev != NULL) && (l->prev->key > c)) { l=l->prev; }
     new->prev=l->prev; l->prev=new; new->next=l;
     if(new->prev != NULL) {
      new->prev->next=new;
     }
    }
    return new;
}

int search(int c, float *f, DL **lptr) {
    if (*lptr == NULL) return 0;
    if (c < (*lptr)->key) {
     while(((*lptr)->prev!=NULL)&&((*lptr)->prev->key >= c)) {
      (*lptr)=(*lptr)->prev;
     }
    }
    else if (c > (*lptr)->key) {
                while(((*lptr)->next!=NULL)&&((*lptr)->next->key <= c)) {
                        (*lptr)=(*lptr)->next;
                }
    }
    if ((*lptr)->key == c) {
     *f = (*lptr)->value;
     return 1;
    }
    return 0;
}

void printList(DL *l) {
    if (l == NULL) return;
    while (l->prev != NULL) { l=l->prev; };
    while(l != NULL) {
     printf("%d,%f\n",l->key,l->value);
     l=l->next;
    }
}

int main(void) {
    DL *list=NULL;
    float f;
    list=insert(3,5.6,list); list=insert(4,5.3,list);
    list=insert(7,3.6,list); list=insert(1,7.7,list);
    list=insert(9,2.3,list); list=insert(0,9.0,list);
    printList(list);
    if (search(3,&f,&list)) {
     printf("Found %f.\n",f);
    }
    else {
     printf("Not found.\n");
    }
    printList(list);
    return 0;
}

An here's the output:

0,9.000000
1,7.700000
3,5.600000
4,5.300000
7,3.600000
9,2.300000
Found 5.600000.
0,9.000000
1,7.700000
3,5.600000
4,5.300000
7,3.600000
9,2.300000

What I don't get is the "search" function. The list being passed is a pointer to a pointer of DL, right? And we are looking for a number, for that we keep doing (*lptr) = (*lptr)->next (or prev) to iterate through the whole list. What I don't get is why the second call to printList() prints the whole list... After the search() call has been made, shouldn't the "list" only have the elements after the one we looked for? The pointer was changed, how come when we return from search() the pointer is restored to the first element and the whole list is printed?

This is what I don't get cause if I change the search() function and add (*lptr) = NULL in the first line, the second call to printList() will not print anything, cause the pointer was changed, it is NULL now, there's nothing to print. Why doesn't (*lptr) = (*lptr)->next has a similar effect? The pointer is also being changed to the next one, shouldn't the second printList() call only print the remaining elements in the list?

EDIT:
Every answer seems to be the correct one and I'm going to sort it by "oldest" and accept the "fastest" one, don't be mad, I need to have some criteria. I could go on and see which answered provided better insight on the issue but it's irrelevant because I already know everything that was said. I was just stupid enough to not even look to the printList() function and assumed it was ok, I also assumed that the error was somewhere on the search() function. But I knew I was right, I knew the pointer was being change and the list couldn't print everything, but I understand why now...

Answer 1

This line return pointer back:

while (l->prev != NULL) { l=l->prev; };

And those do the printing:

while(l != NULL) {
    printf("%d,%f\n",l->key,l->value);
    l=l->next;
}

And there is much better approach of doing this, just by adding the additional field or even two which will always point at the beginning and end of the list.

Answer 2

printList rewinds the list before printing it.

while (l->prev != NULL) { l=l->prev; };

If it didn't have the above line, it would just print the things after the found element.

Answer 3

In the printList() function you are going back from the found element using l = l->prev. Then you are printing all the contents.

Answer 4

What I don't get is why the second call to printList() prints the whole list... After the search() call has been made, shouldn't the "list" only have the elements after the one we looked for? The pointer was changed, how come when we return from search() the pointer is restored to the first element and the whole list is printed?

What you have is not really a pointer to the list, but a pointer to an element in the list. The first thing that the printList function does it to loop back through the prev references to find the first element of the list.

Answer 5

He backtrack the pointer inside the print:

while (l->prev != NULL) { l=l->prev; };

Remember that the list is doubly linked. Search doesn't change the list, just what part of it "list" is presently pointing to.

Answer 6

As far as I can read (and like rmeador commented, it is pretty awful code), the search call does modify the list pointer to point to the found element.

The trick is the printList function. The first thing it does (other than checking for NULL) is this:

while (l->prev != NULL) { l=l->prev; };

So it basically follows the prev pointer back to the start of the list, so the actual printing starts from the start of the list even if it is passed a pointer to the middle or end of it.