submission lab0lab0main

3 files changed, 159 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..0ac8095
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,21 @@
+SRC = linked_list.c
+OBJ = $(SRC:.c=.o)
+
+all: linked_list
+
+.c.o:
+	$(CC) -c $<
+
+linked_list: $(OBJ)
+	$(CC) -o $@ $(OBJ)
+
+run: linked_list
+	./linked_list
+
+valgrind: linked_list
+	valgrind --tool=memcheck --leak-check=yes ./linked_list
+
+clean:
+	rm -f linked_list $(OBJ)
+
+.PHONY: all run valgrind clean
diff --git a/linked_list.c b/linked_list.c
new file mode 100644
index 0000000..0a730d6
--- /dev/null
+++ b/linked_list.c
@@ -0,0 +1,116 @@
+#include "linked_list.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+
+void append(struct list_item *first, int x) {
+    // find the last element
+    struct list_item *current = first;
+    while (current->next) {
+        current = current->next;
+    }
+    // insert after
+    struct list_item *new = malloc(sizeof(struct list_item));
+    new->value = x;
+    new->next = NULL;
+    current->next = new;
+}
+
+void prepend(struct list_item *first, int x) {
+    // the first element is a head-element so we insert after it
+    struct list_item *new = malloc(sizeof(struct list_item));
+    new->value = x;
+    new->next = first->next;
+    first->next = new;
+}
+
+void print(struct list_item *first) {
+    // skip printing the head
+    struct list_item *current = first->next;
+    while (current) {
+        printf("%d ", current->value);
+        current = current->next;
+    }
+    printf("\n");
+}
+
+void input_sorted(struct list_item *first, int x) {
+    struct list_item *current = first;
+    // find the first element in the list larger than x
+    // (we check current->next since we want to insert after current)
+    // if we reach the end (!current->next) we insert after current
+    while (current->next && current->next->value <= x) {
+        current = current->next;
+    }
+    struct list_item *new = malloc(sizeof(struct list_item));
+    new->value = x;
+    new->next = current->next;
+    current->next = new;
+}
+
+void clear(struct list_item *first) {
+    // don't clear head
+    struct list_item *current = first->next;
+    if (!current) {
+        // empty list, don't free anything
+        return;
+    }
+    struct list_item *next;
+    while (current) {
+        next = current->next;
+        free(current);
+        current = next;
+    }
+    first->next = NULL;
+}
+
+int main(int argc, char **argv) {
+    // head element
+    struct list_item root;
+    root.value = -1;
+    root.next = NULL;
+
+    // empty clears
+    clear(&root);
+    clear(&root);
+    print(&root);
+
+    // short append
+    append(&root, 1);
+    append(&root, 2);
+    append(&root, 3);
+    print(&root);
+    clear(&root);
+
+    // short prepend
+    prepend(&root, 1);
+    prepend(&root, 2);
+    prepend(&root, 3);
+    print(&root);
+    clear(&root);
+
+    // mix append prepend
+    append(&root, 1);
+    append(&root, 2);
+    prepend(&root, 4);
+    append(&root, 3);
+    prepend(&root, 5);
+    print(&root);
+    clear(&root);
+
+    //// input_sorted
+    append(&root, 10);
+    append(&root, 20);
+    append(&root, 30);
+    print(&root);
+    // in the middle
+    input_sorted(&root, 15);
+    input_sorted(&root, 25);
+    // at the back (new largest element)
+    input_sorted(&root, 35);
+    // at the front
+    input_sorted(&root, 5);
+    print(&root);
+    clear(&root);
+    print(&root);
+}
diff --git a/linked_list.h b/linked_list.h
new file mode 100644
index 0000000..aefdf29
--- /dev/null
+++ b/linked_list.h
@@ -0,0 +1,22 @@
+#pragma once
+
+struct list_item {
+    int value;
+    struct list_item *next;
+};
+
+/* Put x at the end of the list. */
+void append(struct list_item *first, int x);
+
+/* Put x at the beginning of the list. */
+void prepend(struct list_item *first, int x);
+
+/* Print att elements in the list. */
+void print(struct list_item *first);
+
+/* Find the first element in the list larger than x and input x right before
+ * that element. */
+void input_sorted(struct list_item *first, int x);
+
+/* Free everything dynamically located. */
+void clear(struct list_item *first);