Guest User

Untitled

a guest
Apr 5th, 2014
209
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "ll.h"
  2.  
  3.  
  4.  
  5. static void append(cons *c, int value) {
  6.   if (c->next) {
  7.     append(c->next, value);
  8.   } else {
  9.     /* allocated new memory for the next, because we're at the end */
  10.     cons *new = malloc(sizeof(cons));
  11.     new->value = value;
  12.     new->next = NULL;
  13.     /* make this new cons the new tail */
  14.     c->next = new;
  15.   }
  16. }
  17.  
  18. static int get(cons *c, int index, int current) {
  19.   if (index == current) {
  20.     return c->value;
  21.   } else {
  22.     return get(c->next, index, ++current);
  23.   }
  24. }
  25.  
  26. static void destroy(cons *c) {
  27.   if (c) {
  28.     destroy(c->next);
  29.     free(c);
  30.   }
  31. }
  32.  
  33. static void cons_print(cons *c) {
  34.   if (c) {
  35.     printf("%d ", c->value);
  36.     cons_print(c->next);
  37.   } else {
  38.     printf("\n");
  39.   }
  40. }
  41.  
  42. void insert_after(cons *c, int value, int index, int current) {
  43.   if (index == current) {
  44.     cons *new = malloc(sizeof(cons));
  45.     new->value = value;
  46.     new->next = c->next;
  47.     c->next = new;
  48.   } else {
  49.     insert_after(c->next, value, index, ++current);
  50.   }
  51. }
  52.  
  53. linked_list *new_linked_list(void) {
  54.   linked_list *ll = malloc(sizeof(linked_list));
  55.   assert(ll);
  56.   ll->size = 0;
  57.   ll->list = NULL;
  58.   return ll;
  59. }
  60.  
  61. int linked_list_get(linked_list *ll, int index) {
  62.   assert(ll);
  63.   assert(index >= 0);
  64.   assert(index <= (ll->size - 1));
  65.   return get(ll->list, index, 0);
  66. }
  67.  
  68. void linked_list_append(linked_list *ll, int value) {
  69.   assert(ll);
  70.   (ll->size)++;
  71.   if (ll->list) {
  72.     append(ll->list, value);
  73.   } else {
  74.     /* list is null, so we're at the end - allocate space for new tail */
  75.     cons *new = malloc(sizeof(cons));
  76.     new->value = value;
  77.     /* the next of the tail is NULL */
  78.     new->next = NULL;
  79.     /* assign it */
  80.     ll->list = new;
  81.   }
  82. }
  83.  
  84. void linked_list_insert_after(linked_list *ll, int value, int index) {
  85.   assert(ll);
  86.   assert(index >= 0);
  87.   assert(index <= (ll->size - 1));
  88.   ll->size++;
  89.   insert_after(ll->list, value, index, 0);
  90. }
  91.  
  92. int linked_list_size(linked_list *ll) {
  93.   if (ll) {
  94.     return ll->size;
  95.   } else {
  96.     return -1;
  97.   }
  98. }
  99.  
  100. void linked_list_delete_at(linked_list *ll, int index) {
  101.   assert(ll);
  102.   assert(index >= 0);
  103.   assert(index <= (ll->size - 1));
  104.   /* store the list */
  105.   cons *list = ll->list;
  106.   /* store the list again, will be the last node */
  107.   cons *last = list;
  108.   if (index == 0) {
  109.     ll->list = list->next;
  110.     ll->size--;
  111.     free(list);
  112.     return;
  113.   }
  114.  
  115.   int current = 0;
  116.   while (list) {
  117.     if (index == current) {
  118.       /* skip over pointer to list, then free it */
  119.       last->next = list->next;
  120.       free(list);
  121.       ll->size--;
  122.       break;
  123.     }
  124.     /* will always be one node behind (except at beginning) */
  125.     last = list;
  126.     /* go to next */
  127.     list = list->next;
  128.     current++;
  129.   }
  130. }
  131.  
  132. void linked_list_destroy(linked_list *ll) {
  133.   if (ll) {
  134.     destroy(ll->list);
  135.     free(ll);
  136.   }
  137. }
  138.  
  139. void linked_list_print(linked_list *ll) {
  140.   assert(ll);
  141.   cons_print(ll->list);
  142. }
  143.  
  144. //int main(void) {
  145.   //linked_list *list = new_linked_list();
  146.   //linked_list_print(list);
  147.   //linked_list_append(list, 2);
  148.   //linked_list_print(list); // 2
  149.   //linked_list_append(list, 3);
  150.   //linked_list_print(list); // 2 3
  151.   //linked_list_append(list, 4);
  152.   //linked_list_print(list); // 2 3 4
  153.   //linked_list_insert_after(list, 15, 1);
  154.   //linked_list_print(list); // 2 3 15 4
  155.   //linked_list_delete_at(list, 1);
  156.   //linked_list_print(list); // 2 15 4
  157.   //printf("get 0: %d\n", linked_list_get(list, 0));
  158.   //printf("get 2: %d\n", linked_list_get(list, 2));
  159.   //printf("get 1: %d\n", linked_list_get(list, 1));
  160.   //printf("size 3: %d\n", linked_list_size(list));
  161.   //linked_list_destroy(list);
  162.   //return 0;
  163. //}
RAW Paste Data