Linked List search() and delete() trouble

Got a bit of trouble figuring out where my code is going wrong for a Linked List in C (not C++)...

Both removefirst() and freeNode() work correctly. There's also a few lines of stderr output as debugging, so I can tell how far the methods get before the error. It seems to error when trying to delete a node other than the first node in the list.

nodePtr is a typedef of a nodeType *, and nodeType is a struct: {int info; nodeType * right}.

Can anyone shed some light on what pointer or variable I've got screwed up? I know I've got the algorithm right, it's just a bit of confusion over which pointer isn't getting the correct value... it seems as though the lptr (lead pointer) and tptr (trailing pointer) aren't being assigned correctly in the search() method, as they seem to always return with their original values (lptr = front, tptr = NULL).

Code:

---

boolean search(nodePtr front, nodePtr * lptr, nodePtr * tptr, infoType target)
/* return true if target is in the list, false otherwise */
/* lptr should point to node where target found, and */
/* tptr should point to the trailing node or be NULL */
{
    *lptr = front;
    *tptr = NULL;

    while ((*lptr != NULL) && (front->info != target))
    {
        tptr = lptr;
        *lptr = (*lptr)->right;
    }

    return (lptr != NULL);
}

void deleteNode (nodePtr * front, infoType target)
/* delete the node containing target */
{
    nodePtr tptr, lptr;
   
    if (search(*front, &lptr, &tptr, target) == true)
    {
        fprintf(stderr, "FOUND!\n");
       
        if ((tptr == NULL) && (lptr != NULL))
        {
            fprintf(stderr, "Deleting first node!\n");
            removefirst(front);
        }
        else
        {
            fprintf(stderr, "Deleting node other than first!\n");
            tptr->right = lptr->right;
            freeNode(lptr);
        }
    }
}

---

Look at your while loop's declaration:

Code:

---

while ((*lptr != NULL) && (front->info != target))

---

The assignment of the trailing pointer:

Code:

---

tptr = lptr;

---

And what you're returning:

Code:

---

return (lptr != NULL);

---

Quote:

---

Originally Posted by cma

Look at your while loop's declaration:

Code:

---

while ((*lptr != NULL) && (front->info != target))

---

---

Ah... hehe... don't you hate it when it's something that stupid that's holding the program up?

Quote:

---

Originally Posted by cma

The assignment of the trailing pointer:

Code:

---

tptr = lptr;

---

---

I thought I could assign a pointer-to-a-pointer to a pointer-to-a-pointer that way? Hmmm... guess I gotta use "*tptr = *lptr". It seems to work with that now.

Quote:

---

Originally Posted by cma

And what you're returning:

Code:

---

return (lptr != NULL);

---

---

Weird -- the code works regardless of whether it's "return *lptr != NULL" or "return lptr != NULL".

Thanks for the help!

I have the same problem i am trying to delete a part of a linked list I have the code

Code:

---


void deleteitem(struct list *fly)
{
        int deletenumber;
        int count=0;

        scanf("%i", &deletenumber);
       
        goto_head(fly);

        for(count = 0 ; count == deletenumber ; count ++)
        {
                        goto_next(fly);
                       
        }

                        delete(fly);
                               
               
}

---

and I don't know how to delete an item out of the linked list at the location deletenumber, this code keeps taking the first part out can some one tell me what i need to fix it.

Quote:

---

I thought I could assign a pointer-to-a-pointer to a pointer-to-a-pointer that way? Hmmm... guess I gotta use "*tptr = *lptr". It seems to work with that now.

---

Remember, you're simulating pass-by-reference, **tptr is the actual node, *tptr contains the address of the node, and tptr contains the address of the address of the node. And you should do

Code:

---

return (*lptr != NULL);

---

since the way you have it, it will always return true.


Robbo99, look at your loop declaration:

Code:

---

for(count = 0 ; count == deletenumber ; count ++)

---

Quote:

---

Originally Posted by cma

And you should do

Code:

---

return (*lptr != NULL);

---

since the way you have it, it will always return true.

---

I understand, but it does return false sometimes when written as "lptr != NULL". I have filled a linked list with ascending integers from 1 to 25, then wrote a loop starting at 1 and incrementing by two every pass (essentially, odd numbers) and removed the incrementer value from the list every pass.

Either way I write it, I still end up with a linked list filled only with even numbers, just as expected... why? Could it be the system I run it on (FreeBSD UNIX/Mac OS X)?

Strage... it runs fine on my Mac OS X box, it runs fine on a Solaris box... but on a Fedora Core 2 box, it throws a segmentation fault and dumps the core.

Quote:

---

Originally Posted by Judas1012

Strage... it runs fine on my Mac OS X box, it runs fine on a Solaris box... but on a Fedora Core 2 box, it throws a segmentation fault and dumps the core.

---

We don't have your full program, so no one can really give you a definite answer as to what is wrong. More than likely, the program is not running fine on the systems you're claiming it is running on. You are just lucky that the program behaves "normally".

You should post your program (do not forget a main() function) that duplicates the error. That's the fastest way anyone here can see if you're doing anything wrong.

Regards,

Paul McKenzie

Code:

---

for(count = 0 ; count == deletenumber ; count ++)

---

The loop is executed while the "middle section" is true. Say deletenumber is 5.
The loop will not be entered. change "==" to either "<" or "<=" , depending
on your need.

Full program to follow... three files: linkedList.c, linkedList.h, linkedListMain.c.

First, linkedList.c:

Code:

---

#include "linkedList.h"

void clear(nodePtr * front)
/* delete all items from the list */
{
    nodePtr tptr = NULL;
    while (*front != NULL)
    {
        tptr = *front;
        *front = (*front)->right;
        freeNode(tptr);
    }
}

void prepend(nodePtr * front, infoType newinfo)
/* add an item to the front of the list */
{
    nodePtr newNodePtr;
    if ((newNodePtr = (nodePtr)malloc(sizeof(nodeType))) == NULL)
    {
        fprintf(stderr, "Unable to malloc new node for prepending\n");
        return;
    }
    else
    {
        newNodePtr->info = newinfo;
        newNodePtr->right = *front;
        *front = newNodePtr;
    }
}

void removefirst(nodePtr * front)
/* delete the first item from the list */
{
    if (!isEmpty(*front))
    {
        nodePtr oldNodePtr = *front;
        *front = (*front)->right;
        freeNode(oldNodePtr);
    }
}

void append(nodePtr * front, infoType newinfo)
/* add an item to the end of the list */
{
    nodePtr newNodePtr;
    if ((newNodePtr = (nodePtr)malloc(sizeof(nodeType))) == NULL)
    {
        fprintf(stderr, "Unable to malloc new node for appending\n");
        return;
    }
   
    newNodePtr->info = newinfo;
    newNodePtr->right = NULL;
   
    if (!isEmpty(*front))
    {
        nodePtr iterator = *front;
       
        while(iterator != NULL && iterator->right != NULL)
        {
            iterator = iterator->right;
        }
        iterator->right = newNodePtr;
    }
    else
    {
        prepend(front, newinfo);
    }
}

boolean isEmpty(const nodePtr front)
/* return true if list is empty, false otherwise */
{
    return (front == NULL);
}

int count(nodePtr front)
/* return the number of items in the list */
{
    int i = 0;
    while (front != NULL)
    {
        i++;
        front = front->right;
    }
    return i;
}

void freeNode(nodePtr ptr)
/* free node pointed to by ptr */
{
    if (ptr != NULL)
    {
        free(ptr);
    }
}

void printList(nodePtr ptr)
/* print the list */
{
    while (ptr != NULL)
    {
        fprintf(stdout, "%i ", ptr->info);
        ptr = ptr->right;
    }
    fprintf(stdout, "\n");
}

boolean search(nodePtr front, nodePtr * lptr, nodePtr * tptr, infoType target)
/* return true if target is in the list, false otherwise */
/* lptr should point to node where target found, and */
/* tptr should point to the trailing node or be NULL */
{
    *lptr = front;
    *tptr = NULL;

    while ((*lptr != NULL) && ((*lptr)->info != target))
    {
        *tptr = *lptr;
        *lptr = (*lptr)->right;
    }

    return (*lptr != NULL);
}

void deleteNode (nodePtr * front, infoType target)
/* delete the node containing target */
{
    nodePtr tptr, lptr;
   
    if (search(*front, &lptr, &tptr, target) == true)
    { 
        if ((tptr == NULL) && (lptr != NULL))
        {
            removefirst(front);
        }
        else
        {
            tptr->right = lptr->right;
            freeNode(lptr);
        }
    }
}

void insertAfter(nodePtr ptr, infoType newinfo)
/* precondition: ptr != NULL */
/* insert a new node after ptr */
{
    nodePtr newNodePtr;
    if ((newNodePtr = (nodePtr)malloc(sizeof(nodeType))) == NULL)
    {
        fprintf(stderr, "Unable to malloc new node for insertion after\n");
        return;
    }
   
    newNodePtr->info = newinfo;
    newNodePtr->right = ptr->right;
    ptr->right = newNodePtr;
}

void inPlace(nodePtr * front, infoType newinfo)
/* insert an item in ascending order using prepend or insertAfter */
{
    nodePtr tptr = NULL, lptr = *front;
    while ((lptr != NULL) && (lptr->info < newinfo))
    {
        tptr = lptr;
        lptr = lptr->right;
    }
   
    if (tptr != NULL)
    {
        insertAfter(tptr, newinfo);
    }
    else
    {
        prepend(front, newinfo);
    }
}

---

linkedList.h:

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>*** /* for srand() and rand() */


typedef int infoType;

typedef struct nodeType
{
infoType info;
struct nodeType * right;
} nodeType;

typedef nodeType * nodePtr;

typedef int boolean;
enum boolean {false, true};

void clear(nodePtr * front);
/* delete all items from the list */

void prepend(nodePtr * front, infoType newinfo);
/* add an item to the front of the list */

void removefirst(nodePtr * front);
/* delete the first item from the list */

void append(nodePtr * front, infoType newinfo);
/* add an item to the end of the list */

boolean isEmpty(const nodePtr front);
/* return true if list is empty, false otherwise */

int count(nodePtr front);
/* return the number of items in the list */

void freeNode(nodePtr ptr);
/* free node pointed to by ptr */

void printList(nodePtr ptr);
/* print the list */

boolean search(nodePtr front, nodePtr * lptr, nodePtr * tptr, infoType target);
/* return true if target is in the list, false otherwise */
/* lptr should point to node where target found, and */
/* tptr should point to the trailing node or be NULL */

void deleteNode (nodePtr * front, infoType target);
/* delete the node containing target */

void insertAfter(nodePtr ptr, infoType newinfo);
/* precondition: ptr != NULL */
/* insert a new node after ptr */

void inPlace(nodePtr * front, infoType newinfo);
/* insert an item in ascending order using prepend or insertAfter */

---

linkedListMain.c:

Code:

---

#include "linkedList.h"

int main()
{
    nodePtr list;
    int i;
   
    srand((unsigned)time(NULL));
   
    fprintf(stderr, "Inserting numbers 1 to 25 (prepend):\n");
    for (i = 1; i <= 25; i++)
    {
        prepend(&list, i);
    }
    printList(list);
    fprintf(stderr, "Number of items in list: %i\n", count(list));
    clear(&list);
    fprintf(stderr, "List cleared\n\n");
   
    fprintf(stderr, "Inserting numbers 1 to 25 (append):\n");
    for (i = 1; i <= 25; i++)
    {
        append(&list, i);
    }
    printList(list);
    fprintf(stderr, "Deleting all odd numbers...\n");
    for (i = 1; i <= 25; i += 2)
    {
        deleteNode(&list, i);
    }
    printList(list);
    fprintf(stderr, "Number of items in list: %i\n", count(list));
    clear(&list);
    fprintf(stderr, "List cleared\n\n");

    fprintf(stderr, "Inserting 25 random numbers (inPlace):\n");
    for (i = 0; i < 25; i++)
    {
        inPlace(&list, rand() % 100);
    }
    printList(list);
}

---

Any insight would be greatly appreciated. Thanks for all the help!

Here is one problem:

Code:

---

void printList(nodePtr ptr)
/* print the list */
{
    while (ptr != NULL)
    {
        fprintf(stdout, "%i ", ptr->info);
        ptr = ptr->right;
    }
    fprintf(stdout, "\n");
}

---

Note that you are checking for NULL to terminate the while() loop. The problem is that the passed-in ptr is not guaranteed to have NULL as the terminator. The reason why is this:

Code:

---

//...
void prepend(nodePtr * front, infoType newinfo)
/* add an item to the front of the list */
{
    nodePtr newNodePtr;
    if ((newNodePtr = (nodePtr)malloc(sizeof(nodeType))) == NULL)
    {
        fprintf(stderr, "Unable to malloc new node for prepending\n");
        return;
    }
    else
    {
        newNodePtr->info = newinfo;
        newNodePtr->right = *front;
        *front = newNodePtr;
    }
}

// From main()
    for (i = 1; i <= 25; i++)
    {
        prepend(&list, i);
    }
    printList(list);
 
//...

---

Nowhere in prepend() do you set a node to NULL. The subsequent call to printList() causes an exception right away when I ran this under VC++ 6.0, and possibly the reason why it GPF's on one of your machines.

So basically, you are missing the terminating NULL node. Change the line in main() to this:

Code:

---

    nodePtr list=NULL;

---

I didn't debug beyond this point, but doing this stops the error from occuring. You also have a memory leak, since you don't free all the nodes you malloc()ed (reported by BoundsChecker). You can check this by outputting every time you call malloc() the pointer that is returned, and when you call free() the pointer to the memory that's deallocated. Match up the malloc values with the free() values -- if they don't match, you have a memory leak.

One such memory leak is in your append() function and then when you call deleteNode()-- you never delete the first node in the list that you append() (this is easily checked -- the first node allocated when append() is called is never deallocated).

You also didn't call clear() at the end of your program, causing a memory leak. Even though it is the end of the program, never leave these memory leaks in the program.

Regards,

Paul McKenzie

Hmm... I'm not sure what you mean by "you never deallocate the first node malloc'ed in append()" -- I malloc a new node to be placed on the list, and then add it to the list. It gets deallocated when I remove the node from the list, using the "deleteNode()" method, doesn't it? When the last node is deleted using the "removefirst" method, I define a new nodePtr that points to the front node, then assign the front node to front->right (and if that were the last node in the list, would get assigned NULL) and then I free the pointer I assigned to the front... doesn't that take care of it?

Edit: nevermind, I found it -- when I call "append()" and the if-else statement executes the else statement (for times when adding to an empty list) I forgot to free my node and THEN call "prepend()", since prepend mallocs ANOTHER node.

I think I got it right now (I left my debugging "fprintf()" statements in to check):

Code:

---

#include "linkedList.h"

void clear(nodePtr * front)
/* delete all items from the list */
{
    nodePtr tptr = NULL;
    while (*front != NULL)
    {
        tptr = *front;
        *front = (*front)->right;
        freeNode(tptr);
    }
}

void prepend(nodePtr * front, infoType newinfo)
/* add an item to the front of the list */
{
    nodePtr newNodePtr;
    if ((newNodePtr = (nodePtr)malloc(sizeof(nodeType))) == NULL)
    {
        fprintf(stderr, "Unable to malloc new node for prepending\n");
        return;
    }
    else
    {
        newNodePtr->info = newinfo;
        newNodePtr->right = *front;
        *front = newNodePtr;
        fprintf(stderr, "Malloc'ed: %i\n", newNodePtr->info);
    }
}

void removefirst(nodePtr * front)
/* delete the first item from the list */
{
    if (!isEmpty(*front))
    {
        nodePtr oldNodePtr = *front;
        *front = (*front)->right;
        freeNode(oldNodePtr);
    }
}

void append(nodePtr * front, infoType newinfo)
/* add an item to the end of the list */
{
    nodePtr newNodePtr;
    if ((newNodePtr = (nodePtr)malloc(sizeof(nodeType))) == NULL)
    {
        fprintf(stderr, "Unable to malloc new node for appending\n");
        return;
    }
   
    newNodePtr->info = newinfo;
    newNodePtr->right = NULL;
    fprintf(stderr, "Malloc'ed: %i\n", newNodePtr->info);
   
    if (!isEmpty(*front))
    {
        nodePtr iterator = *front;
       
        while(iterator != NULL && iterator->right != NULL)
        {
            iterator = iterator->right;
        }
        iterator->right = newNodePtr;
    }
    else
    { 
        freeNode(newNodePtr);
        prepend(front, newinfo);
    }
}

boolean isEmpty(const nodePtr front)
/* return true if list is empty, false otherwise */
{
    return (front == NULL);
}

int count(nodePtr front)
/* return the number of items in the list */
{
    int i = 0;
    while (front != NULL)
    {
        i++;
        front = front->right;
    }
    return i;
}

void freeNode(nodePtr ptr)
/* free node pointed to by ptr */
{
    if (ptr != NULL)
    {
        fprintf(stderr, "Freed: %i\n", ptr->info);
        free(ptr);
    }
}

void printList(nodePtr ptr)
/* print the list */
{
    while (ptr != NULL)
    {
        fprintf(stdout, "%i ", ptr->info);
        ptr = ptr->right;
    }
    fprintf(stdout, "\n");
}

boolean search(nodePtr front, nodePtr * lptr, nodePtr * tptr, infoType target)
/* return true if target is in the list, false otherwise */
/* lptr should point to node where target found, and */
/* tptr should point to the trailing node or be NULL */
{
    *lptr = front;
    *tptr = NULL;

    while ((*lptr != NULL) && ((*lptr)->info != target))
    {
        *tptr = *lptr;
        *lptr = (*lptr)->right;
    }

    return (*lptr != NULL);
}

void deleteNode (nodePtr * front, infoType target)
/* delete the node containing target */
{
    nodePtr tptr, lptr;
   
    if (search(*front, &lptr, &tptr, target) == true)
    { 
        if ((tptr == NULL) && (lptr != NULL))
        {
            removefirst(front);
        }
        else
        {
            tptr->right = lptr->right;
            freeNode(lptr);
        }
    }
}

void insertAfter(nodePtr ptr, infoType newinfo)
/* precondition: ptr != NULL */
/* insert a new node after ptr */
{
    nodePtr newNodePtr;
    if ((newNodePtr = (nodePtr)malloc(sizeof(nodeType))) == NULL)
    {
        fprintf(stderr, "Unable to malloc new node for insertion after\n");
        return;
    }
   
    newNodePtr->info = newinfo;
    newNodePtr->right = ptr->right;
    ptr->right = newNodePtr;
    fprintf(stderr, "Malloc'ed: %i\n", newNodePtr->info);
}

void inPlace(nodePtr * front, infoType newinfo)
/* insert an item in ascending order using prepend or insertAfter */
{
    nodePtr tptr = NULL, lptr = *front;
    while ((lptr != NULL) && (lptr->info < newinfo))
    {
        tptr = lptr;
        lptr = lptr->right;
    }
   
    if (tptr != NULL)
    {
        insertAfter(tptr, newinfo);
    }
    else
    {
        prepend(front, newinfo);
    }
}

---

Also -- I don't think we've been taught "clear()". Is that something I should call at the end of the program or something? I'm assuming it's for the times that I exit the program without clearing the list and freeing nodes, correct?

I got it and made the changes as well as edited my post... thanks again for the help -- I think I got it all cleared up now, except for the "clear()" statement at the end. Instead, I cleared the list, effectively freeing up the memory -- is this an equivalent procedure?

Quote:

---

Originally Posted by Judas1012

Also -- I don't think we've been taught "clear()". Is that something I should call at the end of the program or something?

---

clear() is one of your functions. You need to call the function to remove all the items from the list, which you failed to do at the end of your program.

Code:

---

void clear(nodePtr * front)
/* delete all items from the list */
{
    nodePtr tptr = NULL;
    while (*front != NULL)
    {
        tptr = *front;
        *front = (*front)->right;
        freeNode(tptr);
    }
}

---

Regards,

Paul McKenzie

Whoa... perhaps it's a little too late to be coding... sorry about that!

It's in there at the end of "main()" now, and I took care of that rogue node from the "else" part of the "append()" function. All is well is memory land now I believe.

Without calling "clear()" at the end of "main()", wouldn't the program exiting free the memory? I understand not taking care of that rogue node would be considered a memory leak, since the list may be cleared and filled a number of times before the program ends... but doesn't simply exiting the program free any memory not specifically freed by me? I know it would be horrible coding form, but would it still be considered a memory leak?

Thanks again for your help and patience.

Quote:

---

Originally Posted by Judas1012

Without calling "clear()" at the end of "main()", wouldn't the program exiting free the memory? I understand not taking care of that rogue node would be considered a memory leak, since the list may be cleared and filled a number of times before the program ends... but doesn't simply exiting the program free any memory not specifically freed by me?

---

Yes, it is still a memory leak in terms of the programming language and the execution of the code. Even though the OS may free the memory at the end, not all OS'es do this.

Regards,

Paul McKenzie

Quote:

---

Yes, it is still a memory leak in terms of the programming language and the execution of the code. Even though the OS may free the memory at the end, not all OS'es do this.

---

Do you mean it is possible for part of the heap used by a process itself to remain in main memory after the process terminates?

Quote:

---

Originally Posted by HighCommander4

Do you mean it is possible for part of the heap used by a process itself to remain in main memory after the process terminates?

---

Whether the operating system releases the memory when the program terminates depends on how the OS is implemented. There was a thread here just a couple of weeks ago discussing this.

For one, I don't believe that MS-DOS releases the memory if you use the low-level BIOS call to get the memory for you.

Regards,

Paul McKenzie

Symbian OS. You have to plug all leaks in a Symbian app before it can be released on a phone.