{"id":2919,"date":"2018-01-20T00:01:23","date_gmt":"2018-01-20T08:01:23","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=2919"},"modified":"2018-01-06T10:32:35","modified_gmt":"2018-01-06T18:32:35","slug":"playing-with-a-double-linked-list","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=2919","title":{"rendered":"Playing with a Double-Linked List"},"content":{"rendered":"

In last week’s Lesson<\/a>, I demonstrated code that builds a double-linked list: Each structure in the list references both the next structure and the previous structure. The first and last structure addresses are saved. And NULL<\/code> pointers within the list its start and end. How all that junk becomes useful is apparent as you work with the list.
\n
\nThe code presented in last week’s Lesson walked through the linked list from the first structure to the last, displaying each structure’s data. This feat you can perform in single-linked lists as well. To move through a double-linked list in reverse order, the code looks like this:<\/p>\n

\r\n    \/* display list back-to-front *\/<\/span>\r\n    current = last;\r\n    while(current)\r\n    {\r\n        printf(\"%s\\n\",current->letter);\r\n        current = current->prev;\r\n    }<\/pre>\n
The current<\/code> pointer is assigned to the last<\/code> structure in the list (instead of first<\/code>). Within the while<\/em> loop, the current<\/code> pointer is updated to the value of current->prev<\/code> instead of current->next<\/code>. The result is that the first ten letters of the Greek alphabet are output in reverse order:<\/p>\n
kappa\r\niota\r\ntheta\r\neta\r\nzeta\r\nepsilon\r\ndelta\r\ngamma\r\nbeta\r\nalpha<\/code><\/pre>\n
For a standard, single-linked list, this task would be difficult, especially if you wanted to show the list both ways in the same program. Click here<\/a> to view the full code.<\/p>\n
Another advantage of a double-linked list is that you can move forward or backward from any specific structure, even accessing neighboring structure’s data.<\/p>\n
The following code accesses the fifth structure in the linked list. It displays the current, previous, and next letter names in the Greek alphabet:<\/p>\n
\r\n    \/* display item 5 in the list *\/<\/span>\r\n    current = first;\r\n    for(x=0;x<4;x++)\r\n        current = current->next;\r\n    printf(\"The fifth letter is %s\\n\",current->letter);\r\n    printf(\"The previous letter is %s\\n\",(current->prev)->letter);\r\n    printf(\"The next letter is %s\\n\",(current->next)->letter);<\/pre>\n
The for<\/em> loop advances the current<\/code> pointer through the list. Because variable x<\/code> is post-incremented in the for<\/em> loop, the value of x<\/code> equals 4 when the loop is done, which represents the fifth item in the list.<\/p>\n
The letter name of the current<\/code> pointer’s structure is accessed from current->letter<\/code>.<\/p>\n
The previous structure is referenced through the current->prev<\/code> pointer. That structure’s letter<\/code> member is accessed through the (current->prev)->letter<\/code> construction. Likewise, the next structure’s letter member is accessed by using (current->next)->letter<\/code>. (The parentheses are optional; I’ve added them for readability.)<\/p>\n
Here’s the output:<\/p>\n
The fifth letter is epsilon\r\nThe previous letter is delta\r\nThe next letter is zeta<\/code><\/pre>\n
Similar output could be generated for each structure in the list; previous and next structures’ members can always be accessed. Click here<\/a> to view the full code.<\/p>\n
Just to be obnoxious, the following construction is also possible with a linked list:<\/p>\n
\r\n    \/* display item 5 in the list *\/<\/span>\r\n    printf(\"The fifth letter is %s\\n\",\r\n            first->next->next->next->next->letter);<\/pre>\n
I find this type of structure-pointer reference ugly, yet it proves that the method shown earlier ((current->next)->letter<\/code>) isn’t really as weird as it potentially could be.<\/p>\n","protected":false},"excerpt":{"rendered":"
Explore the advantages of going to all the trouble of creating a double-linked 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-2919","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\/2919","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=2919"}],"version-history":[{"count":5,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2919\/revisions"}],"predecessor-version":[{"id":2934,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/2919\/revisions\/2934"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2919"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2919"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2919"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}