Design of a linked list implementation in C

Question

At the moment I am working on creating a small library for common data structures in C. This is mainly for learning purposes, but I do plan to use this library in other projects to see how well it works and where the problems are. So far I'm content with my hash and binary tree implementation, but I cannot decide on the design of the linked list.

All the data structures implemented so far work with void pointers and take no responsibility for creating or destroying data, i.e. they only reference the data. One design goal is to keep them as generic as possible to increase the reuseability.

Regarding the linked list, I've found three approaches so far:

Dedicated list head: the list features a dedicated list head which is used as an abstract data type.
Nodes only: like the example above, except that all functions operate on a list_node. Used in GLib.
In payload: add a list_node structure to the payload data and calculate the offset to the payload with a macro. See lists in the linux kernel
EDIT Generate typed lists with macros: use macros to create type-specific versions of the list structures and functions.

Example for 1 and 2:


/* list.h */
typedef struct list_t list;

typedef int (*comparator)(const void* a, const void* b);

list* list_new          (comparator c);
void  list_delete       (list* l);
void  list_insert_after (list* l, uint32_t index, void* data);
void  list_remove       (list* l, void* data);
uint32_t list_size      (list* l);
/* other functions operating on lists */

/* list.c */
#include "list.h"

typedef struct list_node_t {
  struct list_node_t* next;
  struct list_node_t* prev;
  void* data;
} list_node;

struct list_t {
  list_node* begin;
  list_node* end;
  uint32_t   size;
  comparator cmp;
}

Now to the question: which of these approaches is the most versatile? Are there any other approaches?

It's probably better to use size_t for index, size, etc, rather than uint32_t. — Paul R
– Paul R, Commented Jun 22, 2011 at 8:32
you've got comparators in there, are you trying to implement a priority queue? A basic linked list doesn't need comparators and heaps are a better structure for handling pqueues — tobyodavies
– tobyodavies, Commented Jun 22, 2011 at 8:33
You might want to take a look at sys/queue.h for implementations too. — mripard
– mripard, Commented Jun 22, 2011 at 8:36
@tobyodavies the comparator is needed for list_remove and list_insert_after in the example above, because those two functions would find the element in question by comparing it to whatever is there where the data pointer points to. — Dario Hamidi
– Dario Hamidi, Commented Jun 22, 2011 at 8:50
@Dario - Perhaps those two functions should take a comparator argument, rather than making it an inherent part of the list. — Chris Lutz
– Chris Lutz, Commented Jun 22, 2011 at 9:13

Philip · Accepted Answer · 2011-06-22 08:53:18Z

1

I prefer the second approach, i.e. nodes only.

It has the advantage of being extremely simple, since the results of most list operations (split, push, pop, sublist, ...) are themselves lists.

Also note that you're lacking important list operations, mainly push() and pop(). You should make use of the fact that lists allow insertion in O(1).

answered Jun 22, 2011 at 8:53

Philip

5,9753 gold badges40 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dario Hamidi Over a year ago

Thanks for the advice! The interface given in the example is by no means complete, it is just supposed to illustrate the point.

Chris Lutz Over a year ago

I'd actually prefer a mix of 1 and 2 - 2 for when nodes are enough, but 1 for situations when the extra info that can be stored in a lis head (i.e. end, size, etc.) can cause significant speedups.

Roman A. Taycher · Accepted Answer · 2011-06-22 08:41:14Z

0

Note that you don't necessarily have to use void * pointers. You can use macro pasting tricks to generate types/function(by appending type name to types and functions) for generic type safe data structures.

ex.: http://sglib.sourceforge.net/

answered Jun 22, 2011 at 8:41

Roman A. Taycher

19.7k24 gold badges91 silver badges149 bronze badges

1 Comment

Dario Hamidi Over a year ago

Certainly an interesting approach, do you know of any projects that use sglib?

Collectives™ on Stack Overflow

Design of a linked list implementation in C

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related