exercism-c/linked-list/linked_list.c

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

struct list_node {
   struct list_node *prev, *next;
   ll_data_t data;
};

struct list {
   struct list_node *first, *last;
};

struct list * list_create(void){
   struct list * return_val = calloc(1,sizeof(struct list));
   return_val->first = NULL;
   return_val->last = NULL;
   return return_val;
}

// counts the items on a list
size_t list_count(const struct list *list){
   size_t counter = 0;
   struct list_node *object = list->first;
   if(object == NULL){
      /* Return 0 if nothing exists in the list */
      return counter;
   } else {
      /* Count up by one */
      counter++;
   }
   while(object != list->last){
      /* Increment counter, then get the next object */
      counter++;
      object = object->next;
   }
   return counter;
}

// inserts item at back of a list
void list_push(struct list *list, ll_data_t item_data){
   /* Create new object, allocate memory */
   struct list_node *new_object = calloc(1,sizeof(struct list_node));
   /* Pointer to previous back object */
   struct list_node *last_object = list->last;

   /* If the list is empty, last object will be null */
   if(last_object == NULL){
      /* If the list is empty, this newly added object is both first and last */
      list->last = new_object;
      list->first = new_object;
      /* If the list is empty, previous needs to be null, since there
      *  isn't anything else in the list */
      new_object->prev = NULL;
   } else {
      /* If the list ISN'T empty, be sure to tie the last object and the new object together */
      new_object->prev = last_object;
      last_object->next = new_object;
      /* Append last object to list */
      list->last = new_object;
   }

   /* Since we are appending to the back of the list, there is no next object */
   new_object->next = NULL;
   /* Assign value */
   new_object->data = item_data;
}

// removes item from back of a list
ll_data_t list_pop(struct list *list){
   /* the last object in the list */
   struct list_node *last_object;
   /* the second to last object in the list */
   struct list_node *second_last_object;
   /* data to return from this function */
   ll_data_t return_data;

   /* Assume that this will never be null for now. 
    * Bad assumption, but the instructions say so for now
    * Come back to this later to fix this assumption
    * Also, check that it is actually the last value*/
   if(list->last == NULL){ return -1; }
   last_object = list->last;
   /* Get second to last object from list; NULL is a valid value */
   second_last_object = last_object->prev;
   /* Get the data out of the last object */
   return_data = last_object->data;

   /* Move list's pointer of where the last object is to the new last object */
   list->last = second_last_object;
   if(last_object == list->first){
      list->first = NULL;
   }
   /* clear new last object's next value, since it's done now */
   if(second_last_object != NULL){
      second_last_object->next = NULL;
   }

   /* Nobody left listening to this object, can be freed without consequence(?)*/
   free(last_object);

   /* Return data, end of function */
   return return_data;
}

// inserts item at front of a list
void list_unshift(struct list *list, ll_data_t item_data){
   /* Create new object, allocate memory */
   struct list_node *new_object = calloc(1,sizeof(struct list_node));
   /* Pointer to previous back object */
   struct list_node *first_object = list->first;

   /* If the list is empty, first object will be null */
   if(first_object == NULL){
      /* If the list is empty, this newly added object is both last and first */
      list->first = new_object;
      list->last = new_object;
      /* If the list is empty, previous needs to be null, since there
      *  isn't anything else in the list */
      new_object->prev = NULL;
   } else {
      /* If the list ISN'T empty, be sure to tie the first object and the new object together */
      new_object->next = first_object;
      first_object->prev = new_object;
      /* Append first object to list */
      list->first = new_object;
   }

   /* Since we are appending to the back of the list, there is no next object */
   new_object->prev = NULL;
   /* Assign value */
   new_object->data = item_data;
}

// removes item from front of a list
ll_data_t list_shift(struct list *list){
   /* the last object in the list */
   struct list_node *last_object;
   /* the second to last object in the list */
   struct list_node *second_last_object;
   /* data to return from this function */
   ll_data_t return_data;

   /* Assume that this will never be null for now. 
    * Bad assumption, but the instructions say so for now
    * Come back to this later to fix this assumption
    * Also, check that it is actually the last value*/
   last_object = list->first;
   /* Get second to last object from list; NULL is a valid value */
   second_last_object = last_object->next;
   /* Get the data out of the last object */
   return_data = last_object->data;

   /* Move list's pointer of where the last object is to the new last object */
   list->first = second_last_object;
   if(last_object == list->last){
      list->last = NULL;
   }
   /* clear new last object's next value, since it's done now */
   if(second_last_object != NULL){
      second_last_object->prev = NULL;
   }

   /* Nobody left listening to this object, can be freed without consequence(?)*/
   free(last_object);

   /* Return data, end of function */
   return return_data;
}

// deletes a node that holds the matching data
void list_delete(struct list *list, ll_data_t data){
   struct list_node *object = list->first;
   struct list_node *prev;
   struct list_node *next;
   /*If the list is empty, don't do anything */
   if(object == NULL){
      return;
   }
   /*Search for the first correct object */
   while(object->data != data){
      if(object->next == NULL){
         return;
      }
      object = object->next;
   }
   /*object is now the correct object*/

   /*Remap internally */
   prev = object->prev;
   next = object->next;
   if(prev != NULL){
      /* If we aren't at the beginning of the list, 
       * tie the previous to the next */
      prev->next = next;
   }else {
      /*If we ARE at the beginning of the list,
       * inform the list of the change*/
      list->first = next;
   }
   if(next != NULL){
      /* If we aren't at the end of the list, tie the next to the previous */
      next->prev = prev;
   } else {
      /* If we ARE at the end of the list, inform the list of the change */
      list->last = prev;
   }
   /* No more ties to this object, we can safely free it */
   free(object);
}

// destroys an entire list
// list will be a dangling pointer after calling this method on it
void list_destroy(struct list *list){
   struct list_node *first = list->first;
   struct list_node *next;
   if(first != NULL){
      do{
         next = first->next;
         free(first);
         first = next;
      }while(next != NULL);
   }
   free(list);
}