Linked Lists (C)

#include <stdlib.h>
#include <stdio.h>

struct llnode {            /* since the llnode is a self-referential structure */
   int val;                /* we can not compile the struct and typedef declaration into one */
   struct llnode *next;
};
typedef struct llnode llnode;

int ll_find_by_value(llnode *, int);
int ll_del_by_value(llnode **, int);
int ll_del_from_head( llnode **);
int ll_del_from_tail( llnode **);
int ll_add_to_head( llnode **head, int val);
int ll_add_to_tail( llnode **head, int val);
int ll_insert_in_order(llnode **, int);
int ll_concat(llnode **, llnode **);
int ll_sort(llnode **);
int ll_print( llnode *p);
int ll_free( llnode *p);

/* One of the lessons here is to see that if we want to use a function to malloc something that
 * is a POINTER in the CALLER of the function, then we must send in the ADDRESS of the POINTER
 * to that function.
 *
 * Recap: if we want to use a function to modify a VARIABLE in the caller
 *        then the CALLER needs to send in the ADDRESS of the VARIABLE
 *
 * Similarly: if we want to use a function to modify a POINTER in the caller
 *            then the CALLER needs to send in the ADDRESS of the POINTER
 *
 * In the code below, ll_add_to_head and ll_add_to_tail are dynamically creating new
 * nodes to be added to the linked list. Any dynamic creation of a node must be via
 * malloc.
 */

 int main(void) {
    llnode *root = NULL;
    llnode *root2 = NULL;
    int r=0;
    int i=0;

    printf("List A\n");
    r=ll_add_to_tail(&root,100);
    r=ll_add_to_tail(&root,200);
    r=ll_add_to_tail(&root,300);
    for(i=0;i<10;i=i+1){
       r=ll_add_to_tail(&root,i*100);
    }
    r=ll_print(root);
     /* r=ll_free(root); */

    printf("List B\n");
    // root=NULL;
    r=ll_add_to_tail(&root2,100);
    r=ll_add_to_tail(&root2,200);
    r=ll_add_to_tail(&root2,300);
    for(i=0;i<10;i=i+1){
       r=ll_add_to_head(&root2,i*100);
    }
    r=ll_print(root2);
    printf("Deleting Head\n");
    r=ll_sort(&root2);
    r=ll_insert_in_order(&root2, 350);
    r=ll_print(root2);
    r=ll_find_by_value(root2, 20);
    printf("Search Result: %d \n", r);
    r=ll_free(root2);
    return 0;
 }

int ll_del_from_head(llnode **ppList) {
  llnode *old_head;
  if (ppList == NULL || (*ppList)->next == NULL) {
    return -1;
  }
  old_head = (llnode *)malloc(sizeof(llnode));
  *old_head = **ppList;
  *ppList = ((*ppList)->next);
  free(old_head);
  return 0;
}

int ll_del_from_tail(llnode **ppList) {
   if (ppList == NULL) {
      return -1;
   }
   if ((*ppList)->next == NULL) {
     free((*ppList));
     return 0;
   } else if ((*ppList)->next->next == NULL) {
     free((*ppList)->next);
     (*ppList)->next = NULL;
     return 0;
   } else {
     return ll_del_from_tail(&((*ppList)->next));
   }
   return 0;
}

int ll_del_by_value(llnode **ppList, int val) {
  llnode *deleter;
  if (((*ppList)->next) == NULL) {
    return -1;
  }
  if ((*ppList)->next->val == val) {
     /* Do the delete */
     deleter = (llnode *)malloc(sizeof(llnode));
     deleter = (*ppList)->next;
     /* Change next link */
     if (deleter->next != NULL) {
       (*ppList)->next = deleter->next;
     } else {
       (*ppList)->next = NULL;
     }
     free(deleter);
     return 0;
  } else {
     if ((*ppList)->next == NULL) { return -1; }
     return ll_del_by_value(&((*ppList)->next), val);
  }
  return -1;
}

int ll_find_by_value(llnode *pList, int val) {
   if (pList->val == val) {
      return 0;
   } else {
      if (pList->next == NULL) { return -1; }
      return ll_find_by_value(pList->next, val);
   }
   return -1;
}

int ll_add_to_head( llnode **head, int val) {
    llnode *old_head;
   if (head == NULL) {
      return -1;
   }
        old_head = *head;

   *head = ( llnode *) malloc(sizeof( llnode));
   (*head) -> val = val;
        (*head) -> next = old_head;
        return 0;
}

int ll_add_to_tail( llnode **head, int val) {
   if (head == NULL) {
      return -1;
   }
   if (*head == NULL) {
      *head = ( llnode *) malloc(sizeof( llnode));
      (*head) -> val = val;
      (*head) -> next = NULL;
      return 0;
   } else { /* recursively call ll_add_to_tail until we get to the tail which is the point where the pointer is NULL */
      return ll_add_to_tail(&((*head)->next), val);
   }
}

int ll_insert_in_order(llnode **ppList, int val) {
   llnode **a = NULL;
   llnode *n = NULL;
   llnode *new_node = NULL;
   new_node = (llnode *)malloc(sizeof(llnode));
   if (ppList == NULL) {
      return -1;
   }
   /* Start by sorting the list */
   ll_sort(ppList);
   a = ppList;
   while ((*a)->next->val > val) {
      a = &((*a)->next);
      if ((*a)->next == NULL) {
         break;
      }
   }
   /* Apply the Insert */
   n = (*a)->next;
   new_node->next = n;
   new_node->val = val;
   (*a)->next = new_node;
   return 0;
}

int ll_concat(llnode **a, llnode **b) {
  if (a == NULL || b == NULL) {
    return -1;
  }
  if ((*a)->next == NULL) {
    (*a)->next = *b;
    return 0;
  } else {
    return ll_concat(&((*a)->next), b);
  }
  return 0;
}

int ll_sort(llnode **ppList) {
  llnode *items = NULL;
  int x,y,i = 0;
  int size = 0; /* For my purposes to iterate from one is more intuitive in the instance */
  int *vals = NULL;
  llnode *a = NULL;
  if (ppList == NULL) {
    return -1;
  }
  a = (llnode *)malloc(sizeof(llnode));
  /* Count List */
  a = *ppList;
  while (a != NULL) {
    a = a->next;
    size = size + 1;
  }
  vals = (int *)malloc(sizeof(int)*size);
  /* Add Values to a list */
  a = *ppList;
  i = 0;
  while (a != NULL) {
     vals[i] = a->val;
     i = i + 1;
     a = a->next;
  }
  /* Do the Sort */
  for (x=0; x<size; x++) {
     for (y=0; y<size; y++) {
        if (vals[x] > vals[y]) {
           i = vals[x];
           vals[x] = vals[y];
           vals[y] = i;
        }
     }
  }
  /* Make new llnode chain */
  for (i=0; i<size; i++) {
     ll_add_to_tail(&items, vals[i]);
  }
  *ppList = items;
  return 0;
}

int ll_print( llnode *p) {
   if (p==NULL) {
      return 0;
   } else {
      printf("val = %d\n",p->val);
      return ll_print(p->next);
   }
}

int ll_free( llnode *p) {
   if (p==NULL) {
      return -1;
   } else {
      llnode *f=p->next;
      free(p);
      return ll_free(f);
   }
}