This code is a sorted linked list in C. I was written for part of my PhD for keeping track of nodes in a Contiki OS. The code here is in it’s general form. I am no expert programmer, as the code will show, but it works, which is more than many others I could find.

Source Code for Sorted Linked List in C

// George Smart
// http://www.george-smart.co.uk/
//
// Linked List example

#include
#include

// the list element node structure. Add more stuff if you want to.
struct list_el {
unsigned int id; // ID number
struct list_el * next; // link pointer (where the next element is)
};

// this allows us to refer to the above structure as a node.
typedef struct list_el node;

// This defines *head as our top element. This allows us to find our
// begining element in the linked list.
node *head;

// This function takes an ID and adds it to a linked list, creating a new
// list or updating an existing ID if it exists.
void addNode(unsigned int id) {
node *curr, *new;

// Create and setup our new link
new = (node *)malloc(sizeof(node));
if (new == NULL) {
printf(“Memory not available to create link. Exiting.\n”);
exit (EXIT_FAILURE);
}
new->id = id;

// If Head is NULL, the list doesn’t yet exist, so we create one.
if (head == NULL) {
head = new;
new->next = NULL;
return;
}

// does our new element go before the first one?
if (new->id < head->id) {
new->next = head;
head = new;
return;
}

// if our element goes in the middle, this code will scan through
// to find out exactly where it belongs.
curr = head; // start at the begining node.
while ( (curr->next != NULL) ) {
if ((new->id < curr->next->id)) {
if((new->id > curr->id)) {
// this inserts the new node into the middle if
// it ID doesn’t already exist in the list
new->next = curr->next;
curr->next = new;
return;
} else {
// This section happens if the node DOES already exist
// In a real program you would update the nodes other
// data in this section.
free(new); // get rid of ‘new’, we don’t need it.
return;
}
}
curr = curr->next; // move to the next node.
}

// if we still haven’t found the place, add at the end.
//check if it’s a dupe of the last element or not
if (curr->id == new->id) {
// if it’s the same don’t do anything, because the node already
// exists. In a real program you would update the nodes other
// data in this section.
return;
} else {
// else add the new element on the end.
curr->next = new;
new->next = NULL;
return;
}
}

void delNode(int a) {
int done = 0;
node *curr, *prev;
curr = head;

// If we try and delete a node before the list exists, we’d get SIGSEGV
if (head == NULL) {
//printf(“Couldn’t remove node ID %d. List doesn’t exist!\n”, a);
return;
}

// does our first element need to be removed? If yes, do it.
if (head->id == a) {
free(head);
head = head->next;
done = 1;
return;
}

// find where the node to be deleted exists. Notice we run ahead one
// node, so we don’t loose the pointer to the one before the deletee
while ( (curr->next != NULL) ) {
if (curr->next->id == a) {
prev = curr->next;
free(prev); // get the memory back
curr->next = prev->next; // short reference to prev
done = 1;
}
if (curr->next != NULL) {
curr = curr->next; //only move on if it is safe.
}
}
// if you’re interested in verbose, this well tell you if it couldn’t
// find what you wanted to delete. Useful for testing.
if (done == 0) {
//printf(“Nothing done. Couldn’t find node ID %d\n”, a);
}
}

// This code just loops through the entire list printing out the data.
void showNodes() {
node * temp;
printf(“Printing List:\n”);
temp = head;
while(temp) {
printf(“%d\n”, temp->id);
temp = temp->next ;
}
}

// The main program loop
int main() {
head = NULL; // set head to NULL, symboling no list existing yet.
int i = 0;

// add nodes 5-10.
for (i=10;i<=20;i++) {
addNode(i);
}

addNode(5); // add an element out of order at begining
addNode(25); // add an element out of order at end
addNode(17); // add an element out of order, creating duplicate
// node this program updates same number.

showNodes();

delNode(5); // remove the first element
delNode(15); // remove the a middle element
delNode(25); // remove the last elelemt

delNode(30); // remove a number that isn’t present.

showNodes();

return 0;
}