erste Version einer einfach verketteten Liste mit tail-Wächter

3 files changed, 135 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
index d6748cb..cc84e2c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,4 @@
+.tags
 tags
 allocator
 avl
@@ -6,6 +7,7 @@ dlist
 hashtab
 heap
 list
+list-tail-node
 queue
 quicksort
 rb
diff --git a/list-tail-node.c b/list-tail-node.c
new file mode 100644
index 0000000..d187241
--- /dev/null
+++ b/list-tail-node.c
@@ -0,0 +1,129 @@
+/* Standard C */
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/* Project */
+#include "util.h"
+
+typedef int T;
+
+struct list_node {
+        struct list_node *next;
+        T                 data;
+};
+
+struct list {
+        struct list_node *head, *tail;
+};
+
+void
+list_init(struct list *list)
+{
+        list->head = NULL;
+}
+
+static struct list_node *
+create_node(struct list_node *next, T data)
+{
+        struct list_node *node = malloc(sizeof *node);
+
+        if ( node != NULL ) {
+                node->next = next;
+                node->data = data;
+        }
+        return node;
+}
+
+void
+list_push_back(struct list *list, T data)
+{
+        struct list_node *node = create_node(NULL, data);
+
+        if ( node != NULL ) {
+                if ( list->head == NULL ) {
+                        list->head = node;
+                }
+                else {
+                        list->tail->next = node;
+                }
+                list->tail = node;
+        }
+        else {
+                ERROR("out of memory");
+        }
+}
+
+void
+list_push_front(struct list *list, T data)
+{
+        struct list_node *node = create_node(list->head, data);
+
+        if ( node != NULL ) {
+                if ( list->head == NULL ) { // Einfügen in eine leere Liste?
+                        list->tail = node;
+                }
+                list->head = node;
+        }
+        else {
+                ERROR("out of memory");
+        }
+}
+
+bool
+list_pop_front(struct list *list, T *data)
+{
+        if ( list->head != NULL ) {
+                struct list_node *next = list->head->next;
+                *data                  = list->head->data;
+                free(list->head);
+                list->head = next;
+
+                return true;
+        }
+        else
+                return false;
+}
+
+bool
+list_empty(struct list *list)
+{
+        return list->head == NULL;
+}
+
+void
+list_free(struct list *list)
+{
+        struct list_node *item, *next;
+
+        for ( item = list->head; item; item = next ) {
+                next = item->next;
+                free(item);
+        }
+}
+
+int
+main()
+{
+        struct list list[1];
+
+        list_init(list);
+
+        for ( int i = 0; i != 10; ++i )
+                list_push_front(list, -i);
+
+        for ( int i = 0; i != 10; ++i )
+                list_push_back(list, i);
+
+        while ( !list_empty(list) ) {
+                int i;
+                if ( list_pop_front(list, &i) )
+                        printf("%d\n", i);
+                else
+                        ERROR("this shouldn't happen!");
+        }
+
+        list_free(list);
+
+        return EXIT_SUCCESS;
+}
diff --git a/makefile b/makefile
index 9748166..0237f02 100644
--- a/makefile
+++ b/makefile
@@ -2,11 +2,14 @@
 
 CFLAGS=-Wall -Werror -Wextra -Wno-unused-function -Wsign-conversion -pedantic -std=c99 -g
 
-all: list dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque
+all: list list-tail-node dlist stack stack2 queue ringbuff hashtab tree avl heap quicksort allocator rb deque
 
 list: list.c util.h
         cc $(CFLAGS) $< -o $@
 
+list-tail-node: list-tail-node.c util.h
+        cc $(CFLAGS) $< -o $@
+
 dlist: dlist.c util.h
         cc $(CFLAGS) $< -o $@