20-queue-and-stack/advanced_singly_linked_list.c

/*----------------------------------------------------------
 *				HTBLA-Leonding / Class: 2IHIF
 * ---------------------------------------------------------
 * Exercise Number: S03
 * Title:			Advanced Singly Linked List implementation
 * Author:			Marc Tismonar
 * ----------------------------------------------------------
 * Description:
 * Implementation of an advanced singly linked list.
 * ----------------------------------------------------------
 */

/*
  Implementation notes:

  1) The 'ListData' struct of this linked list SHALL have
     - a pointer to the head node
     - a pointer to the tail node
     - the number of nodes (size)

  2) List and list node allocation: 
     Use functions `mem_alloc(…)` and `mem_free(…)`
     declared in `allocator.h`. DO NOT use `malloc(…)` and `free(…)` directly
     as unit tests will fail.

  3) Implement get_at, insert and insert_at, remove_at in a way that operations
     affecting head or tail are performed with O(1)!

  4) Use 'limits.h' to get maximum and minimum values for numeric types, if needed.

  5) Avoid code duplication wherever (reasonably) possible.
     This is valid for implementation of similar functions as well
     as for reoccurring code patterns, such as list iteration.
     Nevertheless, aim for efficiency, e.g. `remove_all` shall traverse 
     the list only once and not use `remove` as defined, because
     the later would start at the beginning of the list for each iteration.
*/

#include "advanced_singly_linked_list.h"

/* add includes as needed */

#include <stdbool.h>
#include "config.h"
#include "allocator.h"

/** The type of list nodes */
typedef struct IntListNodeData* IntListNode;

/** The implementation of list node data */
struct IntListNodeData {
   int data;
   IntListNode next;
};

/** The implementation of list data: head, tail, size! */
struct IntListData {
   IntListNode head;
   IntListNode tail;
   int size;
};


/* ===================================================================== */
/* private list functions */


static IntListNode list_obtain_node(int data) {
   IntListNode node = (IntListNode)alloc_mem(sizeof(struct IntListNodeData));
   node->data = data;
   node->next = 0;
   return node;
}

static void list_release_node(IntListNode node) {
   free_mem(node);
   node = 0;
}


/* ===================================================================== */

/**
 * Obtains ('creates') and provides a 'new' list instance.
 * Any list obtained via this function MUST be released using
 * function `release_list()`.
 * 
 * Note: This function does not make any assumptions 
 * about how list components, esp. nodes, are allocated.
 * 
 * @return IntList The list instance or 0, if no list could by instantiated.
 */
IntList list_obtain() {
   IntList intList = (IntList)alloc_mem(sizeof(struct IntListData));
   if (intList != 0) {
      intList->head = 0;
      intList->tail = 0;
      intList->size = 0;
   }
   return intList;
}

/**
 * Releases a list that was obtained earlier via function `obtain_list`.
 * Released lists MUST NOT be used anymore.
 * 
 * Note: The implementation of this function does not make any assumptions
 * about the allocation method of list elements, but MUST match the implementation
 * of function `obtain_list` as its inverse function.
 * 
 * @param p_list The pointer to the list to release. The value of the pointer
 * is set to 0, if the list was successfully released, otherwise it is left untouched.
 */
void list_release(IntList* p_list) { // no need to use the tail & size as its going to free everything anyways
   if (p_list == 0 || *p_list == 0) {
      return;
   }
   
   IntList list = *p_list;
   IntListNode current = list->head;
   
   while (current != 0) {
      IntListNode next = current->next;
      list_release_node(current);
      current = next;
   }
   
   free_mem(list);
   *p_list = 0;
}

/**
 * Determines whether or not the given list is valid.
 * 
 * @param list The list to evaluate.
 * @return `True` if the list is valid, false otherwise.
 */
bool list_is_valid(IntList list) {
   return list != 0;
}

/**
 * Determines whether or not the list contains at least one item.
 * 
 * @param list The list to evaluate.
 * @return `False` if the list contains one or more items, `true` otherwise.
 */
bool list_is_empty(IntList list) {
   if (!list_is_valid(list)) {
      return true;
   }

   return list->head == 0 && list->tail == 0 && list->size == 0;
}

/**
 * Provides the number of values stored in the list.
 * 
 * @param list The list to evaluate.
 * @return The number of values the list contains.
 */
int list_get_size(IntList list) {
   if(!list_is_valid(list)) {
      return 0;
   }

   return list->size;
}

/**
 * Determines whether or not the list given list contains the queried value
 * at least once.
 * 
 * @param list The list to query.
 * @param value The value.
 * @return `True` if the list contains at least one instance of the value, 
 * `false ` otherwise.
 */
bool list_contains(IntList list, int value) {
   if (!list_is_valid(list)) {
      return false;
   }
   
   IntListNode current = list->head;
   while (current != 0) {
      if (current->data == value) {
         return true;
      }
      current = current->next;
   }
   
   return false;
}

/**
 * Provides the value stored in the list at the given position.
 * 
 * @param list The list from which the value shall be retrieved.
 * @param index The zero-based position index of the value to retrieve.
 * @return The value stored at the given position or 0, if the position
 * is not available.
 */
int list_get_at(IntList list, unsigned int index) {
   if (!list_is_valid(list) || list_is_empty(list)) {
      return 0;
   }
   
   if (index < list->size) {
      IntListNode current = list->head;
      for(unsigned int i = 0; i < index; i++) {
         current = current->next;
      }
      return current->data;
   }
   
   return 0;
}

/**
 * Inserts the given value at the end of the given list.
 * 
 * @param list The list to which the value shall be appended.
 * @param value The value to append to the list.
 */
void list_insert(IntList list, int value) {
   if (!list_is_valid(list)) {
      return;
   }
   
   IntListNode newNode = list_obtain_node(value);
   
   if (newNode != 0) {
      if (list_is_empty(list)) {
         list->head = newNode;
      } else {
         list->tail->next = newNode;
      }
   }

   list->tail = newNode;
   list->size++;
}

/**
 * Inserts the given value at the indexed position in a way the 
 * the inserted value is on that position. The index is
 * - similar to arrays - zero-based. If the the list is shorter
 * than the indexed position, the value is inserted at the end
 * of the list.
 * 
 * @param list The list into which the value shall be appended.
 * @param index The position index of the value to insert.
 * @param value  The value to insert.
 */
void list_insert_at(IntList list, unsigned int index, int value) {
   if (!list_is_valid(list)) {
      return;
   }
   
   IntListNode newNode = list_obtain_node(value);
   if (newNode == 0) {
      return;
   }
   
   if (list_is_empty(list)) {
      list->head = newNode;
      list->tail = newNode;
      list->size++;
      return;
   }
   
   if (index == 0) {
      newNode->next = list->head;
      list->head = newNode;
      list->size++;
      return;
   }
   
   IntListNode current = list->head;
   for (unsigned int i = 0; i < index - 1 && current->next != 0; i++) {
      current = current->next;
   }
   
   if (current->next == 0) {
      current->next = newNode;
      list->tail = newNode;
   }
   else {
      newNode->next = current->next;
      current->next = newNode;
   }

   list->size++;
}

/**
 * Appends the `list_to_append` at the end of the given `list`.
 * The appended list is empty afterwards, because all nodes of that list
 * have been transferred to `list`.
 * 
 * @param list The list that receives the other list.
 * @param list_to_append The list that is appended to `list`.
 */
void list_append(IntList list, IntList list_to_append) {
   if (!list_is_valid(list) || !list_is_valid(list_to_append) || list_is_empty(list_to_append)) {
      return;
   }
   
   if (list_is_empty(list)) {
      list->head = list_to_append->head;
      list->tail = list_to_append->tail;
      list->size = list_to_append->size;
   } else {
      list->tail->next = list_to_append->head;
      list->tail = list_to_append->tail;
      list->size += list_to_append->size;
   }
   
   list_to_append->head = 0;
   list_to_append->tail = 0;
   list_to_append->size = 0;
}

/**
 * Removes the first occurrance of `value` from the given list.
 * If the list does not contain that value, the list shall not
 * be modified.
 * 
 * @param list The list from which the given value shall be removed.
 * @param value The value to remove from the list.
 */
void list_remove(IntList list, int value) {
   if (!list_is_valid(list) || list_is_empty(list)) {
      return;
   }

   if (list->head->data == value) {
      IntListNode old_head = list->head;
      list->head = list->head->next;
      
      // If list becomes empty, update tail
      if (list->head == 0) {
         list->tail = 0;
      }
      
      list_release_node(old_head);
      list->size--;
      return;
   }

   for (IntListNode current = list->head; current->next != 0; current = current->next) {
      if (current->next->data == value) {
         IntListNode to_remove = current->next;
         current->next = to_remove->next;
         
         if (to_remove == list->tail) {
            list->tail = current;
         }
         
         list_release_node(to_remove);
         list->size--;
         return;
      }
   }
}

/**
 * Removes all occurrances of `value` from the list.
 * If the list does not contain that value, the list shall not
 * be modified.
 * 
 * @param list The list from which all occurrances of `value` shall be removed.
 * @param value The `value` to remove throughout the list.
 */
void list_remove_all(IntList list, int value) {
   if (!list_is_valid(list) || list_is_empty(list)) {
      return;
   }
   
   while (list->head != 0 && list->head->data == value) {
      IntListNode old_head = list->head;
      list->head = list->head->next;
      
      if (list->head == 0) {
         list->tail = 0;
      }
      
      list_release_node(old_head);
      list->size--;
   }
   
   if (list_is_empty(list)) {
      return;
   }

   IntListNode prev = list->head;
   IntListNode current = list->head->next;
   
   while (current != 0) {
      if (current->data == value) {
         prev->next = current->next;
         
         if (current == list->tail) {
            list->tail = prev;
         }
         
         IntListNode to_remove = current;
         current = current->next;
         
         list_release_node(to_remove);
         list->size--;
      } else {
         prev = current;
         current = current->next;
      }
   }
}

/**
 * Removes the value at the indexed position from the given list
 * and provides that value. If the list does not have a value
 * at that position, the list remains unmodified.
 * 
 * @param list The list from which the value at the given index shall be returned.
 * @param index The zero-based index of the value to return.
 * @return The removed value or 0 in case of errors.
 */
int list_remove_at(IntList list, unsigned int index) {
   if (!list_is_valid(list) || list_is_empty(list) || index >= list->size) {
      return 0;
   }

   int value;
   
   if (index == 0) {
      value = list->head->data;
      IntListNode old_head = list->head;
      list->head = list->head->next;
      
      if (list->head == 0) {
         list->tail = 0;
      }
      
      list_release_node(old_head);
      list->size--;
      return value;
   }
   
   IntListNode current = list->head;
   for (unsigned int i = 0; i < index - 1; i++) {
      current = current->next;
   }
   
   IntListNode to_remove = current->next;
   value = to_remove->data;
   
   current->next = to_remove->next;
   
   if (to_remove == list->tail) {
      list->tail = current;
   }
   
   list_release_node(to_remove);
   list->size--;
   return value;
}

/**
 * Clears the given list by removing all values from the list.
 * 
 * @param list The list to clear.
 */
void list_clear(IntList list) {
   if (!list_is_valid(list) || list_is_empty(list)) {
      return;
   }
   
   IntListNode current = list->head;
   while (current != 0) {
      IntListNode next = current->next;
      list_release_node(current);
      current = next;
   }
   
   list->head = 0;
   list->tail = 0;
   list->size = 0;
}