Sorted linked-list in C (self-compiling)

Question

I needed a sorted-list that I can iterate over to render elements in layers. Right now, delete_item deletes the first node with a matching priority it finds but I intend to delete specific list items in my implementation.

I didn't know if I needed the list to be doubly linked, but it turns out it makes deleting an item from the list easier. I've also seen people initializing the memory with calloc, is it important in this case?

There's also probably a way to give each list item a unique identifier (apart from its pointer) so that I can delete a specific item instead of deleting the first occurrence. For now, I'll just use the pointer...

Also, what do you think of my self-compiling trick?

//usr/bin/gcc ${0##*/} -o temp && ./temp ; rm temp 2>/dev/null ; exit
#include <stdio.h>
#include <stdlib.h>
struct node {
 struct node *next;
 struct node *prev;
 int priority;
};
struct node *head;
void add_item(int priority)
{
 struct node *curr = head;
 struct node *prev = NULL;
 while((curr != NULL) && (curr->priority < priority)) {
 prev = curr;
 curr = curr->next;
 }
 struct node *new = malloc(sizeof(struct node));
 new->priority = priority;
 new->next = curr;
 new->prev = prev;
 if(prev != NULL) {
 prev->next = new;
 } else {
 head = new;
 }
}
void remove_item(int priority)
{
 struct node *curr = head;
 while((curr != NULL) && (curr->priority != priority)) {
 curr = curr->next;
 }
 if(!curr)
 return;
 if(curr == head) {
 head = curr->next;
 } else {
 curr->prev->next = curr->next;
 if(curr->next)
 curr->next->prev = curr->prev;
 }
 free(curr);
}
void delete_list()
{
 struct node *curr;
 while(head != NULL) {
 curr = head;
 head = head->next;
 free(curr);
 }
}
void print_items()
{
 int member = 0;
 for(struct node *iter = head; iter != NULL; iter = iter->next)
 {
 printf("Member: %d -> priority: %d\n", member, iter->priority);
 member++;
 }
}
int main(int argc, char** argv)
{
 printf("This file is self-compiling\n");
 add_item(1);
 add_item(1);
 add_item(2);
 add_item(3);
 add_item(1);
 add_item(5);
 add_item(4);
 add_item(3);
 remove_item(1);
 remove_item(4);
 remove_item(5);
 add_item(5);
 print_items();
 delete_list();
}

Answer 1

Bug when inserting item

In add_item(), you are missing this code which fixes the prev pointer of the node after the one you just inseretd:

if (curr != NULL)
 curr->prev = new;

Bug when removing item

In remove_item(), if the node to be removed is the head node, you fail to fix up the prev pointer of the second node. In other words, you need to do the following code in both the head and non-head cases:

 if (curr->next)
 curr->next->prev = curr->prev;

• divx: Nicely spotted! Can't believe I missed that... Thanks. I have to be careful with doubly linked lists.
• divx: I accepted this answer in case someone wants to use the code, but both answers were acceptance worthy.

Answer 2

All in all there's not much to criticize. Be sure to fix the bugs mentioned in the other answer, though!

---

Fail fast

struct node *new = malloc(sizeof(struct node));
new->priority = priority;

You do not check whether allocation succeeded. Thus the next line will probably result in a crash in case malloc returned NULL. But it could also continue to seem to be working, failing at a potentially completely unrelated point in your program. That's the problem with undefined behavior. Thus, if you want an allocation failure to be a fatal failure, then you have to actually code such a failure mode:

void * malloc_or_die(size_t size) {
 void * pointer = malloc(size);
 if (pointer) {
 return pointer;
 }
 fprintf(stderr, "Fatal: failed to allocate memory of size %zu.\n", size);
 exit(EXIT_FAILURE);
}

The trick

Also, what do you think of my self-compiling trick?

//usr/bin/gcc ${0##*/} -o temp && ./temp ; rm temp 2>/dev/null ; exit

• Path to compiler hard coded
• Compiler hard coded
• Deletes a possibly existing file temp without asking

It's a "trick" that's fun to show once, but really don't use it. If you want to avoid the sequence of commands to compile, run and possibly delete, then write a shell function to do that for you.

Global variable

struct node *head;

You could make your code more general (as in usable for more than one single list instance) if you pass (a pointer to) such a head pointer in to your functions.

Use blocks

 if(curr->next)
 curr->next->prev = curr->prev;

Just always use { /* ... */ }. Saves you from potential headaches when you later add a line of code without looking too closely.

Consistency

Just some small oddities, nothing of real importance:

• You have struct node *next; but also char** argv. Decide whether you want to keep the * next to the type or the declared name.
• You test for (curr != NULL) but also use !curr in a condition later one. Use either curr != NULL and curr == NULL or curr and !curr.

• Toby Speight: Another issue with the "trick" - it only works if it's in the current working directory, due to the path removal.
• divx: Thanks a lot! I agree with everything you said. I actually wasn't aware that malloc could have undefined behavior. I thought failure to allocate always ended in segfault.