Problem with fundamental understanding of double link list

This is a discussion on Problem with fundamental understanding of double link list within the C Programming forums, part of the General Programming Boards category; Hi, I am very frustrated right now. Sometimes my functions work and sometimes they dont. This is how I have ...

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    4

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    May 2010
    Posts
    4
    Quote Originally Posted by tabstop View Post
    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.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by bbjunaid View Post
    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.

  6. #6
    Registered User
    Join Date
    May 2010
    Posts
    4
    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

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Error in printf line,,,what's wrong?
    By mft_ika in forum C Programming
    Replies: 9
    Last Post: 03-19-2010, 09:46 PM
  2. Functions, have errors...NEED HELP FAST
    By alkamenes in forum C++ Programming
    Replies: 6
    Last Post: 11-02-2009, 03:00 PM
  3. One more linked list implementation
    By BlackOps in forum C Programming
    Replies: 17
    Last Post: 07-16-2009, 10:34 PM
  4. Linked List, Please Help!
    By CodeMonkeyZ in forum C Programming
    Replies: 5
    Last Post: 02-17-2009, 06:23 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21