2
\$\begingroup\$

I recently learned about linked lists and here is my first try to write one in C. I know it's a lot of code, but I hope someone takes a look. Any tips memory allocation and improvements are welcome.

SinglyLinkedList.h

#ifndef SINGLYLINKEDLIST_
#define SINGLYLINKEDLIST_

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

typedef struct SLNode SLNode;
typedef struct SLList SLList;

struct SLNode {
  void *data;
  SLNode *next;
};

struct SLList {
  size_t size;
  SLNode *head;
};

SLList *createSLList(void);
SLNode *createSLNode(void *data);

// OPERATIONS
int addSLNode(SLList *list, SLNode *node, size_t positon);
int removeSLNode(SLList *list, size_t position);
int containsData(SLList *list, void *data, int compare(void *, void*));

void clearSLList(SLList *list);

// FREEING
void freeSLList(SLList *list);
void freeSLNode(SLNode *node);

// UTILS
void printSLList(SLList *list, void printSLNode(SLNode *));

#endif

SinglyLinkedList.c

#include "SinglyLinkedList.h"

/**
 * createSLNode: Stores passed data in SLNode and
 *               returns pointer to node.
 *
 * @param data Data to store in node. This data should be
 *             allocated with malloc/calloc/etc., since
 *             free is used in freeSLNode.
 *
 * @return Pointer to created SLNode. 
 *         NULL if memory allocation failed.
 */
SLNode *createSLNode(void *data) {
  SLNode *node = malloc(sizeof(SLNode));

  if (node == NULL) {
    return NULL;
  }

  node->data = data;
  node->next = NULL;

  return node;
}

/**
 * createSLList: Allocates space for an SLList and
 *               assigns default values (list->head: NULL,
 *               list->size: 0)
 *
 * @return Pointer to creates SLList.
 *         Null if memory allocation failed.
 */
SLList *createSLList(void) {
  SLList *list = malloc(sizeof(SLList));

  if (list == NULL) {
    return NULL;
  }

  list->head = NULL;
  list->size = 0; 

  return list;
}

/**
 * addSLNode: Adds SLNode to SLList at passed index.
 *
 * @param list  SLList to add node to.
 * @param node  SLNode which should be added to list.
 * @param index Index at which the node should be added 
 *              to list.
 *
 * @return 0 for success,
 *         1 for failure (NULL-arguments, invalid index)
 */
int addSLNode(SLList *list, SLNode *node, size_t index) {
  if (list == NULL || node == NULL) {
    return -1;
  } else if (index > list->size) {
    return -1;
  } else {
    if (index == 0) {
      node->next = list->head;
      list->head = node;
    } else {
      SLNode *tmp = list->head;
      size_t currIndex = 0;

      while (currIndex < index-1) {
        tmp = tmp->next;
        currIndex++;
      }

      node->next = tmp->next;
      tmp->next = node;
    }

    list->size++;
    return 0;
  }
}

/**
 * removeSLNode: Remove element at specific index
 *               in SLList.
 *
 * @param list  SLList to remove element from.
 * @param index Index of element to remove.
 *
 * @return 0 for success.
 *         1 for failure (NULL-arguments, invalid index)
 */
int removeSLNode(SLList *list, size_t index) {
  if (list == NULL) {
    return -1;
  } else if (index >= list->size) {
    return -1;
  } else {
    if (index == 0) {
      if (list->size == 1) {
        freeSLNode(list->head);
        list->head = NULL;
      } else {
        SLNode *tmp = list->head->next;
        freeSLNode(list->head);
        list->head = tmp;
      }
    } else {
      SLNode *tmp = list->head;
      size_t pos = 0;

      while (pos < index-1) {
        tmp = tmp->next;
        pos++;
      }

      SLNode *del = tmp->next;
      tmp->next = del->next;
      freeSLNode(del);
    }

    list->size--;
    return 0;
  }
}

/**
 * containsData: Checks if SLList contains specific data/element.
 *
 * @param list    SLList to search in.
 * @param data    Data to compare with.
 * @param compare Pointer to function, which is used
 *                to test for equality.
 *
 * @return 1 if the list contains the passed data according
 *           to the passed compare function.
 *         0 otherwise (not contained/ NULL passed as list).
 */
int containsData(SLList *list, void *data, int compare(void *, void*)) {
  if (list == NULL) {
    return 0;
  }

  SLNode *node = list->head;
  while (node != NULL) {
    if (compare(data, node->data)) {
      return 1;
    }
    node = node->next;
  }

  return 0;
}


/**
 * freeSLNode: Frees SLNode and contained data.
 *
 * @param node SLNode to free.
 */
void freeSLNode(SLNode *node) {
  if (node == NULL) {
    return;
  }

  free(node->data);
  free(node);
}

/**
 * clearSLList: Removes/frees all nodes in SLList.
 *              The data of the nodes is freed as well.
 *
 * @param list SLList to clear.
 */
void clearSLList(SLList *list) {
  if (list == NULL) {
    return;
  } else {
    SLNode *curr = list->head;

    while (curr != NULL) {  
      SLNode *tmp = curr->next;
      freeSLNode(curr);
      curr = tmp;
    }

    list->head = NULL;
    list->size = 0;
  }
}

/**
 * freeSLList: Removes/frees all nodes in SLList and
 *             frees SLList afterwards.
 * 
 * @param list SLList to free.
 */
void freeSLList(SLList *list) {
  if (list == NULL) {
    return;
  }

  clearSLList(list);
  free(list);
}

static void printSLArrow();

/**
 * printSLList: Prints an SLList (debug as main purpose).
 *
 * @param list SLList to print.
 * @param printSLNode Pointer to function,
 *                    which prints a single SLNode.
 */
void printSLList(SLList *list, void printSLNode(SLNode *)) {
  if (list == NULL) {
    return;
  }

  SLNode *tmp = list->head;

  while (tmp != NULL) {
    printSLNode(tmp);
    printSLArrow();
    tmp = tmp->next;
  }

  printf("NULL\n");
}

void printSLArrow() {
  printf("-->");
}
\$\endgroup\$
3
\$\begingroup\$

size is a bad name

size in SLList is a bad name - size may be the size of the individual elements or the total number of bytes. num_items, nitems or even length would be more clear.

if(...) return; does not need an else statement

Sometimes you write:

if(<condition>) { return; }
// rest of code

and sometimes you write:

if(<condition>) { return; }
else {
  // rest of code
}

I much prefer the first style, as it avoids adding needless indentation. Imagine you had many conditions you had to check for - if each one added indentation the resulting code would be off-screen.

Functions should not accept bad inputs

In C there is the notion of defined and undefined behaviour. Functions will do the proper thing only for a defined set of inputs. For inputs outside of those permitted, behaviour is undefined.

Your functions should not accept bad inputs. Instead you should use assert() to ensure that the user has given inputs for which the function is defined. This meanns addSLNode() and removeSLNode() should always succeed with reasonable inputs. Therefore there is no need for them to return success / failure.

containsData() is not a useful general function

This is more of a design niggle. Keep your interfaces simple. If the user of the SinglyLinkedList.h API can easily iterate through the linked list, they can quickly implement this and many other functions themselves. Focus on making iteration and accessing elements intuitive to users of this API.

Add a comment to #endif

Another minor point - #if... etc. don't usually have any indentation, so it is hard to see where #endif started. The problem grows as files get longer. I like to comment with where the conditional started:

#endif /* ifdef SINGLYLINKEDLIST_ */

Use calloc()

calloc() is just like malloc() but will initialise the memory to zero. You can use this to cut your createSLList() down to just one line with exactly the same behaviour:

SLList *createSLList(void) {
  return calloc(sizeof(SLList), 1);
}

And createSLNode() down to three lines:

SLNode *createSLNode(void *data) {
  SLNode *node = calloc(sizeof(SLNode), 1);
  if(node != NULL) node->data = data;
  return node;
}

Concise code

Finally, using the points above, it is possible to rewrite addSLNode() function in a much more concise and clear manner:

#include <assert.h>

void addSLNode(SLList *list, SLNode *node, size_t index)
{
  assert(list != NULL);
  assert(index <= list->size); // index == list->size means add to end
  size_t i;
  SLNode *prev;

  if(index == 0) {
    node->next = list->head;
    list->head = node;
  }
  else {
    prev = list->head;
    for(i = 1; i < index; i++) { prev = prev->next; }
    node->next = prev->next;
    prev->next = node;
  }
  list->size++;
}

and to remove a node:

void removeSLNode(SLList *list, size_t index)
{
  assert(list != NULL);
  assert(index < list->size);

  SLNode *prev, *node;
  size_t i;

  if(index == 0) {
    node = list->head;
    list->head = list->head->next;
  }
  else {
    prev = list->head;
    node = prev->next;
    for(i = 1; i < index; i++) { prev = node; node = node->next; }
    prev->next = node->next;
  }
  freeSLNode(node);
  list->size--;
}

Using fewer if/else conditionals results in simpler code that has fewer cases to work through when reading the code.

Side note: personally I'm a big fan of two space indentation.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you really much for your time and great review. You are right that size was a bad identifier and I was always unsure about the if-else-blocks with a return statement. Honestly this is the first time I heard about assert` in C and I really like the idea of it. And I didn't even think about using calloc. Thank you again for the great input - with love of two space indentation. \$\endgroup\$ – LastSecondsToLive Jan 21 '16 at 19:03
1
\$\begingroup\$

I like your implementation. Two observations are:

  1. There are more than a couple of situations where brackets are not needed.

     if (list == NULL) {
       return;
     }   
    
  2. Increasing indentation to 4 spaces looks great on C, it increases readability. I personally use 8 but 4 works great too.

\$\endgroup\$
1
\$\begingroup\$

Since the other reviews covered the majority of the memory management and code style topics, I'd like to focus this review on the linked list design.

Currently, your header file exposes unnecessary implementation details to the user; as a user of your linked list, I don't need to know how it is implemented. In other words, I don't need to know that your SLList is implemented using SLNodes. Also, as a user of your library, I should not be responsible for allocating/freeing individual list nodes and then be responsible for passing them into insertion functions. All these implementation details should be hidden away from the user for a couple of reasons:

  1. The implementation details can change. If they do, then the user will need to be aware of them. This is no good.
  2. Exposing them is a violation of good encapsulation practices.

What I would do is provide an opaque pointer to a SLList in the header file and leave all the implementation details in the implementation file. The header file should only contain an API that focuses on using SLLists.

I've provided my comments inline in the code.

SLList.h

#ifndef SINGLYLINKEDLIST_
#define SINGLYLINKEDLIST_

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

// define this in the imp file
typedef struct SLList SLList;

SLList *createSLList(void);

// These functions should be named in a way that doesn't expose the 
// underlying implementation.
int insert(SLList *list, void *data, size_t positon);
int remove(SLList *list, size_t position);
int containsData(SLList *list, void *data, int compare(void *, void*));

void clearSLList(SLList *list);

// FREEING
void freeSLList(SLList *list);

// UTILS
// Again, no need to expose how exactly the list will be implemented.

void printSLList(SLList *list);

#endif

SLList.c

#include "SinglyLinkedList.h"

// by defining these in the implementation file
// the user has no idea how we implement our list
// meaning we're free to change our implementation
// and as long as the API remains the same, the code works just fine
// when built.
struct SLNode {
    void *data;
    SLNode *next;
};

struct SLList {
    size_t size;
    SLNode *head;
 };

// now we can define a node creation function here
// and mark it static so the user cannot call it from outside code.
static SLNode *createSLNode(void *data) {
    // ...
}

SLList *createSLList(void) {
    // ...
}

// now the list entirely manages its own resources (the nodes)
// and the user has no clue.
int insert(SLList *list, void *data, size_t index) {
    SLNode *node = createSLNode(data);
    // ...
}

int remove(SLList *list, size_t index) {
    // ...
}

// this is fine
int containsData(SLList *list, void *data, int compare(void *, void*)) {
    // ...
}


// now we implement this here and mark it static so users can't call it
// from outside code
static void freeSLNode(SLNode *node) {
    // ...
}

I would also remove the printArrow() function as it seems pretty pointless in this case.

\$\endgroup\$
  • \$\begingroup\$ This actually makes a lot of sense. Thank you for your review. I just implemented printArrow pretty much for myself and just kept in in here. I also just noticed that it is actually pointless that the user is able to create SLNodes and even knows about the implementation. \$\endgroup\$ – LastSecondsToLive Jan 21 '16 at 19:06
  • \$\begingroup\$ I just thought insert/remove are bad names, since they are to common and it's quite possibly that other libs are using these names. Is there any workaround? \$\endgroup\$ – LastSecondsToLive Jan 21 '16 at 19:20
  • 1
    \$\begingroup\$ No problem! The easiest way to resolve this issue would just be to add a prefix to all of your function names that identifies your library. For example, you can call your insertion function SLList_insert, removal SLList_removal etc. \$\endgroup\$ – Bizkit Jan 21 '16 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.