Problem with fundamental understanding of double link list

Hi,

I am very frustrated right now. Sometimes my functions work and sometimes they dont. This is how I have implemented certain double link list functions.

For example, the destroy function doesnt work, the print doesnt work, EVEN THE LIST SIZE doesnt work.

Eg., if I do int a = list_length(L), then do printf(%i,a), the code runs. But if I do printf(%i, list_length(L)), it crashes.

Code:

/* Implementation file for the list ADT using a doubly (two-way) linked list */

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

typedef struct node {
  itemType data;
  struct node *next;
  struct node *previous;
} nodeType;

struct listTag {
   nodeType *head;
   nodeType *tail;
   int size;
};

/* Functions Definitions (Implementation)
 * **************************************/

//allocates memory space for a new list, initializes its fields and 
//returns a pointer to the allocated space 
List list_create() {
   List L;
   L = (List)malloc(sizeof(List));

   if (L)
   {
      L->head = NULL;
      L->tail = NULL;
      L->size = 0;
   }
   return L;
}

void list_destroy( List L ) {
   nodeType *P;
   while (L->head!=NULL)
   {
      P = L->head;
      L->head = L->head->next;
      P->previous = NULL;
      P->next = NULL;
      free(P);
   }
   free(L);
   L=NULL;
}

bool list_isEmpty( const List L ) {
   return (L->size==0);
}

int list_length( const List L ) {
   return (L->size);
}

void list_print( const List L ) {
   if(L && L->head)
   {
      nodeType *P;
      printf("( ");
      P = L->head;
      while (P != NULL)
      {
         printf("[%i]", P->data);
         P = P->next;
         if (P != NULL)
            printf(" -> ");
      }
      printf(" )\n");
   }   
}

bool list_insertFront( itemType value, List L ) {   
   if(L)
   {
      nodeType *N;
      N = (nodeType*)malloc(sizeof(nodeType));

      if (N!=NULL)
      { 
         N->previous = NULL;
         N->next = NULL;
         N->data = value;
         if (L->size==0)
         {            
            L->head = N;
            L->tail = N;
         }
         else
         { 
            N->next = L->head;
            L->head->previous = N;
            L->head = N;
         }
        L->size++;
      }
      return true;
   }
   return false;
}


int main()
{
  List L = list_create();
  list_insertFront(9,L);
  list_insertFront(9,L);
  list_insertFront(9,L);
  //int a = list_length(L);
  //printf("%i",list_length(L));
  list_destroy(L);

  //list_print(L);
   
   system("PAUSE");
   exit(EXIT_SUCCESS);
}

I have tried everything, asked some pro CS people, but just cant seem to understand what is wrong.

Thanks a lot for your help.

First oh-no-you-didn't moment:

Code:

L = (List)malloc(sizeof(List));

You don't have nearly enough room for anything in there. You need to allocate enough memory for whatever a List points to.

Second could-be-worse moment:
Your destroy function cannot actually set the List pointer to NULL, since you are only dealing with a local copy of the pointer and not the actual pointer that your user is holding.

If you understand how to correctly destroy a single linked list, then you understand how to destroy a doubly linked list. It uses the same exact steps. Doubly linked lists are easier to insert into the middle of, or to remove from the middle of, because all you need is the node where you want to insert before or after, and you just stick it right there. You don't have to worry about finding the previous pointer, because you've got it built right into your node.

The same goes for finding the size. All you do is start at the front, and walk to the end, just like you would in a single linked list. Or, you pick any random node, and count both forwards, the current node, and backwards. Basically you just loop until next (or prev, if you're counting backwards) is NULL.


Quzah.

Originally Posted by tabstop

First oh-no-you-didn't moment:

Code:

L = (List)malloc(sizeof(List));

You don't have nearly enough room for anything in there. You need to allocate enough memory for whatever a List points to.

Second could-be-worse moment:
Your destroy function cannot actually set the List pointer to NULL, since you are only dealing with a local copy of the pointer and not the actual pointer that your user is holding.

Tab,

Thanks for replying.
I have sizeof(struct listTag) before but someone told me I dont need that. But I talked to my prof today and i realised I was wrong.

For the L = NULL, I think its valid because in the header file, List is defined as a pointer to a struct listTag.

typedef struct listTag *List;

Tell me if I'm wrong though. I'm gona try implementing more fucntions, hopefully I dont get memory leaks. I might be posting here tonight or tomorow. Thanks.

PS: Do I need to set the previous and next pointers to null as I free the nodes? Someone told me once I free the list, it takes care of all those dangling pointers inside. Please let me know.

Originally Posted by bbjunaid

For the L = NULL, I think its valid because in the header file, List is defined as a pointer to a struct listTag.

That just means that you're not quite up to speed on thinking. You can never, pointer or no pointer, change the value of a parameter passed in to a function.

Code:

void fun_one(int b) {
    b = 5;  //the calling function will not see this
}

void fun_two(int* b) {
    b = NULL; //the calling function will not see this
}

If you free an object, nobody cares one jot where the freed pointers point to, since they no longer exist. If you have other pointers pointing to where that memory used to be, then you're in trouble.

First off, I'm not trying to challenge your C knowledge or anything. I'm a complete noob, I'm just trying to understand my lecture notes. I should probably take my laptop to class to make sure the code my prof gives me even compiles.

I'm curious about this DeleteLastNode function in my textbook, why exactly does it set the List to null if there is one node, but not multiple.

Code:

void DeleteLastNode(NodeType **L)
{
   NodeType *prevNode, *curNode;
   
   if(*L != NULL)
   {
      if ((*L)->next == NULL)
      {
         free(*L);
         *L = NULL; 
      }
      else
      {
      prevNode = *L;   
      curNode = prevNode->next;
      while (curNode->next)
      {   
         prevNode = curNode;
         curNode = curNode->next;
      }
      prevNode->next = NULL;
      free(curNode); //what would happen if i freed first, then set next o null???
      }
   }

Also, what should I keep for the destroy function then. You're saying I dont need L = NULL. Should I also take out the parts where I set previous and next pointers to Null?

thanks

Because the DeleteLastNode function is only designed to delete the last node. If there is more than one item in the list, then the list is not empty after this thing runs.

And note how setting a list to NULL is supposed to be done here. The value of L itself is not changed....