Linked List Demo

main.c

// compiled and run via gcc on Linux/Mac: gcc main.c && ./a.out
// on windows (Cygwin)... gcc main.c && ./a.exe

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

#define SUCCESS 0
#define MALLOCFAIL 1
#define INDEXOUTOFBOUNDS INT_MAX
#define INDEXOUTOFBOUNDSCODE 2
#define UNKNOWNEXCEPTION 128

typedef struct LLNode {
  int data;
  struct LLNode* next;
} LLNode;

typedef struct {
  // keep this around so we don't have to count later
  int length;
  LLNode* head;
} LList;


LList* newLList(){
  LList* r = malloc(sizeof(LList));
  if (r == NULL){
    return r;
  }
  r->length = 0;
  r->head = NULL;
  return r;
}

LLNode* newNode(int data){
  LLNode* r = malloc(sizeof(LLNode));
  if (r == NULL){
    return r;
  }
  r->data = data;
  r->next = NULL;
  return r;
}

void printList(LList* list){
  LLNode* current = list->head;

  printf("HEAD");
  while(current != NULL) {
    printf("->%d", current->data);
    current = current->next;
  }
  printf("->NULL\n");

/* // or recursively...
  if (list->head == NULL) {
    printf("->NULL");
  } else {
    printf("->%d", list->head->data);
    LList rest = *list;
    rest.length--;
    rest.head = list->head->next;
    printList(&rest);
  }*/
}

int prepend(LList* list, int data){
  LLNode* node = newNode(data);
  if(node == NULL) {
    return MALLOCFAIL;
  }
  node->next = list->head;
  list->head = node;
  list->length++;
  return SUCCESS;
}

int freeList(LList* list){
  // while(list->head != NULL){
  //   LLNode* next = list->head->next;
  //   printf("Freeing... %d\n", list->head->data);
  //   free(list->head);
  //   list->head = next;
  // }

  // just leverage what I've written elsewhere
  while (pop(list) != INDEXOUTOFBOUNDS);

  printf("Freeing List.\n");
  free(list);
  return SUCCESS;
}


int append(LList* list, int data){
  LLNode* node = newNode(data);
  if(node == NULL) return MALLOCFAIL;

  if (list->head == NULL) { list->head = node; }
  else {
    LLNode* current = list->head;
    while (current->next != NULL){
      current = current->next;
    }
    current->next = node;
  }
  list->length++;
  return SUCCESS;
}

int get(LList* list, unsigned int index){
  unsigned int i = 0;
  LLNode* current = list->head;
  if (index >= list->length || index < 0) return INDEXOUTOFBOUNDS;
  while(i < index){
    current = current->next;
    i++;
  }
  return current->data;
}

int set(LList* list, unsigned int index, int data){
  unsigned int i = 0;
  LLNode* current = list->head;
  if (index >= list->length || index < 0) return INDEXOUTOFBOUNDS;
  while(i < index){
    current = current->next;
    i++;
  }
  current->data = data;
  return SUCCESS;
}

int push(LList* list, int data){
  return prepend(list, data);
}

int enqueue(LList *list, int data){
  return append(list, data);
}

int pop(LList* list){
  LLNode* head = list->head;
  if(head == NULL) {
    return INDEXOUTOFBOUNDS;  // some sentinel value saying I couldn't remove it
                              // this means INT_MAX should not allowed in input data...
  }
  list->head = head->next;
  list->length--;
  int ret = head->data;
  printf("Freeing... %d\n", ret);
  free(head);
  return ret;
}

int dequeue(LList* list){
  return pop(list);
}

int main(void){
  printf("Initial, empty list:\n");
  LList* my_list = newLList();
  printList(my_list);
  printf("\nPrepending 7 to the list:\n");
  prepend(my_list, 7);
  printList(my_list);
  printf("\nPrepending 5 to the list:\n");
  prepend(my_list, 5);
  printList(my_list);
  printf("\nAppending 3 to the list:\n");
  append(my_list, 3);
  printList(my_list);
  printf("\nPushing 100 onto my list:\n");
  push(my_list, 100);
  printList(my_list);

  printf("\nBefore set:\n");
  printList(my_list);
  if (set(my_list, 2, 101)) {
    printf("Fails to set...");
  }
  printf("\nAfter set:\n");
  printList(my_list);
  printf("\nValue at index 1: %d\n", get(my_list, 1));
  if (get(my_list, 7) == INDEXOUTOFBOUNDS) {
    fprintf(stderr, "Could not get out of bounds BOOM!: %d\n", INDEXOUTOFBOUNDS);
    //return INDEXOUTOFBOUNDSCODE;
  }

  printf("\nFreeing my_list...\n");
  freeList(my_list);
  my_list = NULL;
  printf("\nFreeing empty list...\n");
  freeList(newLList());

  printf("\n\nStack testing:\n");
  LList* stack = newLList();
  printf("Empty Stack:\n");
  printList(stack);

  printf("\npush(stack, 1)\n");
  push(stack, 1);
  printList(stack);

  printf("\npush(stack, 2)\n");
  push(stack, 2);
  printList(stack);

  printf("\npush(stack, 3)\n");
  push(stack, 3);
  printList(stack);

  printf("\npop(stack)\n");
  printf("pop: %d\n", pop(stack));
  printList(stack);

  printf("\npush(stack, 4)\n");
  push(stack, 4);
  printList(stack);

  printf("\npopping everything off the stack:\n");
  int x;
  while ((x = pop(stack)) != INDEXOUTOFBOUNDS){
    printf("pop: %d\n", x);
  }
  printList(stack);

  printf("\nFreeing stack:\n");
  freeList(stack);
  stack = NULL;

  printf("\n\nQueue testing:\n");
  LList* queue = newLList();
  printf("Empty Queue:\n");
  printList(queue);

  printf("\nenqueue(queue, 1)\n");
  enqueue(queue, 1);
  printList(queue);

  printf("\nenqueue(queue, 2)\n");
  enqueue(queue, 2);
  printList(queue);

  printf("\nenqueue(queue, 3)\n");
  enqueue(queue, 3);
  printList(queue);

  printf("\ndequeue(queue)\n");
  printf("dequeue: %d\n", dequeue(queue));
  printList(queue);

  printf("\nenqueue(queue, 4)\n");
  enqueue(queue, 4);
  printList(queue);

  printf("\ndraining the queue:\n");
  int y;
  while ((y = dequeue(queue)) != INDEXOUTOFBOUNDS){
    printf("dequeue: %d\n", y);
  }
  printList(queue);

  printf("\nFreeing queue:\n");
  freeList(queue);
  queue = NULL;

  return SUCCESS;
}

sample_output.txt

Initial, empty list:
HEAD->NULL

Prepending 7 to the list:
HEAD->7->NULL

Prepending 5 to the list:
HEAD->5->7->NULL

Appending 3 to the list:
HEAD->5->7->3->NULL

Pushing 100 onto my list:
HEAD->100->5->7->3->NULL

Before set:
HEAD->100->5->7->3->NULL

After set:
HEAD->100->5->101->3->NULL

Value at index 1: 5
Could not get out of bounds BOOM!: 2147483647

Freeing my_list...
Freeing... 100
Freeing... 5
Freeing... 101
Freeing... 3
Freeing List.

Freeing empty list...
Freeing List.


Stack testing:
Empty Stack:
HEAD->NULL

push(stack, 1)
HEAD->1->NULL

push(stack, 2)
HEAD->2->1->NULL

push(stack, 3)
HEAD->3->2->1->NULL

pop(stack)
Freeing... 3
pop: 3
HEAD->2->1->NULL

push(stack, 4)
HEAD->4->2->1->NULL

popping everything off the stack:
Freeing... 4
pop: 4
Freeing... 2
pop: 2
Freeing... 1
pop: 1
HEAD->NULL

Freeing stack:
Freeing List.


Queue testing:
Empty Queue:
HEAD->NULL

enqueue(queue, 1)
HEAD->1->NULL

enqueue(queue, 2)
HEAD->1->2->NULL

enqueue(queue, 3)
HEAD->1->2->3->NULL

dequeue(queue)
Freeing... 1
dequeue: 1
HEAD->2->3->NULL

enqueue(queue, 4)
HEAD->2->3->4->NULL

draining the queue:
Freeing... 2
dequeue: 2
Freeing... 3
dequeue: 3
Freeing... 4
dequeue: 4
HEAD->NULL

Freeing queue:
Freeing List.