Thread: Linked list question.

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    60

    Linked list question.

    Hey I am having trouble with this function.
    It's arguements are 2 integrs and the beginning of the linked list.
    the list begins with one node, which has the value [ 0 | 9999 | / ]

    the first integer is where the break should start. and the second integer is for how many "blocks" it should continue till the next node can start.

    first call: deallocateNode(1000, 100, &h);
    prints two nodes: [ 0 | 999 | ]-----> [ 1100 | 9999 | / ] which is correct.

    second call: deallocateNode(500, 100, &h);

    prints two nodes instead of three: [ 0 | 499 | ]-----> [ 1100 | 9999 | / ]

    but should print: [ 0 | 499 | ]-----> [ 600 | 999 | ]-----> [ 1100 | 9999 | / ]

    why is the node [ 600 | 999 | ] not being printed?

    thanks.



    Code:
    /*the list*/
    struct node {
    	int start;
    	int end;
    	struct node *nextPtr;
    };
    
    /*function deallocateNode*/
    void deallocateNode(int p, int q, struct node **h) {
    	struct node *newPtr, *previousPtr, *currentPtr;
    	if((newPtr = (struct node *)malloc(sizeof(struct node))) == NULL) {
    		printf("Node allocation failed. \n");
    		exit(1);
    	}
    	if(newPtr != NULL) { /*create a new node*/
    		if(p < (*h)->end) {
    			newPtr->start = (*h)->start;
    			printf("newPtr->start &#37;d", newPtr->start);
    			newPtr->end = p-1;
    			newPtr->nextPtr = NULL;
    		}
    
    		previousPtr = NULL;	/*initialize nodes*/
    		(*h)->start = p + q;
    		currentPtr = (*h);
    
    		while(currentPtr != NULL) {
    			previousPtr = currentPtr;
    			currentPtr = currentPtr->nextPtr;
    			printf("WHILE LOOP \n");
    		}
    		
    		
    		newPtr->nextPtr = previousPtr;
    		previousPtr->nextPtr = currentPtr;
    		(*h) = newPtr;
    
    	}
    }
    
    
    /*just the print function */
    void print_list(struct node *h) {
    	if (h == NULL) {
    		printf("The list is empty.\n");
    	}
    	else {
    		printf("Values in the list are:\n");
    		while(h!= NULL) {
    			printf("%d %d\n", h->start, h->end);
    			h = h->nextPtr;
    		}
    	}
    }
    Last edited by gp364481; 09-30-2008 at 10:05 AM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You should always work it out on a piece of paper. When I worked it out, this is what happened:
    1. newPtr was set to a new node, 0--499.
    2. *h was changed to become 600--999.
    3. The while loop walked the old list until it got to the end.
    4. newPtr was set to point to the end of the old list.
    5. *h was changed to point to newPtr, thus leaking the old *h (the node from 600--999, which nothing is pointing at any more).

    You probably don't need to walk the list in this case, just set newPtr->next to point to h, set *h to newPtr and go.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    60
    Quote Originally Posted by tabstop View Post
    You should always work it out on a piece of paper. When I worked it out, this is what happened:
    1. newPtr was set to a new node, 0--499.
    2. *h was changed to become 600--999.
    3. The while loop walked the old list until it got to the end.
    4. newPtr was set to point to the end of the old list.
    5. *h was changed to point to newPtr, thus leaking the old *h (the node from 600--999, which nothing is pointing at any more).

    You probably don't need to walk the list in this case, just set newPtr->next to point to h, set *h to newPtr and go.


    Revised function:
    Code:
    void deallocateNode(int p, int q, struct node **h) {
    	struct node *newPtr, *previousPtr, *currentPtr;
    	if((newPtr = (struct node *)malloc(sizeof(struct node))) == NULL) {
    		printf("Node allocation failed. \n");
    		exit(1);
    	}
    	if(newPtr != NULL) { /*create a new node*/
    		if(p < (*h)->end) {
    			newPtr->start = (*h)->start;
    			printf("newPtr->start %d", newPtr->start);
    			newPtr->end = p-1;
    			newPtr->nextPtr = NULL;
    		}
    
    		previousPtr = NULL;	/*initialize nodes*/
    		(*h)->start = p + q;
    		currentPtr = (*h);
    
    		newPtr->nextPtr = currentPtr;
    		(*h) = newPtr;
    
    	}
    }
    Thanks alot.
    linked lists are confusing. I was working it out on paper though. I just couldnt see that by walking through the list I was making the node that I needed equal NULL.
    Now it works fine. Thanks again.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. linked list question
    By brb9412 in forum C Programming
    Replies: 16
    Last Post: 01-04-2009, 04:05 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM