{"id":233,"date":"2016-03-30T22:57:22","date_gmt":"2016-03-30T21:57:22","guid":{"rendered":"https:\/\/solidt.eu\/blog\/?p=233"},"modified":"2022-01-17T11:02:48","modified_gmt":"2022-01-17T10:02:48","slug":"a-linked-list-in-c","status":"publish","type":"post","link":"https:\/\/solidt.eu\/site\/a-linked-list-in-c\/","title":{"rendered":"A Linked List in C"},"content":{"rendered":"\n\n\n<div style=\"height: 250px; position:relative; margin-bottom: 50px;\" class=\"wp-block-simple-code-block-ace\"><pre class=\"wp-block-simple-code-block-ace\" style=\"position:absolute;top:0;right:0;bottom:0;left:0\" data-mode=\"c_cpp\" data-theme=\"monokai\" data-fontsize=\"14\" data-lines=\"Infinity\" data-showlines=\"true\" data-copy=\"false\">typedef struct node\n{\n    void* data;\n    struct node* prev;\n    struct node* next;\n} node_t;\n\n\ntypedef struct list\n{\n    struct node* first;\n    struct node* last;\n    long length;\n} list_t;\n\n\n\/\/ Create and free list\nlist_t* list_new();\nvoid list_free(list_t *l);\n\n\/\/ Create and free nodes\nnode_t* node_new(void* data);\n\/\/ WARNING: free does free the node data by default\n\/\/ to prevent freeing of the data set data to 0 before removing from the list\nvoid node_free(node_t* n);\n\n\/\/ List operations\nvoid list_insert(list_t *l, node_t* n);\nvoid list_append(list_t *l, node_t* n);\nvoid list_remove(list_t *l, node_t *n);\nvoid list_clear(list_t *l);\n\n\n\/\/ Default implementation of specal list modes\n\n\/\/ Queue\nvoid list_queue_push(list_t *l, void* data);\nvoid* list_queue_pop(list_t *l);\n\n\/\/ Stack\nvoid list_stack_push(list_t *l, void* data);\nvoid* list_stack_pop(list_t *l);\n\n#include \"linkedlist.h\"\n\n#include \n\nlist_t* list_new()\n{\n    list_t *l = malloc(sizeof(list_t));\n    l->first = 0;\n    l->last = 0;\n    l->length = 0;\n    return l;\n}\n\nnode_t* node_new(void* data)\n{\n    node_t *n = malloc(sizeof(node_t));\n    n->prev = 0;\n    n->next = 0;\n    n->data = data;\n    return n;\n}\n\nvoid node_free(node_t* n)\n{\n    free(n->data);\n    free(n);\n}\n\nvoid list_insert(list_t *l, node_t* n)\n{\n    if (l->first != 0)\n    {\n        n->next = l->first;\n        l->first->prev = n;\n        l->first = n;\n    }\n    else\n    { \/\/ assuming list is empty\n        l->first = n;\n        l->last = n;\n    }\n\n    l->length += 1;\n}\n\nvoid list_append(list_t *l, node_t* n)\n{\n    if (l->last != 0)\n    {\n        n->prev = l->last;\n        l->last->next = n;\n        l->last = n;\n    }\n    else\n    { \/\/ assuming list is empty\n        l->first = n;\n        l->last = n;\n    }\n\n    l->length += 1;\n}\n\nvoid list_remove(list_t *l, node_t *n)\n{\n    if (n->prev != 0 &amp;&amp; n->next != 0)\n    {\n        \/\/ We are dealing with a middle node\n        n->prev->next = n->next;\n        n->next->prev = n->prev;\n    }\n    else if (n->prev != 0 &amp;&amp; n->next == 0)\n    {\n        \/\/ We are dealing with a last node\n        n->prev->next = 0;\n        l->last = n->prev;\n    }\n    else if (n->prev == 0 &amp;&amp; n->next != 0)\n    {\n        \/\/ We are dealing with a first node\n        n->next->prev = 0;\n        l->first = n->next;\n    }\n    else if (n->prev == 0 &amp;&amp; n->next == 0)\n    {\n        \/\/ We are dealing with a single node\n        l->first = 0;\n        l->last = 0;\n    }\n\n    l->length -= 1;\n}\n\nvoid list_clear(list_t *l)\n{\n    while(l->first != 0)\n    {\n        list_remove(l, l->first);\n    }\n}\n\nvoid list_free(list_t *l)\n{\n    if (l->length > 0)\n    {\n        list_clear(l);\n    }\n    free(l);\n}\n\n\/\/ Queue (FIFO)\nvoid list_queue_push(list_t *l, void* data)\n{\n    list_append(l, node_new(data));\n}\n\nvoid* list_queue_pop(list_t *l)\n{\n    void* data = 0;\n    if (l->first != 0)\n    {\n        data = l->first->data;\n        l->first->data = 0;\n        list_remove(l, l->first);\n    }\n    return data;\n}\n\n\/\/ Stack (FILO)\nvoid list_stack_push(list_t *l, void* data)\n{\n    list_append(l, node_new(data));\n}\n\nvoid* list_stack_pop(list_t *l)\n{\n    void* data = 0;\n    if (l->last != 0)\n    {\n        data = l->last->data;\n        l->last->data = 0;\n        list_remove(l, l->last);\n    }\n    return data;\n}\n\n#include \n#include \n\n#include \"linkedlist.h\"\n\n\nvoid list_test1()\n{\n    printf(\"start\\n\");\n\n    list_t *l;\n\n    l = list_new();\n\n    printf(\"list count: %ld\\n\", l->length);\n\n    list_append(l, node_new(\"Hello 1\"));\n    list_append(l, node_new(\"Hello 2\"));\n    list_append(l, node_new(\"Hello 3\"));\n    list_append(l, node_new(\"Hello 4\"));\n    list_append(l, node_new(\"Hello 5\"));\n\n    printf(\"list count: %ld\\n\", l->length);\n\n    list_insert(l, node_new(\"Hello 1\"));\n    list_insert(l, node_new(\"Hello 2\"));\n    list_insert(l, node_new(\"Hello 3\"));\n    list_insert(l, node_new(\"Hello 4\"));\n    list_insert(l, node_new(\"Hello 5\"));\n\n    printf(\"list count: %ld\\n\", l->length);\n\n    node_t *n = l->first;\n    while(n != 0)\n    {\n        printf(\"item: %s\\n\", (char*) n->data);\n        n = n->next;\n    }\n\n    list_remove(l, l->last);\n\n    printf(\"list count: %ld\\n\", l->length);\n\n    list_clear(l);\n\n    printf(\"list count: %ld\\n\", l->length);\n\n    list_free(l);\n\n    printf(\"end\\n\");\n}\n\nvoid list_test2()\n{\n    printf(\"start\\n\");\n\n    list_t *l;\n\n    l = list_new();\n\n    list_queue_push(l, \"Hello 1\");\n    list_queue_push(l, \"Hello 2\");\n    list_queue_push(l, \"Hello 3\");\n    list_queue_push(l, \"Hello 4\");\n    list_queue_push(l, \"Hello 5\");\n    printf(\"list count: %ld\\n\", l->length);\n\n    char *data = 0;\n\n    data = (char*)list_queue_pop(l);\n    \/\/printf(\"list count: %ld\\n\", l->length);\n    while(data != 0)\n    {\n        printf(\"item: %s\\n\", data);\n        data = (char*)list_queue_pop(l);\n        \/\/printf(\"list count: %ld\\n\", l->length);\n    }\n\n    printf(\"list count: %ld\\n\", l->length);\n    list_clear(l);\n\n    printf(\"\\n\");\n\n    list_stack_push(l, \"Hello 1\");\n    list_stack_push(l, \"Hello 2\");\n    list_stack_push(l, \"Hello 3\");\n    list_stack_push(l, \"Hello 4\");\n    list_stack_push(l, \"Hello 5\");\n    printf(\"list count: %ld\\n\", l->length);\n\n    data = (char*)list_stack_pop(l);\n    \/\/printf(\"list count: %ld\\n\", l->length);\n    while(data != 0)\n    {\n        printf(\"item: %s\\n\", data);\n        data = (char*)list_stack_pop(l);\n        \/\/printf(\"list count: %ld\\n\", l->length);\n    }\n\n    printf(\"list count: %ld\\n\", l->length);\n\n    list_free(l);\n\n    printf(\"end\\n\");\n}\n\nvoid list_test3()\n{\n    list_t *l = list_new();\n\n    int i = 0;\n    for(i=0; i&lt;1000000; i++)\n    {\n        int *d = malloc(sizeof(int));\n        *d = i;\n        list_stack_push(l, d);\n    }\n\n    int *data = (int*)list_stack_pop(l);\n\n    while(data != 0)\n    {\n        printf(\"%i\\n\", *data);\n        data = (int*)list_stack_pop(l);\n    }\n\n    list_free(l);\n}\n\nint main(int argc, char *argv[])\n{\n    list_test1();\n\n    list_test2();\n\n    \/\/list_test3();\n\n    return 0;\n}\n<\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[8],"tags":[],"class_list":["post-233","post","type-post","status-publish","format-standard","hentry","category-other-scripts"],"_links":{"self":[{"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/posts\/233","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/comments?post=233"}],"version-history":[{"count":2,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/posts\/233\/revisions"}],"predecessor-version":[{"id":5936,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/posts\/233\/revisions\/5936"}],"wp:attachment":[{"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/media?parent=233"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/categories?post=233"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solidt.eu\/site\/wp-json\/wp\/v2\/tags?post=233"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}