Ham Radio

Sorted Linked List in C

From George Smart's Wiki

Jump to: navigation, search

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 <stdlib.h>
#include <stdio.h>

// 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;
}