C linked list implementation

Question

For the following C linked list implementation, please give me some suggestions for improved efficiency, style and design. This implementation is not 100% complete, please give some suggestions for additional features. Notice the data type for the list is void*, I want it to be as generic as possible.

accList.h:

#ifndef ACCLIST_H
#define ACCLIST_H

#include <stdio.h>
#include <stdlib.h>

struct accListNode                 //the nodes of a linked-list for any data type
{
  void *data;                     //generic pointer to any data type
  struct accListNode *next;       //the next node in the list
};

struct accList                    //a linked-list consisting of accListNodes
{
  struct accListNode *head;
  struct accListNode *tail;
  int size;
};

void accList_allocate(struct accList *theList);           //allocate the accList and set to NULL
void appendToEnd(void *data, struct accList *theList);    //append data to the end of the accList
void removeData(void *data, struct accList *theList);         //removes data from accList

#endif

accList.c:

#include "accList.h"
#include "cmpsc311.h"

void accList_allocate(struct accList *theList)    //allocate and initialize to NULL values
{
   theList = Malloc(sizeof(struct accList));
   theList->head = NULL;
   theList->tail = NULL;
   theList->size = 0;
}

void appendToEnd(void *data, struct accList *theList)
{
  struct accListNode *newNode = Malloc(sizeof(struct accListNode));
  newNode->data = data;
  newNode->next = NULL;
  if(theList->head == NULL)    //the list is empty
  {
    theList->head = theList->tail = newNode;
  }
  else                        //the list is not empty
  {
    theList->tail->next = newNode;
    theList->tail = newNode;
  }
}

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

I think the remove function needs the most work. I did post that function on this site, however I think I needed to include the whole implementation to get the best feedback. Will this work on an embedded system?

Answer 1

Several problems I see:

accList_allocate

accList_allocate doesn't do what you probably think. It creates a new accList, yes, but this new one will not be visible to the caller (and thus, will be lost as memory leakage). If you want to initialize the pointer passed to it, use a pointer-to-pointer:

void accList_allocate(struct accList **outList)    //allocate and initialize to NULL values
{
   struct accList* theList = Malloc(sizeof(struct accList));
   theList->head = NULL;
   theList->tail = NULL;
   theList->size = 0;
   *outList = theList;
}

Also, you should really check the return value of Malloc. Especially on embedded systems, there's a real possibility of running out of memory. Let the caller handle the error, but tell him that something's wrong.

appendToEnd

Same as with accList_allocate, check Malloc's return value and return some kind of error code if it's NULL. What you're writing there is library code that should always handle errors gracefully and let the caller decide whether to crash and burn or recover and try again.

removeData

Please refer to my answer in your other thread.

Answer 2

I see two issues with the removeData function. The first is in the "single item list" section:

else if(theList->head == theList->tail)                   //there is one element in the list
{
  free(theList->head);
  theList->head = NULL;
}

What happens if I have a list with a single item in it, and I ask the removeData() function to remove a piece of data that isn't in the list? It'll remove the wrong item instead of ignoring the function call. It should really look like this:

else if(theList->head == theList->tail)                   //there is one element in the list
{
  if (theList->head->data == data) {
    free(theList->head);
    theList->head = NULL;
    theList->tail = NULL;
  }
}

Note that I also set the tail pointer to NULL, which you've missed.

Secondly, the section of the function that deals with searching for the data within the list should really exit once it finds a match, unless you are specifically intending to remove all instances of data from the list.

Here's the code:

if(cur->data == data)   //this is the node we must free
{
  prev->next = cur->next;
  free(cur);
}

Here's what I'd do:

if(cur->data == data)   //this is the node we must free
{
  prev->next = cur->next;
  free(cur);
  return;
}

To make it more obvious what's going on, I'd probably rename the function to removeFirstInstance(), and maybe have another function called removeAllInstances() that followed your current design, but that's somewhat anathema to the terseness of idiomatic C (I like descriptive names rather than obtuse names that encourage me constantly to have the API docs open).

I can also see an opportunity for a tiny optimisation:

for(cur = theList->head; cur != NULL; prev = cur, cur = cur->next)

You already know that the data isn't stored in the head node from earlier if statements, so you can skip the first item in the search loop:

for(cur = theList->head->next; cur != NULL; prev = cur, cur = cur->next)

If I were to rewrite this method it'd probably look like this:

void removeData(void *data, struct accList *list) {

    struct accListNode *previous = NULL;
    struct accListNode *current = list->head;

    while (current != NULL) {

        if (current->data == data) {

            if (list->head == current) list->head = current->next;
            if (list->tail == current) list->tail = previous;

            if (previous != NULL) previous->next = current->next;

            free(current);
            --size;
            return;
        }

        previous = current;
        current = current->next;
    }
}

I'd forgo the micro-optimsation of all of the guard clauses in favour of a shorter method.

One more problem that applies generally: you have a size value in the list struct but you never change its value. Either increase it in the append function and decrease it in the remove function or remove it from the struct. As it stands it is misleading.

Answer 3

Isn't this an issue?

void appendToEnd(void *data, struct accList *theList)
{
  struct accListNode *newNode = Malloc(sizeof(struct accListNode));
  newNode->data = data;   <===

What happens if the input is freed. The linked list will also lose the value. I think the value should be copied here.