Commit 6ccdccb

mo khan <mo.khan@gmail.com>
2020-07-05 00:22:24
Reverse a doubly linked list
master
1 parent 1460895
Changed files (7)
src
01
02b
README.md
05
doubly_linked_list.c
doubly_linked_list.h
doubly_linked_list_test.c
main.c
Makefile
README.md
src/01/02b/README.md
@@ -8,6 +8,7 @@ Student ID: 3431709
 Swap two adjacent elements in a list by adjusting only the links (and not the data) using doubly-linked list.
 
 ## Description of the Code
+
 ## Errors and Warnings
 
 ```bash
src/01/05/doubly_linked_list.c
@@ -0,0 +1,93 @@
+#include "doubly_linked_list.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+Node *initialize(int data) {
+  Node *node = malloc(sizeof(Node));
+  node->data = data;
+  node->next = NULL;
+  node->prev = 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);
+  tail->next->prev = tail;
+  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;
+}
+
+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;
+}
+
+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;
+}
+
+static void print(Node *node) {
+  if (node->prev && node->next)
+    printf("(%d<%d>%d)", node->prev->data, node->data, node->next->data);
+  else if (node->next)
+    printf("(nil<%d>%d)", node->data, node->next->data);
+  else
+    printf("(%d<%d>nil)", node->prev->data, node->data);
+}
+
+void inspect(Node *node) {
+  if (!node) return;
+
+  printf("[ ");
+  while (node) {
+    print(node);
+    printf(" ");
+    node = node->next;
+  }
+  printf("]\n");
+}
+
src/01/05/doubly_linked_list.h
@@ -0,0 +1,13 @@
+struct node {
+  int data;
+  struct node *next;
+  struct node *prev;
+};
+
+typedef struct node Node;
+
+Node *initialize(int data);
+Node *add(Node *head, int data);
+Node *get(Node *from, int index);
+Node *reverse(Node *head);
+void inspect(Node *node);
src/01/05/doubly_linked_list_test.c
@@ -0,0 +1,448 @@
+#include <cgreen/cgreen.h>
+#include "doubly_linked_list.h"
+
+Describe(DoublyLinkedList);
+BeforeEach(DoublyLinkedList){ }
+AfterEach(DoublyLinkedList){ }
+
+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 *reverse_doubly_linked_list_tests() {
+  TestSuite *suite = create_test_suite();
+
+  add_test_with_context(suite, DoublyLinkedList, when_reversing_a_short_list);
+  add_test_with_context(suite, DoublyLinkedList, when_reversing_an_empty_list);
+
+  return suite;
+}
+
+int main(int argc, char **argv) {
+  TestSuite *suite = create_test_suite();
+  add_suite(suite, reverse_doubly_linked_list_tests());
+  return run_test_suite(suite, create_text_reporter());
+}
src/01/05/main.c
@@ -0,0 +1,34 @@
+#include "doubly_linked_list.h"
+#include <stdio.h>
+#include <stdlib.h>
+
+int next(void) {
+  return rand() % 100;
+}
+
+int main(int argc, char *argv[])
+{
+  printf("=== COMP-272 - Assignment 1 - Question 2b ===\n");
+  Node *head = initialize(next());
+  Node *new_head = NULL;
+
+  for (int i = 0; i < 9; ++i)
+    add(head, next());
+
+  printf("\t");
+  inspect(head);
+
+  new_head = get(head, 1);
+  swap(head, new_head);
+  head = new_head;
+  printf("swap: 0,1\n\t");
+  inspect(head);
+
+  for (int i = 2; i < 10; i+=2) {
+    swap(get(head, i), get(head, i + 1));
+    printf("swap: %d,%d\n\t", i, i + 1);
+    inspect(head);
+  }
+
+  return 0;
+}
src/01/05/Makefile
@@ -0,0 +1,37 @@
+#!/usr/bin/make -f
+SHELL=/bin/sh
+
+CC=clang
+TEST_LIBS = -lcgreen
+
+BUILDDIR := build
+OBJS := $(addprefix $(BUILDDIR)/,doubly_linked_list.o)
+TEST_OBJS := $(addprefix $(BUILDDIR)/,doubly_linked_list_test.o)
+
+$(BUILDDIR)/%.o : %.c
+	$(COMPILE.c) $(OUTPUT_OPTION) $<
+
+.PHONY: all
+all: $(OBJS) $(BUILDDIR)/main.o
+	$(CC) $(OBJS) $(BUILDDIR)/main.o -o $(BUILDDIR)/program
+
+.PHONY: test
+test: $(OBJS) $(TEST_OBJS)
+	$(CC) $(OBJS) $(TEST_OBJS) $(TEST_LIBS) -o $(BUILDDIR)/test
+
+$(OBJS): | $(BUILDDIR)
+
+$(TEST_OBJS): | $(BUILDDIR)
+
+$(BUILDDIR):
+	mkdir $(BUILDDIR)
+
+.PHONY: clean
+clean:
+	rm -fr build
+
+run : all
+	./build/program
+
+run_test : test
+	cgreen-runner -c -v $(BUILDDIR)/test
src/01/05/README.md
@@ -0,0 +1,13 @@
+# Learning Profile for Assignment #1 - Question #05 - Computer Science 272: Data Structures and Algorithms
+
+Name: Mo Khan
+Student ID: 3431709
+
+## Problem Statement
+
+Write a method, reverse(), that reverses the order of elements in a DLList.
+
+## Description of the Code
+## Errors and Warnings
+## Sample Input and Output
+## Discussion