cycleDetection

Detect cycles in graphs
Log | Files | Refs | README

LinkedList.c (2177B)

      1 #include "LinkedList.h"
      2 #include "Graph.h"
      3 #include <stdio.h>
      4 #include <stdlib.h>
      5 #include <assert.h>
      6 
      7 LinkedList *LinkedList_new() {
      8         LinkedList *ll = malloc( sizeof( LinkedList ) );
      9         if ( !ll )
     10                 return NULL;
     11         ll->head = NULL;
     12         ll->tail = NULL;
     13         ll->size = 0;
     14         return ll;
     15 }
     16 
     17 LinkedListNode *LinkedList_append( LinkedList *ll, void *elem ) {
     18         LinkedListNode *node = malloc( sizeof( LinkedListNode ) );
     19         if ( !node )
     20                 return NULL;
     21         node->data = elem;
     22         if ( ll->size == 0 ) 
     23                 ll->head = node;
     24         node->next = ll->tail;
     25         if( node->next ) 
     26                 node->next->prev = node;
     27         node->prev = NULL;
     28         ll->tail = node;
     29         ll->size += 1;
     30         return node;
     31 }
     32 
     33 /*
     34  * Den her funktion er muligvis lidt buggy
     35  */
     36 void *LinkedList_popFront( LinkedList *ll ) {
     37         assert( ll->size > 0 );
     38         LinkedListNode *front = ll->head;
     39         if ( ll->size == 1 )
     40                 ll->head = ll->tail = NULL;
     41         else { // ll->size > 1
     42                 ll->head = front->prev;
     43                 ll->head->next = NULL;
     44         }
     45         ll->size -= 1;
     46         void *elem = front->data;
     47         free( front );
     48         return elem;
     49 }
     50 
     51 void LinkedList_delete( LinkedList *ll ) {
     52         LinkedListNode *p = ll->tail;
     53         LinkedListNode *pt;
     54         while ( p ) {
     55                 pt = p->next;
     56                 free( p );
     57                 p = pt;
     58         }
     59         free( ll );
     60 }
     61 
     62 void *LinkedList_remove( LinkedList *ll, LinkedListNode *node ) {
     63         if ( node->next )
     64                 node->next->prev = node->prev;
     65         else // first element
     66                 ll->head = node->prev;
     67         if ( node->prev ) 
     68                 node->prev->next = node->next;
     69         else // last element
     70                 ll->tail = node->next;
     71         void *elem = node->data;
     72         free( node );
     73         ll->size -= 1;
     74         return elem;        
     75 }
     76 
     77 LinkedListNode *LinkedList_find( LinkedList *ll, void *elem ) {
     78         LinkedListNode *p = ll->tail;
     79         while ( p && p->data != elem ) {
     80                 p = p->next;
     81         }
     82         return p;
     83 }