Linked list implementation in C

Question

I'm learning C for mainly for fun and to get a better understanding of how things work under the hood (most of my experience lies with high-level languages). I've been following quite a few books and working through the exercises. For extra practice, I've implemented a linked list using the knowledge I've learned - I thought it might be useful to get some feedback on it!

I plan to make this generic and work with any type once I learn how to do this :)

I desire any and all feedback. Especially feedback that pushes me in the right direction (except for 'give up'!)

llist.h:

#ifndef __llist_
#define __llist_

#include <stdlib.h>
#include <errno.h>
#include <assert.h>

#define LLMSG_ELISTNULL "List cannot be NULL"
#define LLMSG_EHEADNULL "Head cannot be NULL - list corrupted"
#define LLMSG_ENODENULL "Node cannot be NULL"
#define LLMSG_ENEWNULL  "New node cannot be NULL"

typedef struct _llist_node {
  struct _llist_node *next;
  int value;
} llist_node;

typedef struct _llist {
  struct _llist_node *head;
} llist;

/* 
   constructors & destructor
*/
llist_node *llist_node_create(int value);
llist *llist_create(llist_node *head);
void llist_destroy(llist *list);

/*
  insertion
*/

llist *llist_append(llist *list, llist_node *node);
llist *llist_prepend(llist *list, llist_node *node);

llist_node *llist_insert_after(llist_node *node, llist_node *new);
llist_node *llist_insert_before(llist *list, llist_node *node, llist_node *new);

/*
  removal
*/

llist *llist_remove_head(llist *list);
llist_node *llist_remove_after(llist_node *node);
llist *llist_remove(llist *list, llist_node *node);

#endif

llist.c:

#include "llist.h"

#include <stdlib.h>
#include <errno.h>
#include <assert.h>

llist_node *llist_node_create(int value) {
  llist_node *node = malloc(sizeof(llist_node));
  if (! node) {
    errno = ENOMEM;
    return NULL;
  }

  node->value = value;
  node->next = NULL;

  return node;
}

llist *llist_create(llist_node *head) {
  assert(head != NULL && LLMSG_ENODENULL);

  llist *list = malloc(sizeof(llist));
  if (list == NULL) {
    errno = ENOMEM;
    return NULL;
  }

  list->head = head;
  return list;
}

void llist_destroy(llist *list) {
  assert(list != NULL && LLMSG_ELISTNULL);

  // do not proceed if list container corrupt
  if (list->head != NULL) {
    llist_node *head = list->head;
    llist_node *next;
    llist_node *next_next;

    // free rest of list first
    if (head->next != NULL) {
      next = head->next;
      while (next != NULL) {
        next_next = next->next;
        free(next);
        next = next_next;
      }
    }

    if (head != NULL) {
      free(head);
    }
  }

  free(list);
}

llist *llist_append(llist *list, llist_node *node) {
  assert(list != NULL && LLMSG_ELISTNULL);
  assert(node != NULL && LLMSG_EHEADNULL);
  assert(list->head != NULL && LLMSG_EHEADNULL);

  llist_node *next;

  if (list->head->next == NULL) {
    list->head->next = node;
  }
  else {
    for (next = list->head->next; next != NULL; next = next->next) {
      if (next->next == NULL) {
        next->next = node;
        break;
      }
    }
    assert(next->next == node && "Failed to insert node to end of list");
  }

  return list;
}

llist *llist_prepend(llist *list, llist_node *node) {
  assert(list != NULL && LLMSG_ELISTNULL);
  assert(node != NULL && LLMSG_ENODENULL);
  assert(list->head != NULL && LLMSG_EHEADNULL);

  llist_node *head = list->head;
  list->head = node;
  node->next = head;

  return list;
}

llist_node *llist_insert_after(llist_node *node, llist_node *new) {
  assert(node != NULL && LLMSG_ENODENULL);
  assert(new != NULL && LLMSG_ENEWNULL);

  llist_node *next = node->next;
  node->next = new;
  new->next = next;

  return new;
}

llist_node *llist_insert_before(llist *list, llist_node *node, llist_node *new) {
  assert(list != NULL && LLMSG_ELISTNULL);
  assert(node != NULL && LLMSG_ENODENULL);
  assert(new != NULL && LLMSG_ENEWNULL);

  llist_node *curr = list->head;
  while (curr->next != NULL) {
    if (node == curr->next) {
      curr->next = new;
      new->next = node;
      break;
    }
    curr = curr->next;
  }

  return new;
}

llist *llist_remove_head(llist *list) {
  assert(list != NULL && LLMSG_ELISTNULL);

  llist_node *head = list->head;
  if (list->head->next) {
    list->head = list->head->next;
  }
  free(head);

  return list;
}

llist_node *llist_remove_after(llist_node *node) {  
  assert(node != NULL && LLMSG_ENODENULL);

  if (node->next != NULL) {
    llist_node *delete = node->next;
    node->next = node->next->next;
    free(delete);
  }

  return node;
}

llist *llist_remove(llist *list, llist_node *node) {
  assert(list != NULL && LLMSG_ELISTNULL);
  assert(node != NULL && LLMSG_ENODENULL);

  llist_node *curr = list->head;
  while (curr->next != NULL) {
    if (node == curr->next) {
      curr = llist_remove_after(curr);
      break;
    }
    curr = curr->next;
  }

  return list;
}

linked-list.c (test output for each operation):

#include <stdio.h>
#include "llist.h"

int main() {
  llist *list = llist_create(llist_node_create(1));
  list = llist_append(list, llist_node_create(2));
  list = llist_append(list, llist_node_create(3));

  printf("1: %d\n", list->head->value);
  printf("2: %d\n", list->head->next->value);
  printf("3: %d\n", list->head->next->next->value);

  list = llist_prepend(list, llist_node_create(-1));

  printf("1: %d\n", list->head->value);
  printf("2: %d\n", list->head->next->value);
  printf("3: %d\n", list->head->next->next->value);
  printf("4: %d\n", list->head->next->next->next->value);

  llist_insert_after(list->head->next, llist_node_create(400));

  printf("1: %d\n", list->head->value);
  printf("2: %d\n", list->head->next->value);
  printf("3: %d\n", list->head->next->next->value);
  printf("4: %d\n", list->head->next->next->next->value);
  printf("5: %d\n", list->head->next->next->next->next->value);

  llist_insert_before(list, list->head->next->next, llist_node_create(500));

  printf("1: %d\n", list->head->value);
  printf("2: %d\n", list->head->next->value);
  printf("3: %d\n", list->head->next->next->value);
  printf("4: %d\n", list->head->next->next->next->value);
  printf("5: %d\n", list->head->next->next->next->next->value);
  printf("6: %d\n", list->head->next->next->next->next->next->value);

  list = llist_remove_head(list);

  printf("1: %d\n", list->head->value);
  printf("2: %d\n", list->head->next->value);
  printf("3: %d\n", list->head->next->next->value);
  printf("4: %d\n", list->head->next->next->next->value);
  printf("5: %d\n", list->head->next->next->next->next->value);

  list = llist_remove(list, list->head->next->next);

  printf("1: %d\n", list->head->value);
  printf("2: %d\n", list->head->next->value);
  printf("3: %d\n", list->head->next->next->value);
  printf("4: %d\n", list->head->next->next->next->value);

  list->head = llist_remove_after(list->head);

  printf("1: %d\n", list->head->value);
  printf("2: %d\n", list->head->next->value);
  printf("3: %d\n", list->head->next->next->value);  

  llist_destroy(list);

  return 0;
}

ChrisW · Accepted Answer · 2014-02-23 22:30:32Z

It looks good.

#ifndef __llist_

Avoid using leading underscores: they are reserved.

#include <stdlib.h>
#include <errno.h>
#include <assert.h>

Code which includes your llist.h therefore includes <stdlib.h> etc., which makes compilation slower. Put as little as you can in your public header file; you could include those in your llist.c instead.

typedef struct _llist_node {
  struct _llist_node *next;
  int value;
} llist_node;

typedef struct _llist {
  struct _llist_node *head;
} llist;

/* 
   constructors & destructor
*/
llist_node *llist_node_create(int value);
llist *llist_create(llist_node *head);

Continuing to minimize the contents of the header file, you can use an "opaque pointer" (a.k.a. "handle" a.k.a. "cheshire cat") by declaring the following instead ...

struct llist_node;

struct llist;

/* 
   constructors & destructor
*/
struct llist_node *llist_node_create(int value);
struct llist *llist_create(struct llist_node *head);

... and define the structs in your C file. After all, client code doesn't/shouldn't need to know what's inside your structs.

To do that you would also need another function to get the value out of a node:

int llist_node_read_value(struct llist_node *node); // implemented as return node->value

Maybe an opaque pointer is 'overkill' in this simple example but it's a useful technique:

Less in the header file makes it easier for clients to understand the public API
Less in the header file makes it harder for clients to poke into private details (e.g. writing into your data structures
May avoid recompiling client code when/if the layout/content of your struct changes (e.g. if your module is shipped as a static- or dynamic-linked library)

llist_node *llist_insert_after(llist_node *node, llist_node *new);
llist_node *llist_insert_before(llist *list, llist_node *node, llist_node *new);

I understand why one needs a llist *list parameter and the other doesn't, but it looks odd.

In llist_insert_after you don't check that node is on a list. When you add a created node to the list you assume that its next pointer is null.

However your API allows user code to do:

llist_node *first = llist_node_create(1);
llist *list = llist_create(first);
llist_node *second = llist_node_create(2);
llist_node *third = llist_node_create(3);
// this works even though second isn't a member of a list
llist_insert_after(second, third);
// this works badly because second->next is not null
llist_insert_before(list, first, second);

I don't understand why llist_append and llist_prepend return a pointer to llist instead of a pointer to llist_node.

void llist_destroy(llist *list) {
  assert(list != NULL && LLMSG_ELISTNULL);

  // do not proceed if list container corrupt
  if (list->head != NULL) {
    llist_node *head = list->head;
    llist_node *next;
    llist_node *next_next;

    // free rest of list first
    if (head->next != NULL) {
      next = head->next;
      while (next != NULL) {
        next_next = next->next;
        free(next);
        next = next_next;
      }
    }

    if (head != NULL) {
      free(head);
    }
  }

  free(list);
}

It's better to avoid/delay declaring a local variable until (later) the moment when you can first assign a value to it; so, the following would be clearer:

void llist_destroy(llist *list) {
  assert(list != NULL && LLMSG_ELISTNULL);

  // do not proceed if list container corrupt
  if (list->head != NULL) {
    llist_node *head = list->head;

    // free rest of list first
    if (head->next != NULL) {
      llist_node *next = head->next;
      while (next != NULL) {
        llist_node *next_next = next->next;
        free(next);
        next = next_next;
      }
    }

    if (head != NULL) {
      free(head);
    }
  }

  free(list);
}

Your list_remove methods silently do nothing (instead of loudly failing) if they fail to remove the requested node.

Consider coding your void llist_destroy(llist *list); function as void llist_destroy(llist **list_ptr); instead, so that its last statement can be *list_ptr = 0 to try to ensure that the user/caller can't try to use (dereference) the list memory after it has been freed.

linked-list.c (test output for each operation):

Your testing could be a bit more thorough, for example:

Remove enough elements to completely empty the list and then verify that you can add more
Destroy an empty list and destroy a non-empty list
Append after one element in the list and prepend before one element in the list
Decide whether you want to detect user errors (e.g. inserting a null pointer) and if so test that

Your use of messages like LLMSG_ELISTNULL in assert functions was new to me (I hadn't seen that before).

You don't have any methods to do anything useful with the list: for example, to search the list to see whether it contains a specific value.

I'm not sure that llist_prepend() and llist_append() require a return value at all. If the "instance" of llist being modified is provided, doesn't it not matter if a return to the list's node or the list itself is returned at all? — user61611, Jan 2 at 22:59
Returning a pointer to the newly-created node lets the caller do things to that node (e.g. subsequently delete the node from the list). — ChrisW, Jan 2 at 23:07
One more question. Where the program is checking for memory errors does it make sense to return NULL? Doesn't that put the impetus on the programmer to then deal with that error? Instead, shouldn't the program exist because none of the functions that follow adequately handle a Node or List with a NULL entry? — user61611, Jan 2 at 23:29
It makes sense to check for errors, because when errors are detected 'as soon as possible' that's makes them easier to debug. When a library finds an error, returning an error value (e.g. NULL) is problematic if (and only if) the calling program doesn't test for that error value: and that's a reason why C++ supports throwing exceptions instead. I don't have time for a good, long answer. I suggest you post a question on Programmers.SE and/or ask about this in the Chat room. — ChrisW, Jan 3 at 0:23

chrisb · Answer 2 · 2014-02-23 21:13:50Z

Making it type-generic

The key to making it generic is in the ll add function. This should take the size of the object you want to add, and a pointer to the data member:

llist_node *llist_node_create(void * pData, uint size);

And then the implementation becomes:

typedef struct llist_node { pNext, char data[1] };
llist_node *llist_node_create(void * pData, uint dataSize)
{
    // -1 so you don't waste a byte of memory when copying over
    llist_node * pNewNode = malloc(sizeof(llist_node -1) + dataSize);
    memcpy(&pNewNode->data, pData, dataSize);
    return pNewNode;
}

This relies on whatever is calling the library knowing about the type/size of data object.

Encapsulation

Also, if you want to increase encapsulation, implement a void * llist_GetDataElement(llist_node * llistEle); function. This means you can hide the implementation details (i.e. the internal structure of your llist_node), and hence you could easily change it over to say, a fixed array, as opposed to malloc, based implementation etc.

asked	1 year ago
viewed	653 times
active	1 year ago

current community

your communities

more stack exchange communities

Linked list implementation in C

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged c data-structures linked-list memory-management pointers or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Linked list implementation in C

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c data-structures linked-list memory-management pointers or ask your own question.

Related

Hot Network Questions