Wanted: Very Fast Linked Lists in C

Question

I am trying to implement a singly linked list in C. A common implementation that you see floating around the internet is something like

typedef struct {
  int head;
  Node *tail;
} Node;

with methods like

Node cons(int head, Node tail) {
  Node y;
  y.head = head;
  y.tail = malloc(sizeof(Node));
  *y.tail = tail;
}

Performance is very important. Is there any way to implement a linked list in C that will be faster than this? For example, getting rid of the memory allocation (y.tail = malloc(sizeof(Node))) should provide a significant speed increase.

Answer 1

Yes there is... This is called as a memory pool. Similar to a thread pool. Basically you allocate an area of memory at the beginning of the program of type Node. Pointers to this area are stored in an array. In your cons function all you do is get the pointers from the array. This does not improve the overall speed, but if you have frequent memory allocations this will increase the responsiveness of the program at the cost of some space for the array

Answer 2

Very fast appending to a linked list? A rope (not limited to strings with small modifications) would allow you to batch allocate memory (improving perfomance) while not penalizing appending to the end of the list.