6 files changed, 1385 insertions, 0 deletions

diff --git a/src/01/README.md b/src/01/README.md
new file mode 100644
index 0000000..9957da2
--- /dev/null
+++ b/src/01/README.md
@@ -0,0 +1,30 @@
+# Assignment 1 - Computer Science 272: Data Structures and Algorithms
+
+Answer question 1, question 2, and any other 2 questions from questions 3 to 6 – maximum 100 marks.
+You must score at least 50 to pass the assignment.
+
+1. You have learned some fundamental data structure concepts such as array,
+  queue and priority queue, stack, list and linked list, sequence,
+  and unordered set, and you understand the concept of interface or abstract data type that defines the set of operations supported by a data structure and the semantics, or meaning, of those operations.
+  You can use the interface of one particular data structure to define or implement the operations of a different data structure.
+  * a. Describe the meaning of the essential methods `add(x)`, `deleteMin()`, and `size()` that are supported by the priority queue interface. Implement those methods using a singly-linked list. Analyze the running time of the `add(x)` and `deletMin()` operations based on this implementation.
+    * The `add(x)` method is used to add an element to the queue with a priority.
+    * The `deleteMin()` method is used to remove the element with the lowest priority from the queue and return it.
+    * The `size()` method is used to determine how many items are in the queue.
+    * The `add(x)` function is linear time O(n).
+    * The `deleteMin(x)` function is constant time O(1).
+  * b. Implement the stack methods `push(x)` and `pop()` using two queues.
+    Analyze the running time of the `push(x)` and `pop()` operations based on this implementation.
+2. Swap two adjacent elements in a list by adjusting only the links (and not the data) using:
+  * a. singly-linked list.
+  * b. doubly-linked list.
+3. Using a `USet`, implement a `Bag`. A `Bag` is like a `USet` - it supports the `add(x)`, `remove(x)`, and `find(x)` methods - but it allows duplicate elements to be stored.
+  The `find(x)` operation in a Bag returns some element (if any) that is equal to x.
+  In addition, a `Bag` supports the `findAll(x)` operation that returns a list of all elements in the Bag that are equal to x.
+4. Design and implement a `RandomQueue`.
+  This is an implementation of the Queue interface in which the `remove()` operation removes an element that is chosen uniformly at random among all the elements currently in the queue.
+  (Think of a RandomQueue as a bag in which we can add elements or reach in and blindly remove some random element.)
+  The `add(x)` and `remove()` operations in a `RandomQueue` should run in constant time per operation.
+5. Write a method, `reverse()`, that reverses the order of elements in a `DLList`
+6. Design and implement a `MinStack` data structure that can store comparable elements and supports the stack operations `push(x)`, `pop()`, and `size()`, as well as the `min()` operation, which returns the minimum value currently stored in the data structure.
+  All operations should run in constant time.
diff --git a/src/01/min_stack_test.c b/src/01/min_stack_test.c
new file mode 100644
index 0000000..383ae62
--- /dev/null
+++ b/src/01/min_stack_test.c
@@ -0,0 +1,171 @@
+#include <cgreen/cgreen.h>
+
+/*
+   Design and implement a `MinStack` data structure that can store
+   comparable elements and supports the stack operations:
+
+ * `push(x)`
+ * `pop()`
+ * `size()`
+ * `min()`
+ All operations should run in constant time.
+ */
+
+Describe(MinStack);
+BeforeEach(MinStack){ }
+AfterEach(MinStack){ }
+
+struct node {
+  int data;
+  struct node *next;
+};
+
+typedef struct node Node;
+
+typedef struct {
+  Node *head;
+} Stack;
+
+static Stack *initialize() {
+  Stack *self = malloc(sizeof(Stack));
+  self->head = NULL;
+  return self;
+}
+
+static int size(Stack *self) {
+  Node *current = self->head;
+  int i;
+  for (i = 0; current != NULL; i++)
+    current = current->next;
+  return i;
+}
+
+static Node *new(int data) {
+  Node *node = malloc(sizeof(Node));
+  node->next = NULL;
+  node->data = data;
+  return node;
+}
+
+static int compare(int x, int y) {
+  return x == y ? 0 : (x > y) ? 1 : -1;
+}
+
+static void insert(Node **self, int data) {
+  int comparison = compare(data, (*self)->data);
+  Node *node = new(data);
+
+  switch(comparison) {
+    case 1:
+      if ((*self)->next)
+        insert(&((*self)->next), data);
+      else
+        (*self)->next = node;
+      break;
+    default:
+      node->next = *self;
+      *self = node;
+      break;
+  }
+}
+
+static void push(Stack *self, int data) {
+  if (self->head)
+    insert(&self->head, data);
+  else
+    self->head = new(data);
+}
+
+static int min(Stack *self) {
+  if (self && self->head)
+    return self->head->data;
+
+  return (int)NULL;
+}
+
+static int pop(Stack *self) {
+  if (!self->head)
+    return (int)NULL;
+
+  Node *current = self->head;
+  int data = current->data;
+  self->head = current->next;
+  current->next = NULL;
+  free(current);
+  return data;
+}
+
+Ensure(MinStack, when_empty) {
+  Stack *stack = initialize();
+
+  assert_that(size(stack), is_equal_to(0));
+  assert_that(min(stack), is_equal_to(NULL));
+  assert_that(pop(stack), is_equal_to(NULL));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_pushing_a_single_integer) {
+  Stack *stack = initialize();
+
+  push(stack, 1);
+
+  assert_that(size(stack), is_equal_to(1));
+  assert_that(min(stack), is_equal_to(1));
+  assert_that(pop(stack), is_equal_to(1));
+  assert_that(size(stack), is_equal_to(0));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_pushing_multiple_integers_out_of_order) {
+  Stack *stack = initialize();
+
+  push(stack, 2);
+  push(stack, 3);
+  push(stack, 1);
+
+  assert_that(size(stack), is_equal_to(3));
+  assert_that(min(stack), is_equal_to(1));
+
+  assert_that(pop(stack), is_equal_to(1));
+  assert_that(size(stack), is_equal_to(2));
+
+  assert_that(pop(stack), is_equal_to(2));
+  assert_that(size(stack), is_equal_to(1));
+
+  assert_that(pop(stack), is_equal_to(3));
+  assert_that(size(stack), is_equal_to(0));
+
+  assert_that(pop(stack), is_equal_to(NULL));
+  assert_that(size(stack), is_equal_to(0));
+
+  free(stack);
+}
+
+Ensure(MinStack, when_pushing_duplicate_values_on_to_the_stack) {
+  Stack *stack = initialize();
+
+  push(stack, 2);
+  push(stack, 1);
+  push(stack, 2);
+
+  assert_that(size(stack), is_equal_to(3));
+  assert_that(min(stack), is_equal_to(1));
+
+  assert_that(pop(stack), is_equal_to(1));
+  assert_that(pop(stack), is_equal_to(2));
+  assert_that(pop(stack), is_equal_to(2));
+  assert_that(pop(stack), is_equal_to(NULL));
+
+  free(stack);
+}
+
+TestSuite *min_stack_tests() {
+  TestSuite *suite = create_test_suite();
+
+  add_test_with_context(suite, MinStack, when_empty);
+  add_test_with_context(suite, MinStack, when_pushing_a_single_integer);
+  add_test_with_context(suite, MinStack, when_pushing_multiple_integers_out_of_order);
+  return suite;
+}
diff --git a/src/01/priority_queue_test.c b/src/01/priority_queue_test.c
new file mode 100644
index 0000000..f754c33
--- /dev/null
+++ b/src/01/priority_queue_test.c
@@ -0,0 +1,150 @@
+#include <cgreen/cgreen.h>
+#include <string.h>
+
+/*
+Implement the methods of the priority queue interface using a singly-linked list.
+
+* `add(x)`
+* `deleteMin()`
+* `size()`
+
+Analyze the running time of the `add(x)` and `deletMin()` operations based on this implementation.
+*/
+struct node {
+  int priority;
+  int data;
+  struct node *next;
+};
+
+typedef struct node Node;
+
+typedef struct {
+  Node *head;
+  int size;
+} PriorityQueue;
+
+
+// https://en.wikipedia.org/wiki/Priority_queue
+static PriorityQueue *initialize() {
+  PriorityQueue *queue = malloc(sizeof(PriorityQueue));
+  queue->size = 0;
+  queue->head = NULL;
+  return queue;
+}
+
+static Node *create_node(int priority, int data) {
+  Node *node = malloc(sizeof(Node));
+  node->priority = priority;
+  node->data = data;
+  node->next = NULL;
+  return node;
+}
+
+// This function is constant time O(1)
+static int size(PriorityQueue *queue) {
+  return queue->size;
+}
+
+// This function is linear time O(n)
+static void add(PriorityQueue *queue, Node *node) {
+  queue->size++;
+
+  if (queue->head == NULL) {
+    queue->head = node;
+    return;
+  }
+
+  Node *tmp = queue->head;
+  Node *prev = NULL;
+
+  while(tmp != NULL) {
+    if (tmp->data > node->data) {
+      node->next = tmp;
+      if (tmp == queue->head)
+        queue->head = node;
+      else if (prev != NULL)
+        prev->next = node;
+      break;
+    }
+    prev = tmp;
+    tmp = tmp->next;
+  }
+}
+
+// This function is constant time O(1)
+static Node *delete_min(PriorityQueue *queue) {
+  Node *tmp = queue->head;
+  queue->head = tmp->next;
+  return tmp;
+}
+
+static void inspect(PriorityQueue *queue) {
+  Node *tmp = queue->head;
+
+  while(tmp) {
+    printf("%d\n", tmp->data);
+    tmp = tmp->next;
+  }
+}
+
+static void destroy(PriorityQueue *queue) {
+  Node *current = queue->head;
+  Node *tmp;
+
+  while(current) {
+    tmp = current, current = current->next;
+
+    if (tmp) free(tmp);
+  }
+  free(queue);
+}
+
+Describe(PriorityQueue);
+BeforeEach(PriorityQueue){ }
+AfterEach(PriorityQueue){ }
+
+Ensure(PriorityQueue, returns_size) {
+  PriorityQueue *queue = initialize();
+
+  assert_that(size(queue), is_equal_to(0));
+
+  destroy(queue);
+}
+
+Ensure(PriorityQueue, adds_a_node) {
+  PriorityQueue *queue = initialize();
+  Node *node = create_node(1, 0);
+
+  add(queue, node);
+
+  assert_that(size(queue), is_equal_to(1));
+
+  destroy(queue);
+}
+
+Ensure(PriorityQueue, removes_the_node_with_the_lowest_priority){
+  PriorityQueue *queue = initialize();
+  Node *min = create_node(1, 100);
+  Node *mid = create_node(2, 200);
+  Node *max = create_node(3, 300);
+
+  add(queue, max);
+  add(queue, min);
+  add(queue, mid);
+
+  assert_that(size(queue), is_equal_to(3));
+  assert_that(delete_min(queue), is_equal_to(min));
+  assert_that(queue->head, is_equal_to(mid));
+
+  destroy(queue);
+};
+
+TestSuite *priority_queue_tests() {
+  TestSuite *suite = create_test_suite();
+
+  add_test_with_context(suite, PriorityQueue, returns_size);
+  add_test_with_context(suite, PriorityQueue, adds_a_node);
+  add_test_with_context(suite, PriorityQueue, removes_the_node_with_the_lowest_priority);
+
+  return suite;
+}
diff --git a/src/01/stack_test.c b/src/01/stack_test.c
new file mode 100644
index 0000000..b34c191
--- /dev/null
+++ b/src/01/stack_test.c
@@ -0,0 +1,168 @@
+#include <cgreen/cgreen.h>
+
+/*
+Implement the stack methods using two queues
+
+* `push(x)`
+* `pop()`
+
+Analyze the running time of the `push(x)` and `pop()` operations based on this implementation.
+*/
+
+struct node {
+  int data;
+  struct node *next;
+};
+
+typedef struct node Node;
+
+typedef struct {
+  Node *head;
+  int size;
+} Queue;
+
+typedef struct {
+  Queue *q1;
+} Stack;
+
+static Queue *newQueue(){
+  Queue *queue = malloc(sizeof(Queue));
+  queue->size = 0;
+  queue->head = NULL;
+  return queue;
+}
+
+static Stack *initialize() {
+  Stack *stack = malloc(sizeof(Stack));
+  stack->q1 = newQueue();
+  return stack;
+}
+
+Node *newNode(int data) {
+  Node *node = malloc(sizeof(Node));
+  node->data = data;
+  node->next = NULL;
+  return node;
+}
+
+void enqueue(Queue *q, int data) {
+  Node *node = newNode(data);
+  q->size++;
+
+  if (q->head == NULL) {
+    q->head = node;
+  } else {
+    Node *tail = q->head;
+
+    while (tail->next != NULL)
+      tail = tail->next;
+    tail->next = node;
+  }
+}
+
+int dequeue(Queue *q) {
+  if (q->head == NULL) return -1;
+
+  Node *node = q->head;
+  int data = node->data;
+
+  q->head = node->next;
+  free(node);
+  return data;
+}
+
+// The running time is linear time.
+static void push(Stack *stack, int data) {
+  enqueue(stack->q1, data);
+}
+
+// The running time is linear time.
+static int pop(Stack *stack) {
+  int count = stack->q1->size - 1;
+  Queue *tmp = newQueue();
+
+  for (int i = 0; i < count; i++)
+    enqueue(tmp, dequeue(stack->q1));
+
+  int data = dequeue(stack->q1);
+  free(stack->q1);
+  stack->q1 = tmp;
+  return data;
+}
+
+int size(Stack *stack) {
+  return stack->q1->size;
+}
+
+static void destroy(Stack *stack) {
+  int count = size(stack);
+
+  for (int i = 0; i < count; i++)
+    pop(stack);
+
+  free(stack->q1);
+  free(stack);
+}
+
+static void inspect(Queue *q) {
+  Node *tmp = q->head;
+
+  if (q->size == 0) {
+    printf("[]\n");
+    return;
+  }
+
+  printf("[");
+  for (int i = 0; i < q->size; i++) {
+    printf("%d,", tmp->data);
+    tmp = tmp->next;
+  }
+  printf("\b]\n");
+}
+
+Describe(Stack);
+BeforeEach(Stack){ }
+AfterEach(Stack){ }
+
+Ensure(Stack, push_onto_stack) {
+  Stack *stack = initialize();
+
+  push(stack, 1);
+  assert_that(size(stack), is_equal_to(1));
+
+  push(stack, 2);
+  assert_that(size(stack), is_equal_to(2));
+
+  destroy(stack);
+}
+
+Ensure(Stack, pop_single_item) {
+  Stack *stack = initialize();
+
+  push(stack, 1);
+
+  assert_that(pop(stack), is_equal_to(1));
+  destroy(stack);
+}
+
+Ensure(Stack, pop_successive_items) {
+  Stack *stack = initialize();
+
+  push(stack, 1);
+  push(stack, 2);
+
+  assert_that(pop(stack), is_equal_to(2));
+  assert_that(pop(stack), is_equal_to(1));
+
+  destroy(stack);
+}
+
+TestSuite *stack_tests() {
+  TestSuite *suite = create_test_suite();
+
+  add_test_with_context(suite, Stack, push_onto_stack);
+  add_test_with_context(suite, Stack, pop_single_item);
+  add_test_with_context(suite, Stack, pop_successive_items);
+
+  return suite;
+}
diff --git a/src/01/swap_doubly_linked_list_test.c b/src/01/swap_doubly_linked_list_test.c
new file mode 100644
index 0000000..0520f67
--- /dev/null
+++ b/src/01/swap_doubly_linked_list_test.c
@@ -0,0 +1,588 @@
+#include <cgreen/cgreen.h>
+/*
+Swap two adjacent elements in a list by adjusting
+only the links (and not the data) using a:
+* singly-linked list
+* doubly-linked list
+*
+*
+* Write a method, `reverse()`, that reverses the order of elements in a `DLList`
+*/
+
+Describe(DoublyLinkedList);
+BeforeEach(DoublyLinkedList){ }
+AfterEach(DoublyLinkedList){ }
+
+struct node {
+  int data;
+  struct node *next;
+  struct node *prev;
+};
+
+typedef struct node Node;
+
+static void print(Node *node) {
+  if (node->prev && node->next)
+    printf("%d <- %d -> %d\n", node->prev->data, node->data, node->next->data);
+  else if (node->next)
+    printf("nil <- %d -> %d\n", node->data, node->next->data);
+  else
+    printf("%d <- %d -> nil\n", node->prev->data, node->data);
+}
+
+static void inspect(Node *node) {
+  if (!node) return;
+
+  printf("*******\n");
+  while (node) {
+    print(node);
+    node = node->next;
+  }
+  printf("*******\n");
+}
+
+static Node *initialize(int data) {
+  Node *node = malloc(sizeof(Node));
+  node->data = data;
+  node->next = NULL;
+  node->prev = NULL;
+  return node;
+}
+
+static Node *add(Node *head, int data) {
+  Node *tail;
+  Node *tmp = head;
+
+  while(tmp) {
+    if (!tmp->next)
+      break;
+    tmp = tmp->next;
+  }
+  tail = tmp;
+  tail->next = initialize(data);
+  tail->next->prev = tail;
+  return tail->next;
+}
+
+static Node *get(Node *from, int index) {
+  if (!from || index < 0) return NULL;
+
+  while(index > 0 && from){
+    from = from->next;
+    index--;
+  }
+  return from;
+}
+
+static int size(Node *head) {
+  int i = 0;
+  for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next) i++;
+  return i;
+}
+
+static void assign_next(Node *self, Node *other) {
+  if (self)
+    self->next = other;
+
+  if (other)
+    other->prev = self;
+}
+
+static void assign_prev(Node *self, Node *other) {
+  if (self)
+    self->prev = other;
+
+  if (other)
+    other->next = self;
+}
+
+static void swap(Node *x, Node *y) {
+  if (x == y) return;
+  if (!x || !y) return;
+  if (x->prev == y && y->next == x) return swap(y, x);
+
+  Node *xp = x->prev, *xn = x->next, *yp = y->prev, *yn = y->next;
+
+  // if adjacent
+  if (x->next == y && y->prev == x) {
+    assign_next(x, yn);
+    assign_prev(x, y);
+    assign_prev(y, xp);
+  } else {
+    assign_prev(x, yp);
+    assign_next(x, yn);
+    assign_prev(y, xp);
+    assign_next(y, xn);
+  }
+}
+
+static Node *reverse(Node *head) {
+  Node *tmp = NULL;
+  Node *current = head;
+
+  while (current != NULL) {
+    tmp = current->prev;
+    current->prev = current->next;
+    current->next = tmp;
+    current = current->prev;
+  }
+  return tmp ? tmp->prev : head;
+}
+
+Ensure(DoublyLinkedList, when_getting_head) {
+  Node *head = initialize(100);
+  assert_that(get(head, 0), is_equal_to(head));
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_getting_mid) {
+  Node *head = initialize(100);
+
+  Node *mid = add(head, 200);
+  add(head, 300);
+
+  assert_that(get(head, 1), is_equal_to(mid));
+  assert_that(get(head, 1)->data, is_equal_to(200));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_getting_tail) {
+  Node *head = initialize(100);
+
+  add(head, 200);
+  Node *tail = add(head, 300);
+
+  assert_that(get(head, 2), is_equal_to(tail));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_getting_from_empty_list) {
+  assert_that(get(NULL, 2), is_equal_to(NULL));
+}
+
+Ensure(DoublyLinkedList, when_getting_negative_index) {
+  Node *head = initialize(100);
+
+  assert_that(get(head, -1), is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_getting_index_out_of_range) {
+  Node *head = initialize(100);
+
+  assert_that(get(head, 1), is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_head_with_non_adjacent_node) {
+  Node *head = initialize(100);
+  Node *mid1 = add(head, 200);
+  Node *mid2 = add(head, 300);
+  Node *tail = add(head, 400);
+
+  swap(head, mid2);
+
+  assert_that(head->prev, is_equal_to(mid1));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(tail));
+
+  assert_that(mid1->prev, is_equal_to(mid2));
+  assert_that(mid1->data, is_equal_to(200));
+  assert_that(mid1->next, is_equal_to(head));
+
+  assert_that(mid2->prev, is_equal_to(NULL));
+  assert_that(mid2->data, is_equal_to(300));
+  assert_that(mid2->next, is_equal_to(mid1));
+
+  assert_that(tail->prev, is_equal_to(head));
+  assert_that(tail->data, is_equal_to(400));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_head_with_non_adjacent_node_inverted) {
+  Node *head = initialize(100);
+  Node *mid1 = add(head, 200);
+  Node *mid2 = add(head, 300);
+  Node *tail = add(head, 400);
+
+  swap(mid2, head);
+
+  assert_that(head->prev, is_equal_to(mid1));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(tail));
+
+  assert_that(mid1->prev, is_equal_to(mid2));
+  assert_that(mid1->data, is_equal_to(200));
+  assert_that(mid1->next, is_equal_to(head));
+
+  assert_that(mid2->prev, is_equal_to(NULL));
+  assert_that(mid2->data, is_equal_to(300));
+  assert_that(mid2->next, is_equal_to(mid1));
+
+  assert_that(tail->prev, is_equal_to(head));
+  assert_that(tail->data, is_equal_to(400));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_head_adjacent) {
+  Node *head = initialize(100);
+  Node *mid = add(head, 200);
+  Node *tail = add(head, 300);
+
+  swap(head, mid);
+
+  assert_that(head->prev, is_equal_to(mid));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(tail));
+
+  assert_that(mid->prev, is_equal_to(NULL));
+  assert_that(mid->data, is_equal_to(200));
+  assert_that(mid->next, is_equal_to(head));
+
+  assert_that(tail->prev, is_equal_to(head));
+  assert_that(tail->data, is_equal_to(300));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_head_adjacent_inverted) {
+  Node *head = initialize(100);
+  Node *mid = add(head, 200);
+  Node *tail = add(head, 300);
+
+  swap(mid, head);
+
+  assert_that(head->prev, is_equal_to(mid));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(tail));
+
+  assert_that(mid->prev, is_equal_to(NULL));
+  assert_that(mid->data, is_equal_to(200));
+  assert_that(mid->next, is_equal_to(head));
+
+  assert_that(tail->prev, is_equal_to(head));
+  assert_that(tail->data, is_equal_to(300));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_mid) {
+  Node *head = initialize(100);
+  Node *mid1 = add(head, 200);
+  Node *mid2 = add(head, 300);
+  Node *mid3 = add(head, 400);
+  Node *tail = add(head, 500);
+
+  swap(mid1, mid3);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(mid3));
+
+  assert_that(mid1->prev, is_equal_to(mid2));
+  assert_that(mid1->data, is_equal_to(200));
+  assert_that(mid1->next, is_equal_to(tail));
+
+  assert_that(mid2->prev, is_equal_to(mid3));
+  assert_that(mid2->data, is_equal_to(300));
+  assert_that(mid2->next, is_equal_to(mid1));
+
+  assert_that(mid3->prev, is_equal_to(head));
+  assert_that(mid3->data, is_equal_to(400));
+  assert_that(mid3->next, is_equal_to(mid2));
+
+  assert_that(tail->prev, is_equal_to(mid1));
+  assert_that(tail->data, is_equal_to(500));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_y_mid) {
+  Node *head = initialize(100);
+  Node *mid1 = add(head, 200);
+  Node *mid2 = add(head, 300);
+  Node *mid3 = add(head, 400);
+  Node *tail = add(head, 500);
+
+  swap(mid3, mid1);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(mid3));
+
+  assert_that(mid1->prev, is_equal_to(mid2));
+  assert_that(mid1->data, is_equal_to(200));
+  assert_that(mid1->next, is_equal_to(tail));
+
+  assert_that(mid2->prev, is_equal_to(mid3));
+  assert_that(mid2->data, is_equal_to(300));
+  assert_that(mid2->next, is_equal_to(mid1));
+
+  assert_that(mid3->prev, is_equal_to(head));
+  assert_that(mid3->data, is_equal_to(400));
+  assert_that(mid3->next, is_equal_to(mid2));
+
+  assert_that(tail->prev, is_equal_to(mid1));
+  assert_that(tail->data, is_equal_to(500));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_mid_adjacent) {
+  Node *head = initialize(100);
+  Node *mid1 = add(head, 200);
+  Node *mid2 = add(head, 300);
+  Node *tail = add(head, 400);
+
+  swap(mid1, mid2);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(mid2));
+
+  assert_that(mid1->prev, is_equal_to(mid2));
+  assert_that(mid1->data, is_equal_to(200));
+  assert_that(mid1->next, is_equal_to(tail));
+
+  assert_that(mid2->prev, is_equal_to(head));
+  assert_that(mid2->data, is_equal_to(300));
+  assert_that(mid2->next, is_equal_to(mid1));
+
+  assert_that(tail->prev, is_equal_to(mid1));
+  assert_that(tail->data, is_equal_to(400));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_mid_adjacent_y) {
+  Node *head = initialize(100);
+  Node *mid1 = add(head, 200);
+  Node *mid2 = add(head, 300);
+  Node *tail = add(head, 400);
+
+  swap(mid2, mid1);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(mid2));
+
+  assert_that(mid1->prev, is_equal_to(mid2));
+  assert_that(mid1->data, is_equal_to(200));
+  assert_that(mid1->next, is_equal_to(tail));
+
+  assert_that(mid2->prev, is_equal_to(head));
+  assert_that(mid2->data, is_equal_to(300));
+  assert_that(mid2->next, is_equal_to(mid1));
+
+  assert_that(tail->prev, is_equal_to(mid1));
+  assert_that(tail->data, is_equal_to(400));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_tail_adjacent) {
+  Node *head = initialize(100);
+  Node *mid = add(head, 200);
+  Node *tail = add(head, 300);
+
+  swap(mid, tail);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(tail));
+
+  assert_that(mid->prev, is_equal_to(tail));
+  assert_that(mid->data, is_equal_to(200));
+  assert_that(mid->next, is_equal_to(NULL));
+
+  assert_that(tail->prev, is_equal_to(head));
+  assert_that(tail->data, is_equal_to(300));
+  assert_that(tail->next, is_equal_to(mid));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_tail_adjacent_inverted) {
+  Node *head = initialize(100);
+  Node *mid = add(head, 200);
+  Node *tail = add(head, 300);
+
+  swap(tail, mid);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(tail));
+
+  assert_that(mid->prev, is_equal_to(tail));
+  assert_that(mid->data, is_equal_to(200));
+  assert_that(mid->next, is_equal_to(NULL));
+
+  assert_that(tail->prev, is_equal_to(head));
+  assert_that(tail->data, is_equal_to(300));
+  assert_that(tail->next, is_equal_to(mid));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_tail_with_non_adjacent_node) {
+  Node *head = initialize(100);
+  Node *mid1 = add(head, 200);
+  Node *mid2 = add(head, 300);
+  Node *tail = add(head, 400);
+
+  swap(mid1, tail);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(tail));
+
+  assert_that(mid1->prev, is_equal_to(mid2));
+  assert_that(mid1->data, is_equal_to(200));
+  assert_that(mid1->next, is_equal_to(NULL));
+
+  assert_that(mid2->prev, is_equal_to(tail));
+  assert_that(mid2->data, is_equal_to(300));
+  assert_that(mid2->next, is_equal_to(mid1));
+
+  assert_that(tail->prev, is_equal_to(head));
+  assert_that(tail->data, is_equal_to(400));
+  assert_that(tail->next, is_equal_to(mid2));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_tail_with_non_adjacent_node_inverted) {
+  Node *head = initialize(100);
+  Node *mid1 = add(head, 200);
+  Node *mid2 = add(head, 300);
+  Node *tail = add(head, 400);
+
+  swap(tail, mid1);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(tail));
+
+  assert_that(mid1->prev, is_equal_to(mid2));
+  assert_that(mid1->data, is_equal_to(200));
+  assert_that(mid1->next, is_equal_to(NULL));
+
+  assert_that(mid2->prev, is_equal_to(tail));
+  assert_that(mid2->data, is_equal_to(300));
+  assert_that(mid2->next, is_equal_to(mid1));
+
+  assert_that(tail->prev, is_equal_to(head));
+  assert_that(tail->data, is_equal_to(400));
+  assert_that(tail->next, is_equal_to(mid2));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_with_NULL) {
+  Node *head = initialize(100);
+  Node *mid = add(head, 200);
+  Node *tail = add(head, 300);
+
+  swap(mid, NULL);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+  assert_that(head->next, is_equal_to(mid));
+
+  assert_that(mid->prev, is_equal_to(head));
+  assert_that(mid->data, is_equal_to(200));
+  assert_that(mid->next, is_equal_to(tail));
+
+  assert_that(tail->prev, is_equal_to(mid));
+  assert_that(tail->data, is_equal_to(300));
+  assert_that(tail->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_swapping_self) {
+  Node *head = initialize(100);
+  Node *mid = add(head, 200);
+  Node *tail = add(head, 300);
+
+  swap(mid, mid);
+
+  assert_that(head->prev, is_equal_to(NULL));
+  assert_that(head->data, is_equal_to(100));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_reversing_a_short_list) {
+  Node *head = initialize(100);
+  Node *mid = add(head, 200);
+  Node *tail = add(head, 300);
+
+  Node *new_head = reverse(head);
+
+  assert_that(new_head->prev, is_equal_to(NULL));
+  assert_that(new_head, is_equal_to(tail));
+  assert_that(new_head->next, is_equal_to(mid));
+
+  assert_that(mid->prev, is_equal_to(tail));
+  assert_that(mid->next, is_equal_to(head));
+
+  assert_that(head->prev, is_equal_to(mid));
+  assert_that(head->next, is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(DoublyLinkedList, when_reversing_an_empty_list) {
+  Node *head = initialize(100);
+  Node *result = reverse(head);
+
+  assert_that(result, is_equal_to(head));
+
+  free(head);
+}
+
+TestSuite *swap_doubly_linked_list_tests() {
+  TestSuite *suite = create_test_suite();
+
+  add_test_with_context(suite, DoublyLinkedList, when_getting_head);
+  add_test_with_context(suite, DoublyLinkedList, when_getting_mid);
+  add_test_with_context(suite, DoublyLinkedList, when_getting_tail);
+  add_test_with_context(suite, DoublyLinkedList, when_getting_from_empty_list);
+  add_test_with_context(suite, DoublyLinkedList, when_getting_negative_index);
+  add_test_with_context(suite, DoublyLinkedList, when_getting_index_out_of_range);
+
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_head_adjacent);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_head_adjacent_inverted);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_head_with_non_adjacent_node);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_head_with_non_adjacent_node_inverted);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_mid);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_y_mid);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_mid_adjacent);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_mid_adjacent_y);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_adjacent);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_adjacent_inverted);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_with_non_adjacent_node);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_tail_with_non_adjacent_node_inverted);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_with_NULL);
+  add_test_with_context(suite, DoublyLinkedList, when_swapping_self);
+
+  add_test_with_context(suite, DoublyLinkedList, when_reversing_a_short_list);
+  add_test_with_context(suite, DoublyLinkedList, when_reversing_an_empty_list);
+
+  return suite;
+}
diff --git a/src/01/swap_singly_linked_list_test.c b/src/01/swap_singly_linked_list_test.c
new file mode 100644
index 0000000..aedd015
--- /dev/null
+++ b/src/01/swap_singly_linked_list_test.c
@@ -0,0 +1,278 @@
+#include <cgreen/cgreen.h>
+/*
+Swap two adjacent elements in a list by adjusting
+only the links (and not the data) using a:
+* singly-linked list
+* doubly-linked list
+*/
+
+Describe(SinglyLinkedList);
+BeforeEach(SinglyLinkedList){ }
+AfterEach(SinglyLinkedList){ }
+
+struct node {
+  int data;
+  struct node *next;
+};
+
+typedef struct node Node;
+
+static void inspect(Node *node) {
+  if (!node) return;
+
+  printf("*******\n");
+  while (node) {
+    printf("\t%d\n", node->data);
+    node = node->next;
+  }
+  printf("*******\n");
+}
+
+Node *initialize(int data) {
+  Node *node = malloc(sizeof(Node));
+  node->data = data;
+  node->next = NULL;
+  return node;
+}
+
+Node *add(Node *head, int data) {
+  Node *tail;
+  Node *tmp = head;
+
+  while(tmp) {
+    if (!tmp->next)
+      break;
+    tmp = tmp->next;
+  }
+  tail = tmp;
+  tail->next = initialize(data);
+  return tail->next;
+}
+
+Node *get(Node *from, int index) {
+  if (!from || index < 0) return NULL;
+
+  while(index > 0 && from){
+    from = from->next;
+    index--;
+  }
+  return from;
+}
+
+static int size(Node *head) {
+  int i = 0;
+  for (Node *tmp = head; tmp && tmp != NULL; tmp = tmp->next) i++;
+  return i;
+}
+
+void swap(Node **head, int x, int y) {
+  int count = size(*head);
+
+  if (x == y) return;
+  if (x >= count) return;
+  if (y >= count) return;
+
+  Node *xp = get(*head, x - 1);
+  Node *yp = get(*head, y - 1);
+  Node *xc = get(*head, x);
+  Node *yc = get(*head, y);
+
+  if (x == 0)
+    *head = yc;
+  else
+    xp->next = yc;
+
+  if (y == 0)
+    *head = xc;
+  else
+    yp->next = xc;
+
+  Node *tmp = yc->next;
+  yc->next = xc->next;
+  xc->next = tmp;
+}
+
+Ensure(SinglyLinkedList, when_getting_head) {
+  Node *head = initialize(100);
+  assert_that(get(head, 0), is_equal_to(head));
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_getting_mid) {
+  Node *head = initialize(100);
+
+  Node *mid = add(head, 200);
+  add(head, 300);
+
+  assert_that(get(head, 1), is_equal_to(mid));
+  assert_that(get(head, 1)->data, is_equal_to(200));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_getting_tail) {
+  Node *head = initialize(100);
+
+  add(head, 200);
+  Node *tail = add(head, 300);
+
+  assert_that(get(head, 2), is_equal_to(tail));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_getting_from_empty_list) {
+  assert_that(get(NULL, 2), is_equal_to(NULL));
+}
+
+Ensure(SinglyLinkedList, when_getting_negative_index) {
+  Node *head = initialize(100);
+
+  assert_that(get(head, -1), is_equal_to(NULL));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_getting_index_out_of_range) {
+  Node *head = initialize(100);
+
+  assert_that(get(head, 1), is_equal_to(NULL));
+
+  free(head);
+}
+
+
+Ensure(SinglyLinkedList, when_swapping_head) {
+  Node *head = initialize(100);
+
+  add(head, 200);
+  add(head, 300);
+
+  swap(&head, 0, 1);
+
+  assert_that(get(head, 0), is_non_null);
+  assert_that(get(head, 0)->data, is_equal_to(200));
+  assert_that(get(head, 1), is_non_null);
+  assert_that(get(head, 1)->data, is_equal_to(100));
+  assert_that(get(head, 2), is_non_null);
+  assert_that(get(head, 2)->data, is_equal_to(300));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_swapping_y_head) {
+  Node *head = initialize(100);
+
+  add(head, 200);
+  add(head, 300);
+
+  swap(&head, 1, 0);
+
+  assert_that(get(head, 0), is_non_null);
+  assert_that(get(head, 0)->data, is_equal_to(200));
+  assert_that(get(head, 1), is_non_null);
+  assert_that(get(head, 1)->data, is_equal_to(100));
+  assert_that(get(head, 2), is_non_null);
+  assert_that(get(head, 2)->data, is_equal_to(300));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_swapping_mid) {
+  Node *head = initialize(100);
+
+  add(head, 200);
+  add(head, 300);
+  add(head, 400);
+
+  swap(&head, 1, 2);
+
+  assert_that(get(head, 0)->data, is_equal_to(100));
+  assert_that(get(head, 1)->data, is_equal_to(300));
+  assert_that(get(head, 2)->data, is_equal_to(200));
+  assert_that(get(head, 3)->data, is_equal_to(400));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_swapping_y_mid) {
+  Node *head = initialize(100);
+
+  add(head, 200);
+  add(head, 300);
+  add(head, 400);
+
+  swap(&head, 2, 1);
+
+  assert_that(get(head, 0)->data, is_equal_to(100));
+  assert_that(get(head, 1)->data, is_equal_to(300));
+  assert_that(get(head, 2)->data, is_equal_to(200));
+  assert_that(get(head, 3)->data, is_equal_to(400));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_swapping_tail) {
+  Node *head = initialize(100);
+
+  add(head, 200);
+  add(head, 300);
+
+  swap(&head, 1, 2);
+
+  assert_that(get(head, 0), is_non_null);
+  assert_that(get(head, 0)->data, is_equal_to(100));
+  assert_that(get(head, 1), is_non_null);
+  assert_that(get(head, 1)->data, is_equal_to(300));
+  assert_that(get(head, 2), is_non_null);
+  assert_that(get(head, 2)->data, is_equal_to(200));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_swapping_index_out_of_range) {
+  Node *head = initialize(100);
+
+  add(head, 200);
+  add(head, 300);
+
+  swap(&head, 1, 3);
+
+  assert_that(get(head, 0)->data, is_equal_to(100));
+  assert_that(get(head, 1)->data, is_equal_to(200));
+  assert_that(get(head, 2)->data, is_equal_to(300));
+
+  free(head);
+}
+
+Ensure(SinglyLinkedList, when_swapping_self) {
+  Node *head = initialize(100);
+
+  swap(&head, 0, 0);
+
+  assert_that(get(head, 0), is_non_null);
+  assert_that(get(head, 0)->data, is_equal_to(100));
+
+  free(head);
+}
+
+TestSuite *swap_singly_linked_list_tests() {
+  TestSuite *suite = create_test_suite();
+
+  add_test_with_context(suite, SinglyLinkedList, when_getting_head);
+  add_test_with_context(suite, SinglyLinkedList, when_getting_mid);
+  add_test_with_context(suite, SinglyLinkedList, when_getting_tail);
+  add_test_with_context(suite, SinglyLinkedList, when_getting_from_empty_list);
+  add_test_with_context(suite, SinglyLinkedList, when_getting_negative_index);
+  add_test_with_context(suite, SinglyLinkedList, when_getting_index_out_of_range);
+
+  add_test_with_context(suite, SinglyLinkedList, when_swapping_head);
+  add_test_with_context(suite, SinglyLinkedList, when_swapping_y_head);
+  add_test_with_context(suite, SinglyLinkedList, when_swapping_mid);
+  add_test_with_context(suite, SinglyLinkedList, when_swapping_y_mid);
+  add_test_with_context(suite, SinglyLinkedList, when_swapping_tail);
+  add_test_with_context(suite, SinglyLinkedList, when_swapping_index_out_of_range);
+  add_test_with_context(suite, SinglyLinkedList, when_swapping_self);
+
+  return suite;
+}