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;
		}
	}
}

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.

Originally Posted by tabstop

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.