{"id":2905,"date":"2018-01-13T00:01:49","date_gmt":"2018-01-13T08:01:49","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=2905"},"modified":"2018-01-20T08:39:54","modified_gmt":"2018-01-20T16:39:54","slug":"building-a-double-linked-list","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=2905","title":{"rendered":"Building a Double-Linked List"},"content":{"rendered":"

Similar to a linked list, a double-linked list requires that you work on both the current item in the list as well as the the previous item. You just have one additional structure member to update, which is the pointer from the current item to the previous structure.
\n
\nIn a linked list, two pointer variables are used to create the list. They reference the current and newly-created structures in the list, so I use the variable names current<\/code> and created<\/code> (formerly “new”). After allocating the created<\/code> structure, you update the current<\/code> structure’s member referencing that new structure, *next<\/code>, as in:<\/p>\n

current->next=created;<\/code><\/p>\n

So the current<\/code> structure’s next<\/code> member helps find the next structure in the list, created<\/code>.<\/p>\n

In a double-linked list you must also set the created<\/code> structure’s *prev<\/code> member to reference the previous structure. That structure’s location is saved in the current<\/code> pointer:<\/p>\n

created->prev=current;<\/code><\/p>\n

That’s really all the overhead you need, though the sequence of events is crucial.<\/p>\n

The following code uses the greek<\/code> structure introduced in last week’s Lesson<\/a>. The double-linked list created contains the names of the first ten letters of the Greek alphabet.<\/p>\n

\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n\r\n#define ITEMS 10\r\n\r\nint main()\r\n{\r\n    struct greek {\r\n        struct greek *prev;\r\n        char *letter;\r\n        struct greek *next;\r\n    };\r\n    char *ab[] = {\r\n        \"alpha\", \"beta\", \"gamma\", \"delta\", \"epsilon\",\r\n        \"zeta\", \"eta\", \"theta\", \"iota\", \"kappa\"\r\n    };\r\n    struct greek *first,*last,*current,*created;\r\n    int x;\r\n\r\n    \/* build the double-linked list *\/<\/span>\r\n    for(x=0;x<=<ITEMS;x++)\r\n    {\r\n        created = (struct greek *)malloc(sizeof(struct greek));\r\n        if( created==NULL )\r\n        {\r\n            puts(\"Unable to allocate memory\");\r\n            exit(1);\r\n        }\r\n        \/* first item in the list is special *\/\r\n        if( x==0 )\r\n        {\r\n            created->prev = NULL;\r\n            first = created;\r\n        }\r\n        else\r\n        {\r\n            created->prev = current;\r\n            current->next = created;\r\n        }\r\n        created->letter = ab[x];\r\n        created->next = NULL;\r\n        current = created;\r\n    }\r\n    last = current;\r\n\r\n    \/* display list front-to-back *\/<\/span>\r\n    current = first;\r\n    while(current)\r\n    {\r\n        printf(\"%s\\n\",current->letter);\r\n        current = current->next;\r\n    }\r\n\r\n    return(0);\r\n}<\/pre>\n
The code has a lot of setup, which is necessary for a double-linked list: The structure greek<\/code> is declared at the start of the main()<\/em> function, as is the *ab[]<\/code> array, and the pointers required to manage the structure. Because this example uses only the main()<\/em> function, the greek<\/code> structure as well as the pointers are declared inside that function. If any other functions referenced the structure pointers, they must be declared externally.<\/p>\n
The core of the code is the for<\/em> loop between Lines 21 and 43.<\/p>\n
Line 23 allocates memory for a new structure and assigns that address to the created<\/code> pointer.<\/p>\n
Lines 30 through 34 handle the first item in the double-linked list, which is special: Line 32 sets the *prev<\/code> element to NULL<\/code>, marking the start of the list. The first<\/code> pointer is assigned to the beginning structure to mark its location for reference.<\/p>\n
The else<\/em> statements set options for all structures after the first: The current<\/code> pointer references what becomes the previous structure in the list; its location is saved in the created<\/code> structure’s *prev<\/code> member. The current<\/code> structure’s *next<\/code> member is updated to point to the created<\/code> structure’s address:<\/p>\n
created->prev = current;
\ncurrent->next = created;<\/code><\/p>\n
Next, the new (created<\/code>) structure’s letter<\/code> member is set to a letter of the Greek alphabet (Line 40). The *next<\/code> member is assigned the NULL<\/code> pointer. Finally, Line 42 sets the new structure to the current<\/code> pointer, current=created<\/code>.<\/p>\n
When the for<\/em> loop is complete, the last<\/code> pointer is updated to reference current<\/code>, which becomes the final structure in the list.<\/p>\n
To prove that it all works, a while<\/em> loop displays the double-linked list:<\/p>\n
alpha\r\nbeta\r\ngamma\r\ndelta\r\nepislon\r\nzeta\r\neta\r\ntheta\r\niota\r\nkappa<\/pre>\n
<\/code><\/p>\n
Because the list is double-linked, you can also display it in reverse order, as well as reference previous and next items from within the list. I'll explore these options in next week's Lesson<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"
A structure in a double-linked list must reference the previous structure in memory, which requires extra overhead when creating the list. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-2905","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2905","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2905"}],"version-history":[{"count":8,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2905\/revisions"}],"predecessor-version":[{"id":2940,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2905\/revisions\/2940"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2905"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2905"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2905"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}