Geek Answers Handbook

Requires: very fast linked lists in C

I am trying to implement a singly linked list in C. The usual implementation that you see on the Internet is something like

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

using 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 a way to implement a linked list in C that will be faster than this? For example, getting rid of memory allocation ( y.tail = malloc(sizeof(Node)) ) should provide a significant increase in speed.

+6
performance c linked-list
source share
8 answers

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

+16
source share

Very fast adding a linked list? A rope (not limited to lines with small changes) will allow you to allocate memory (improving performance) without punishing adding to the end of the list.

+8
source share

What operation should be quick: insert, extract, all? There is always a compromise. Is a scalable solution required? There is no linked list.

If you need / need to stick to a linked list, you can save it to an array of structures that have a field indicating the index of the next record in the linked list. The insert will be very fast, without any selection, the disadvantage is that you need to know the number of elements in advance - or redistribute the table when it is filled.

Refer to the “Linked Lists Using Node Arrays” section of the Wikipedia page in the linked list .

+5
source share

Memory aside, some thoughts on making link lists faster.

I think there is a bit of confusion in your code. It has a very basic linked list:

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

Most implementations have void * to hang the payload. This is not particularly important now.

List insertions should include pointers. To simply add a node (and ignore the addition of a payload), there is 1 purpose if node goes at the beginning or end of the list, and 2 in the middle. This is not enough that can be done to get around this.

Sometimes simple lists use only node structures, so traversal is required to insert a tail. It is expensive. Having a special header structure with knowledge of the first and last node removes this cost.

Traverses can be done faster by implementing this as a skip list ( http://en.wikipedia.org/wiki/Skip_list ). Although the optimization process is necessary in the node process (although you get more pointers during insertion).

+3
source share

If you are interested in malloc fragmentation, you can request a large number of Node numbers and continue to increment the sizeof (Node) pointer each time you copy Node values.

+2
source share

I would suggest you 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 extra memory allocation)

+2
source share

Check the speed of this implementation with the same list:

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

0
source share

If you only need what you need, it is click, pop up and repeat, and instead of a linked list you can put elements into an array. Pushing and popping element is just changing one number (index of the first or last element). The front and back of the array can be connected cyclically, so the elements can move freely without problems that end with the array.

0
source share

More articles:


All Articles