add

1 files changed, 138 insertions, 0 deletions

diff --git a/data_structures/chapter_3/linked_list.c b/data_structures/chapter_3/linked_list.c
new file mode 100644
index 0000000..920be0d
--- /dev/null
+++ b/data_structures/chapter_3/linked_list.c
@@ -0,0 +1,138 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "linked_list.h"
+
+struct node
+{
+    elem data;
+    position next;
+};
+
+int is_empty(list header)
+{
+    return header->next == NULL;
+}
+
+int is_last(position p, list header)
+{
+    return p->next == NULL;
+}
+
+position find(elem x, list header)
+{
+    position p;
+    p = header->next;
+
+    for(; p != NULL; p = p->next) {
+        if(p->data == x) return p;
+    }
+
+    return NULL;
+}
+
+void delete(elem x, list header)
+{
+    position tmp;
+    position pre;
+
+    pre = find_previous(x, header);
+
+    if(!is_last(pre, header)) {
+        tmp = pre->next;
+        pre->next = pre->next->next;
+        free(tmp);
+    }
+
+}
+
+position find_previous(elem x, list header)
+{
+    position p;
+
+    p = header;
+    while(p->next != NULL && p->next->data != x)
+        p = p->next;
+
+    return p;
+}
+
+void insert(elem x, list header, position p)
+{
+    position tmp;
+    
+    tmp = malloc(sizeof(struct node));
+    
+    if(tmp == NULL)
+       printf("Out of space!\n"); 
+
+    tmp->data = x;
+    tmp->next = p->next;
+    p->next = tmp;
+}
+
+void delete_list(list header)
+{
+    position p, tmp;
+
+    p = header->next;
+    header->next = NULL;
+
+    while(p != NULL) {
+        tmp = p;
+        p = p->next;
+        free(tmp);
+    }
+}
+
+void print_list(list header)
+{
+    position p;
+
+    if(is_empty(header))
+       printf("empty list! \n");
+
+    p = header->next;
+    for(; p != NULL; p = p->next) 
+        printf("%d->", p->data);
+    printf("\n");
+}
+
+int test()
+{
+    position p1, p2, p3;
+    list l1, l2, l3, l4;
+    l1 = malloc(sizeof(struct node));
+    l1->next == NULL;
+
+    print_list(l1);
+
+    /* test insert foo */
+    insert(5, l1, l1);
+    insert(4, l1, l1);
+    insert(3, l1, l1);
+    insert(2, l1, l1);
+    insert(1, l1, l1);
+    print_list(l1);
+
+
+    /* test find foo */
+    p1 = find(2, l1);
+    printf("%d\n", p1->next->data);
+
+    /* test delete foo */
+    delete(3, l1);
+    delete(5, l1);
+    delete(1, l1);
+    print_list(l1);
+
+    /* test delete_list foo */
+    delete_list(l1);
+    print_list(l1);
+}
+
+int main()
+{
+    test();
+    return 0;
+}