Linked list remove() and free()

Question

How can I improve my remove function? Could someone also give me a solid explanation of the free() function?

Here is my remove function:

void removeData(void *data, struct accList *theList)
{
  if(theList->head == NULL)                  //nothing can be deleted
    return;
  else if(theList->head == theList->tail)          //there is only one element in the    list
  {
    free(theList->head);
    theList->head = theList->tail = NULL;
  }
  else if(data == theList->head->data)           //the node to be deleted is the head
  {
    struct accListNode *temp = theList->head;
    free(theList->head);
    theList->head = temp;
    theList->head->next = temp->next;
  }
  else if(data == theList->tail->data)      //the node to be deleted is the tail
  {
    struct accListNode *cur;
    for(cur = theList->head; cur->next->next != NULL; cur = cur->next);
    theList->tail = cur;
    free(cur->next);
    cur->next = NULL;
  }
  else                                     //the node to be deleted is any other node
  {
    struct accListNode *cur;
    for(cur = theList->head; cur != NULL; cur = cur->next)
    {  
      if(cur->data == data)     //this is the node we must delete from theList
      {
        struct accListNode *temp = cur->next->next;
        free(cur->next);
        cur->next = temp;
        break;
      }
    }
  }
}

Answer 1

First, about free(). If you need memory, you call malloc() and it will give you a pointer that points to a block of memory that is yours now. The OS will (hopefully) take care that no one else will use this memory. But, as with all resources, be it sockets, open files or threads, you will have to relinquish this memory at one time. At the latest, when your application exits. Better, before that, ideally the moment you don't need it anymore. And that's what free() is for. That pointer you got from malloc()? Give it to free() and you're telling the OS that you're done with this particular block of memory. This will allow other programs to reutilize the memory and keeps your memory footprint small. However, that means that you shouldn't use this memory yourself again. The mean thing is that using the memory anyway might not crash your application right away. That's why it's always a good idea to set a pointer to NULL right after freeing it. That way, if you try to use this pointer again, it will crash directly, making it more obvious where the error is.

If you don't free memory you allocated, it's a memory leak. Especially if this happens periodically, it can be a real problem, because the longer your program runs, the more memory it consumes. Memory it doesn't use, but other programs might need. So always free your memory. Use tools like valgrind to check for leaks and other problems.

Now, to your function. I spotted one little error:

struct accListNode *temp = theList->head;
free(theList->head);
theList->head = temp; // Does nothing
theList->head->next = temp->next; // Potential crash

I think the first line should read

struct accListNode *temp = theList->head->next;

Otherwise, the third line does nothing (it's just the first line in reverse) and the fourth will sooner or later lead to a crash because you're accessing free'd memory.

Then, there's the second case, where there's only one element in the list. Are you sure you want to remove that element without first checking if it's actually the data that was requested to be removed?

And a small optimization in the last case:

for(cur = theList->head->next; cur != theList->tail; cur = cur->next)

You've already established that the data to remove isn't in the tail or head, so you don't need to check them again. The rest is just stylistic:

if(theList->head == NULL)
    return;

Even if it's only one line, it's good practice to put braces around it:

if(theList->head == NULL) {
    return;
}

Also, you use struct accList a lot. You can make a typedef like so:

typedef struct accList accList

It looks a little weird, but after that, you can replace all your struct accList with just accList. To better distinguish it from a variable name, I also recommend renaming it to AccList.

Answer 2

I find it easier when working with hierarchical data structures that the functions you write should be written recursively to make your job as simple as possible. These types lends themselves well for such methods.

The typical structure for such methods will usually have this form:

1. For operations that alter the structure (i.e., add or remove items), it will accept an object to modify and return the modified item. The modified item may or may not be the same exact object that was passed in, depending on the operation you're doing and the state of the object (more on that later). You might be thinking your function does something like this: search through a list to remove an object. Instead, you should be thinking of your functions like this: given a list, return a list that has an object removed from the list.

2. They will be recursive usually doing some operation on the first object in the collection and recursively be called on the rest. The recursion is what drives the code so you generally would not have loops going through the collection. That's not to say you will never have loops, you might have loops going through a subset of the collection, just not the whole collection.

3. Being recursive, the function will perform different actions depending on the state of the object so you'll usually have a set of if/else statements (or if possible, switch). Ideally there'd be only 2-4 different conditions at most. The key is that the conditions should be as general as possible. i.e., have cases for an empty collection, one item and more than one item; don't have cases for an empty collection, one item, two items, three items, four, five, etc.

As a side note, you should have separate functions defined to perform the different node manipulations. e.g., functions to create/initialize a new node, to destroy a node, etc. You will need to perform these operations a lot so there you should minimize the amount of copy/pasting to do these.

Though this is C, you should follow C naming conventions. You shouldn't use camelCase, but rather underscore_separated_words (I don't know if there's a name for this convention). I'd recommend naming functions in this form: [type name]_[operation].

Personally, I'd create typedefs for your types rather than using raw structs, makes things easier to use and cleaner IMHO.

To rewrite your remove function to follow this form, it would look more like this:

typedef struct _acc_list_node {
    struct _acc_list_node *next;
    void *data;
} *acc_list_node;
typedef struct _acc_list {
    acc_list_node head;
} *acc_list;

/* you should have a corresponding acc_list_node_create() function */
static void acc_list_node_destroy(acc_list_node node)
{
    free(node);
}

/* this is the actual ("private") implementation */
static acc_list_node acc_list_node_remove(acc_list_node root, void *data)
{
    acc_list_node tail;

    /* the list is "empty", no changes to be made */
    if (root == NULL)
    {
        return root;
    }

    /* current node has the data, remove (omit) it */
    if (root->data == data)
    {
        tail = root->next;
        acc_list_node_destroy(root);
        return tail;
    }

    /* current node does not contain the data, remove data from the tail (if possible) */
    root->next = acc_list_node_remove(root->next, data);

    return root;
}

void acc_list_remove(acc_list list, void *data)
{
    if (list == NULL || data == NULL)
        return;
    list->head = acc_list_node_remove(list->head, data);
}

---

The free() function is just a function that frees ("deletes") dynamically allocated memory (memory that was requested from the runtime by a program when running). You will usually see it in conjunction with malloc() or calloc() (functions that request memory from the runtime).

Think of it this way, functions like malloc() allow you to ask the operating system for some memory. You're free to do whatever you want with that memory for the lifetime of your program. When you're done with that memory, you'd use free() to give that memory back to the operating system.

Answer 3

At least in my opinion, the explicit checks for the head or tail being the one you want to remove is pretty much a waste of time and effort.

I'd just walk through the list until you find the correct data or hits the end of the list. I'm also a bit worried about the way you're currently doing comparisons -- you're comparing the address of the data you're searching for to the address of the data in the node. To work reasonably, you normally want to compare the data at the locations, rather than the addresses at which they happen to be stored. To do this, I'd add a field to your structure to say how long its data is.

typedef struct accList acc_list;

void remove_data(void *data, size_t len, acc_list *list) {
    while (list != NULL && memcmp(data, list->data, len)
       list=list->next;
    if (list != NULL) {
        acc_list *temp = list->next;
        free(list->data);
        list->data = temp->data;
        free(temp);
    }
}