So I've done some reading through the source code of the linked list implementation, and I'm laying them out some of my thoughts here.
One does not simply index a linked list
It's important to notice, that the complexity of random access to a linked list is O(n)
, that means that 1 if you need to do a lot of random access you shouldn't be using a linked list and that you should always prefer iteration to indexing.
Using iterate_ll
to implement sort_ll
and search_ll
automatically results in very slow code.
search_ll
Ok, let's get this out of the way search_ll
should be called bsearch_ll
or binarysearch_ll
, the name search
doesn't tell the user that the linked list needs to be sorted to search for elements.
Note that using binary search on a linked isn't a good idea in the first place, as you need to traverse almost the entire list anyways (if iterate_ll
wasn't used, otherwise it does literally quadratic work). It's only useful if you need to reduce the calls to compare, which is something you might want to do, but this should definitely be done explicitly and not be the default search.
Also, why are you calling the compare function twice instead of storing the result? I'd also return int
instead of short
, but that's just nitpicking now.
sort_ll
sort_ll
also has the problem of using iterate_ll
, so I transformed the bubble sort algorithm to work without it:
void sort_ll(struct LinkedList *linked_list, int (*compare)(void *a, void *b))
{
for (struct Node *i = linked_list->head; i; i = i->next)
{
for (struct Node *j = i->next; j; j = j->next)
{
if (compare(i->data, j->data) > 0)
{
// Swap them.
void *temporary = j->data;
j->data = i->data;
i->data = temporary;
}
}
}
}
Note that I also changed the comparison from == 0
to > 0
, this allows you to e.g. implement the compare function for integers using a - b
, which is commonly done.
Now the complexity has been reduced from O(n^3)
to O(n^2)
.
Bubble sort itself isn't the best sorting algorithm, and I'd suggest actually using something like merge sort.
Getting rid of the indexes
Generally when working with linked lists you should pass around node pointers instead of indexes.
To illustrate that let's say you'd like to remove a node. To delete a node you firstly need to know where the node currently is.
The current implementation requires you to iterate over each element of the list with indexes, so you automatically have a complexity of O(n)
and then when you've found the correct element iterate over the entire list again (at least this time in O(n)
), to find the element at the index.
An alternative solution, which is preferable when working with liked lists, is to traverse the linked list using pointers for (Node *i = list; i; i = i->next)
and then pass the current node pointer to the delete function.
On ownership and pointers
Another thing I've noticed is that you're linked list owns pointers, as in allocates and frees them.
This isn't automatically wrong, but I'd say that it isn't a good design decision.
For one, how would you only use a shallow copy, so inserting e.g.
struct Str {
size_t len;
char *str;
};
wouldn't copy str
and now you've got two references to str
and you'd somehow need to decide who frees str
(I'm assuming that str is heap allocated).
I suggest that instead of doing the allocation inside insert_ll
the user would call it with a pointer allocated from the user, this would also get rid of the problem of constructing a node with data of size zero. Having a node with a null pointer should be totally allowed.
How I would do it
This isn't for everyone's taste, but I like to use a Node as a base class for the elements of the list.
This allows you to basically do whatever you want to, and you don't have an extra indirection between the node and the data, which is more cache friendly.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
struct Node {
struct Node *next;
struct Node *previous;
};
struct IntNode {
struct Node node;
int i;
};
static struct Node *
sort_ll_merge(struct Node *a, struct Node *b, int (*cmp)(void *a, void *b));
/* mergesort */
struct Node *
sort_ll(struct Node *head, int (*cmp)(void *a, void *b))
{
struct Node *a, *b;
if (!head || !head->next)
return head;
{
struct Node *fast, *slow;
slow = head;
fast = head->next;
/* Advance 'fast' two nodes, and advance 'slow' one node */
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
/* 'slow' is before the midpoint in the list, so split it in
* two at that point. */
a = head;
b = slow->next;
slow->next = NULL;
}
a = sort_ll(a, cmp);
b = sort_ll(b, cmp);
return sort_ll_merge(a, b, cmp);
}
struct Node *
sort_ll_merge(struct Node *a, struct Node *b, int (*cmp)(void *a, void *b))
{
struct Node* res = NULL;
/* Base cases */
if (a == NULL)
return (b);
else if (b == NULL)
return (a);
/* Pick either a or b, and recur */
if (cmp(a, b) > 0) {
res = a;
res->next = sort_ll_merge(a->next, b, cmp);
} else {
res = b;
res->next = sort_ll_merge(a, b->next, cmp);
}
return res;
}
int
cmp_intnode(void* a, void* b)
{
struct IntNode *ia = a, *ib = b;
return ia->i - ib->i;
}
int
main(void)
{
/* just on way to construct an linked list,
* you could use malloc instead. */
struct IntNode nodes[30] = {0};
for (int i = 0; i < 29; ++i) {
nodes[i].node.next = &nodes[i+1];
nodes[i+1].node.previous = &nodes[i];
nodes[i].i = rand();
}
struct IntNode *newhead = sort_ll(nodes, cmp_intnode);
for (struct IntNode *i = newhead; i; i = i->node.next) {
printf("%d\n", i->i);
}
}
enhancement help wanted good first issue