Thread: Doubly-Linked List

Hello all,

Thank you in advance for your help and patience. I'm implementing a doubly-linked list in C, and I have some questions about freeing resources. Please forgive me if I get too detailed in my overview. My goal is to be as clear and close to complete as possible in my description.

I will use the confused smile in the sections where I'm describing problems, and I will indent and number actual questions.


I'll start by listing my data structures. First is the node struct, peNode:

Code:

   typedef struct peNode__{
         void*  p_vElem;
         struct peNode__* p_Next;
         struct peNode__* p_Prev;
    } peNode;

Notice that it contains two node pointers that will point to the next and previous list nodes. It also contains a void pointer that will point to the node's data.

The final component of this list data structure is the peList struct:

Code:

   typedef struct peList__{
         peNode* p_Head;
	 peNode* p_Tail;
	 int     iSize;
         int    (*f_Equ)(peNode* p_Node1, peNode* p_Node2);
	 void   (*f_Del)(peNode* p_Node);
   }peList;

So far, it has five elements. I will eventually add more and maybe get rid of one based on your input. There are two peNode pointers that will point to the beginning and end nodes in a list. There is an integer field - iSize - that will contain the size of the list.

Finally, there are two function pointers. The first - f_Equ - returns an int and takes two peNode pointers as parameters. This field may be instantiated with a pointer that compares two peNodes to see if they are "equal". The idea is that the equality of two nodes can be determined and defined by the developer.

The second of the two function pointers is f_Del. It returns void and takes a peNode pointer as a parameter. This field may be instantiated with a pointer to a function that deletes a peNode.

I thought that this would be necessary if a developer decided to store a complex data structure in each of the nodes of a list. Since the peNode p_vElem field is a void pointer, it can point to anything. It seemed like a good idea, but now I'm not sure.

1. First, it occured to me that if an implementation needed a user-defined function for the deletion of nodes, then it would also need a user-defined function for the creation of nodes. (I currently have a function called createNode, which I will list and discuss later). Isn't this the case? If you need special instructions to delete a node, wouldn't that imply that you needed special instructions to create it? Of course, it's no trouble to add this functionality to the code. However, the more I thought about it, the less certain I was that the user defined create and delete functions would be of any use.

2. Are there potential uses of this list that would require user-defined create and delete functions for nodes? If a peNode consists of two peNode pointers and a void pointer, then does one call to malloc always do the trick? If the node's void pointer (p_vElem) points to some complex data type, doesn't the developer have to worry about allocating space for the complex data object itself, and not its pointer?

I've currently run into a problem when testing the list using simple data. I'm not worrying about user-defined create and delete functions at this phase of testing. I simply use the following function to create a node:

Code:

peNode* createNode(void *p_vElem){

   peNode *p_Node = (peNode *) malloc(sizeof(peNode));

   if(p_Node!=NULL){
     p_Node->p_vElem = p_vElem;
     p_Node->p_Next = NULL;
     p_Node->p_Prev = NULL;
   }
   
   return p_Node;
}

That's pretty straightforward. Now, if I want to add a node to the head of a list, I use the prependNode function:

Code:

RTRN prependNode(peList *p_List, peNode *p_Node){

   if(p_Node == NULL){
     return PE_LIST_NULL_ELEMENT;
   }
   
   if(isEmpty(p_List)){
     p_List->p_Head = p_Node;
     p_List->p_Tail = p_Node;
     p_Node->p_Prev = NULL;
     p_Node->p_Next = NULL;
   }else{
     p_Node->p_Next = p_List->p_Head;
     p_List->p_Head->p_Prev = p_Node;
     p_Node->p_Prev = NULL;
     p_List->p_Head = p_Node;
   }

   p_List->iSize++;

   return PE_LIST_OK;

}

To remove a node from a list, I use removeNode:

Code:

RTRN removeNode(peList *p_List, peNode *p_Node, void **p_vElem){

   if(isEmpty(p_List)){
     return PE_LIST_EMPTY;
   }

   if(p_Node == NULL){
     return PE_LIST_NULL_ELEMENT;
   }

   *p_vElem = p_Node->p_vElem;

   if(isHead(p_List,p_Node)){

     if(hasNext(p_Node)){
       p_List->p_Head = p_Node->p_Next;
       p_Node->p_Next->p_Prev = NULL;
     }else{

       p_List->p_Head = NULL;
       p_List->p_Tail = NULL;
     }

   }else{

     p_Node->p_Prev->p_Next = p_Node->p_Next;

     if(isTail(p_List, p_Node)){
       p_List->p_Tail = p_Node->p_Prev;
     }else{
       p_Node->p_Next->p_Prev = p_Node->p_Prev;
     }
   }

   free(p_Node);

   p_List->iSize--;
  
   return PE_LIST_OK;

}

Finally, if I want to delete a list, I call deleteList. (Please note that I'm not posting the initList code, but it does contain a call to malloc.):

Code:

RTRN deleteList(peList *p_List){

   void *p_vElem;

   while(containsData(p_List)){
     removeNode(p_List, p_List->p_Tail, &p_vElem);
   }

   free(p_List);
   
   return PE_LIST_OK;
}

OK. Thank you for taking the time to look at these functions. Now I'll get on with the problem. If I use the functions as they are intended:

Code:

int main(void){

   peList *p_List;
   char *p_str = "A test string";
   void *p_vElem;
   peNode *p_Node; 

   initList(p_List);
   p_Node = createNode(p_str);
   prependNode(p_List, p_Node);
   deleteList(p_List);
}

all is fine. But what if I don't call createNode? Well, if I set p_Node to NULL, I'm still fine:

Code:

int main(void){

   peList *p_List;
   void *p_vElem;
   peNode *p_Node = NULL; 

   initList(p_List);
   prependNode(p_List, p_Node);
   deleteList(p_List);
}

This works because prependNode checks to ensure that the p_Node parameter isn't null before it adds it to a list. So in the above example, deleteList is passed an empty list, and simply frees the peList object.

But what if I don't call createNode and I don't set p_Node to NULL?

Code:

int main(void){

   peList *p_List;
   void *p_vElem;
   peNode *p_Node; 

   initList(p_List);
   prependNode(p_List, p_Node);
   deleteList(p_List);
}

This causes an error. When the p_Node pointer is declared and not initialized (either to NULL or with createNode), it contains garbage. Therefore, the aforementioned NULL check in prependNode doesn't apply, and the p_Node is added to the list. But when deleteList tries to free it, a runtime error is thrown because the node wasn't created with malloc.

So what if I try to free the list without freeing the node? This time I won't call deleteList at all:

Code:

int main(void){

   peList *p_List;
   void *p_vElem;
   peNode *p_Node; 

   initList(p_List);
   prependNode(p_List, p_Node);
   free(p_List);
}

Well, this program gets past the call to free, but then it crashes. I'm asuming that this is because I still have a peNode pointer hanging in limbo, but I'm not sure.

3. Can anyone tell me why the last program dies?

4. How can I change deleteList or prependNode to handle uninitialized nodes?

I'd like to thank you all again for you time and your input!

But what if I don't call createNode and I don't set p_Node to NULL?

Then basically you, as the programmer, would not be using the list in the way it should be used. Pointers should always be initialised to something (NULL if they're not going to be pointing to something straight away). So you should always set those pointers to NULL, or call createNode(). Lots of functions in common APIs (such as Win32) would break if you didn't initialise the parameters properly first.

That last program crashes because you're constantly playing with invalid pointers.

From what I can tell, you can't handle the cases where pointers are uninitialised. They should be initialised. The value of an uninitialised pointer isn't defined, so you can't check for it.

So make sure they're initialised properly!

Hope that helps.

Thanks for the reply. I was hoping to write something that could handle this type of misuse at runtime without killing the program. I guess I'm out of luck.

Do you have any insight on the user-defined delete and create functions?

I think I may have answered my own questions (see 1 and 2) regarding user-defined create and delete functions in a doubly-linked list. At first, I wasn't sure that I would need to include this functionality in my list. But when I began testing the list, I found a problem.

During the first round of tests, I simply hard coded string values when I was creating new list nodes. For example:

Code:

   printf("Creating an empty peList.\n");
   p_List = initList();
   printf("A peList has been created.\n");

   printf("The size of the list is %d.\n", getSize(p_List));

   printf ("Creating a new Node with a string value: \"ABC\".\n");
   p_Node = createNode("\"ABC\"");

   printf("Prepending the node to the list.\n");
   prependNode(p_List, p_Node);

   printf("The size of the list is %d.\n", getSize(p_List));

   printf ("Creating a new Node with a string value: \"XYZ\".\n");
   p_Node = createNode("\"XYZ\"");

   printf("Prepending the node to the list.\n");
   prependNode(p_List, p_Node);

... and so on. This worked as expected. (Defintions of the data structures and createNode and prependNode are listed earlier in this post). If I were to print the list, I would get :

"XYZ"
"ABC"

However, I used a menu interface during my second round of tests so that I could chose the size and content of the list at runtime.

So, if I chose the menu option to prepend a node to the test list, doPrependNode is called:

Code:

void doPrependNode(peList *p_List){

   char *p_strData;
   peNode *p_Node = NULL;

   p_strData = getData("\n\nPlease enter data for Node \n)");
   p_Node = createNode(p_strData);
   prependNode(p_List, p_Node);

}

Since getData returns a pointer to a global buffer, and the only memory allocated for data in createNode is for a void pointer, the contents of each node changes after each insertion:

Code:

// GLOBAL
static char bufr[129];

Code:

char* getData(char *p_strPrompt){

   int ch;
   int i = 0;

   printf("%s\n", p_strPrompt);
   scanf("%s", bufr);

   puts(bufr);

   return (bufr);

}

Now, if I select prependNode from the menu and enter "ABC", and then select it again and enter "XYZ", the list will contain:

"XYZ"
"XYZ"

This is because I'm storing the address of bufr in each node. But the content of bufr changes with each call to getData.

I think this illustrates why I need to have the programmer define createNode, deleteNode and the dataType of the node's content (which might be more complicated than a string) during list initialization.

Q: Is this the case, or have I just defined getData incorrectly?

Thank you!

Thanks for the reply Quzah. The general questions I have are : Should I have function pointers in my peList struct that are to be initialized with createNode and deleteNode functions? Is this the only way that my list library can dynamically handle any and all types of node data?

Thanks.

Yes, the user of the list library would need to implement a function or functions to get node data. The data within a peNode is represented as a void pointer (p_vElem). If a user wanted to use the list library to create a list of integers, then getData (or something like it) might query the user, read a file, etc. for an integer. If another user wanted to create a list of his/her own struct typedef, then there might be a series of getData-like functions to fill in the structure data. Since I'm using a void pointer to store node data, I would think that the user would have to implement 'getData' functionality.

The code I posted on 04-13-2005 is test code for the actual library. Here getData returns a character pointer, but when I get my user-defined createNode and deleteNode issues ironed out, I'll write functions to test lists with many other data types.

So, you are correct: the users must provide their own functions to "fill up the data". You suggest that I should therefore "allow them to write their own allocation and freeing functions too". It would be great to add user-defined create and destroy functionality to the library as a user option. But it appears to me that these functions would need to be supplied by the user if I'm using a void pointer for data. Isn't this the case?

In other words, of what use are the createNode, removeNode and deleteList functions as defined above if they don't address (<--no pun intended) memory management for the actual data type? If they were to be used as the default create and cleanup functions, how would a user who didn't define their own use the library to create a list of various data types?

Thank you, Quzah, for digging in to this with me!