Simple linked list (C) for OSP lab
A simple linked list (FIFO-queue) for future generations ;) Get the source.
/* Description: Very simple single linked list. Intended for use in the OSP lab at Chalmers. In the OS course at Chalmers, you are allowed and even encouraged to use an existing linked list instead of implementing your own - just remember to add a reference (or else it's cheating!). Author: André Laszlo <andre@laszlo.nu> */ #include <stdlib.h> #include <stdio.h> typedef struct node_s { void *data; struct node_s *next; } NODE; typedef struct list_s { NODE *first; NODE *last; int length; } LIST; /* Create a new list */ LIST* new_list() { LIST *l; if (!(l=malloc(sizeof(LIST)))) return NULL; l->length = 0; l->first = NULL; l->last = NULL; return l; } /* Create a new node that can be inserted into the list */ NODE* new_node(void *data) { NODE *n; if (!(n=malloc(sizeof(NODE)))) return NULL; n->next = NULL; n->data = data; return n; } /* Insert element at the end of the list */ void append(LIST *l, void *data) { NODE *n = new_node(data); if (l->length == 0) { l->first = n; l->last = n; } else { l->last->next = n; l->last = n; } l->length++; } /* remove from head of list and return data */ void* pop(LIST *l) { if (l->length == 0) { return NULL; } else if (l->length == 1) { void *data = l->first->data; free(l->first); l->first = NULL; l->length = 0; return data; } else { void *data = l->first->data; NODE *tmp = l->first->next; free(l->first); l->first = tmp; l->length--; return data; } } /* Return the position of an element in the list, or -1 if it does not exist */ int find(LIST *l, void* data) { int i = 0; NODE *current = l->first; while (current != NULL) { if (current->data == data) return i; current = current->next; i++; } return -1; } /* Clean up list. TODO: Test this (since it's not used in lab) */ void destroy_list(LIST *l) { NODE *current = l->first; NODE *next; while (current != NULL) { next = current->next; free(current->data); free(current); current = next; } free(l); } /* Return pointer to an integer with value n */ int* intpointer(int n) { int* num = malloc(sizeof(int)); *num = n; return num; } /* Test and demo subroutine */ int main() { LIST *l = new_list(); /* Should be zero */ printf("Length: %d\n", l->length); /* Add some stuff to the list */ int i; int *n; int *thing; for (i = 0; i < 10; i++) { n = intpointer(i); if (i == 4) thing = n; /* Keep this for searching, later */ append(l, n); } /* Test find() */ printf("Pos %d: %d\n", *(int*)thing, find(l, thing)); int *other_thing = intpointer(12); printf("Pos %d: %d\n", *other_thing, find(l, other_thing)); /* Test iteration */ NODE* iter = l->first; printf("List: "); while(iter != NULL) { printf("%d ", *(int*)iter->data); /* Note: if reappending while iterating we might end up with an infinite loop. Try keeping a reference to the first reappended item if you want to break, or create a copy of the list */ iter = iter->next; } printf("\n"); printf("Length: %d\n", l->length); /* Test pop() */ int *popped = (int*)pop(l); while (popped != NULL) { printf("Pop result: %d\n", *popped); printf("Length: %d\n", l->length); popped = (int*)pop(l); } printf("Length: %d\n", l->length); /* Free up some memory */ destroy_list(l); return 0; }
