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

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.

Answer 2

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 3

If you are concerned with malloc fragmentation, you could request a large multiple number of size Node and keep incrementing a pointer by sizeof(Node) every time you copy Node values.

Answer 4

What operation shall be fast: insertion, retrieval, all ? There is always a trade-off. Does your solution need to be scalable ? Linked list are not.

Should you want/need to stick to a linked list, you could store it into an array of structs having a field indicating the index of the next entry in the linked list. Insertion will be very fast, without any allocation, the downside being you have to know the number of elements in advance - or to reallocate the table when it's getting full.

Refer to the "Linked lists using arrays of nodes" subsection of the Wikipedia page on linked list.

Answer 5

I would suggest you to use the linux kernel list implementation:

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=include/linux/list.h

(no additional memory allocation)

Answer 6

Memory concerns aside, some thoughts on making single link lists faster.

I think there is a bit of confusion in your code. At it's very core a linked list is:

typdef struct _node {
     ...
     struct _node *next;
} NODE;

Most implementations would have a void * in there to hang the payload on. That is not particularly important for now.

List inserts must connect the pointers. For simply adding the node (and ignoring the adding the payload) there 1 assignment if the node is going at the head or tail of a list, and 2 if it is going in the middle. There isn't much that can be done to get around that.

Occasionally simple lists only use node structures, so tail inserting requires traversal. This is costly. Having a special head structure with knowledge of the first and last node removes that cost.

Traversals can be made faster by implementing this as a skip-list (http://en.wikipedia.org/wiki/Skip_list). Though some care needs to be taken during node insertion to optimize (and you get more pointer assignments during insertion).

Answer 7

Check the speed of this singly linked list implementation as well:

http://web.archive.org/web/20071103112712/http://stsdas.stsci.edu/bps/linked_list.html

Answer 8

If the only operations you need is pushing, popping and iterating then instead of linked list you could put elements into an array. Pushing and popping element is just to modify one number (index of the first or the last element). Front and back of the array can be cyclically connected so elements can be freely pushed without a problem that the array ends.