Guest User

Linked List

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