How to make doubly linked list design more efficient?

I have played recently and implemented doubly linked list with merge sort algorithm. I was wondering if there is any way of improving the algorithm further to make it as fast as possible (I know about implementing list as array of void* pointers but I want to implement that as a separate structure).

I've gone from something like merge sort in learn C the hard way and added list_split function to split list in half and improved merging so it only links lists together without calling list_push/list_pop procedure which uselessly call calloc and free. That way I was able to get from ~3.3s to 0.9s needed for sorting 1,000,000 integers in list.

Also any comments about style and hints for possible bugs are welcome.

src/dllist.c:

```
#include
#include

#include "dllist.h"

struct node {
struct node *next;
struct node *prev;
void *data;
};

struct list {
unsigned int count;
struct node *first;
struct node *last;
};

List list_create()
{
List l;

l = calloc(1, sizeof(*l));
assert(l);
return l;
}

void list_destroy(List l)
{
free(l);
}

static inline void list_bond(struct node first, struct node second)
{
first->next = second;
second->prev = first;
}

void list_push_first(List l, void *data)
{
struct node *n;

n = calloc(1, sizeof(*n));
assert(n);
n->data = data;
if(l->count > 1) {
list_bond(n,l->first);
l->first = n;
} else {
l->first = n;
l->last = n;
}
l->count++;
}

void list_push_last(List l, void *data)
{
struct node *n;

n = calloc(1, sizeof(*n));
assert(n);
n->data = data;
if(l->count > 1) {
list_bond(l->last, n);
l->last = n;
} else {
l->first = n;
l->last = n;
}
l->count++;
}

/ if count == 0 return NULL! /
static struct node *list_find_nth(List l, unsigned int c)
{
struct node *tmp;
unsigned int i;

assert(c count+1);
if(l->count == 0)
return NULL;

Once you get under a second for whole process execution it's better to start timing inside the program using a accurate timestamp function. This avoids the C runtime initialization and printing from dominating the measurement.

One suggestion I had was keeping a struct node *freelist so you can easily grab a new node by doing

struct node *newNode = freelist;
freelist = freelist->next;

And when you free a node you can add it to the free list by doing:

oldNode->next = freelist;
freelist = oldNode;

This avoids having to call calloc and free over and over.

If you destroy a non empty list you leak all nodes still in the list. Similarly the rightlist in list_split just gets its values overwritten.

StackExchange Code Review Q#126431, answer score: 3