{"id":27350,"date":"2018-01-20T21:58:08","date_gmt":"2018-01-20T16:28:08","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27350"},"modified":"2018-11-01T12:21:49","modified_gmt":"2018-11-01T06:51:49","slug":"reverse-doubly-linked-list-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/reverse-doubly-linked-list-2\/","title":{"rendered":"Reverse a Doubly Linked List"},"content":{"rendered":"<p><span style=\"color: #0000ff;\"><strong>Write a C function to reverse a given Doubly Linked List<\/strong><\/span><\/p>\n<h3 id=\"doubly-linked-list\"><span style=\"color: #008080;\">Doubly Linked List:<\/span><\/h3>\n<p><a href=\"https:\/\/www.wikitechy.com\/technology\/quicksort-doubly-linked-list-2\/\" target=\"_blank\" rel=\"noopener\">Doubly Linked List<\/a> (DLL) is a list of elements and it varies from\u00a0<a href=\"https:\/\/www.wikitechy.com\/technology\/write-function-get-nth-node-linked-list\/\" target=\"_blank\" rel=\"noopener\">Linked List<\/a>. It allows navigation,\u00a0<strong>either forward or backward<\/strong>\u00a0when compared to\u00a0<a href=\"https:\/\/www.wikitechy.com\/technology\/insertion-sort-singly-linked-list\/\" target=\"_blank\" rel=\"noopener\">Single Linked List<\/a>.\u00a0It has two pointers:<strong>\u00a0previous pointer and next pointer<\/strong>.\u00a0Every element points to next of the list and previous element in list.<\/p>\n<p><strong>Terms used in doubly linked list:<\/strong><\/p>\n<ul>\n<li>Link<\/li>\n<li>Next<\/li>\n<li>Prev<\/li>\n<li>Linked list<\/li>\n<\/ul>\n<p>See below diagrams for example.<span id=\"more-5985\"><\/span><\/p>\n<pre><strong>     (a) Original Doubly Linked List  <\/strong><\/pre>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-27359\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL.png\" alt=\"Reverse a Doubly Linked List\" width=\"553\" height=\"112\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL.png 553w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL-300x61.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/DLL-550x112.png 550w\" sizes=\"(max-width: 553px) 100vw, 553px\" \/><\/p>\n<pre><strong>(b) Reversed Doubly Linked List  <\/strong><\/pre>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-27361\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/RDLL.png\" alt=\"Reverse a Doubly Linked List\" width=\"553\" height=\"112\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/RDLL.png 553w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/RDLL-300x61.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/06\/RDLL-550x112.png 550w\" sizes=\"(max-width: 553px) 100vw, 553px\" \/><\/p>\n<p>Here is a simple method for <strong>reversing a Doubly Linked List<\/strong>. All we need to do is <strong>swap prev and next pointers<\/strong> for all nodes, change prev of the head (or start) and change the head pointer in the end.<\/p>\n<h3 id=\"c-programming\"><span style=\"color: #003366;\">C programming:<\/span><\/h3>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F*%20Program%20to%20reverse%20a%20doubly%20linked%20list%20*%2F%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F*%20a%20node%20of%20the%20doubly%20linked%20list%20*%2F%0Astruct%20node%0A%7B%0A%20%20int%20data%3B%0A%20%20struct%20node%20*next%3B%0A%20%20struct%20node%20*prev%3B%20%20%20%20%0A%7D%3B%0A%20%0A%2F*%20Function%20to%20reverse%20a%20Doubly%20Linked%20List%20*%2F%0Avoid%20reverse(struct%20node%20**head_ref)%0A%7B%0A%20%20%20%20%20struct%20node%20*temp%20%3D%20NULL%3B%20%20%0A%20%20%20%20%20struct%20node%20*current%20%3D%20*head_ref%3B%0A%20%20%20%20%20%20%0A%20%20%20%20%20%2F*%20swap%20next%20and%20prev%20for%20all%20nodes%20of%20%0A%20%20%20%20%20%20%20doubly%20linked%20list%20*%2F%0A%20%20%20%20%20while%20(current%20!%3D%20%20NULL)%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20temp%20%3D%20current-%3Eprev%3B%0A%20%20%20%20%20%20%20current-%3Eprev%20%3D%20current-%3Enext%3B%0A%20%20%20%20%20%20%20current-%3Enext%20%3D%20temp%3B%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20current%20%3D%20current-%3Eprev%3B%0A%20%20%20%20%20%7D%20%20%20%20%20%20%0A%20%20%20%20%20%20%0A%20%20%20%20%20%2F*%20Before%20changing%20head%2C%20check%20for%20the%20cases%20like%20empty%20%0A%20%20%20%20%20%20%20%20list%20and%20list%20with%20only%20one%20node%20*%2F%0A%20%20%20%20%20if(temp%20!%3D%20NULL%20)%0A%20%20%20%20%20%20%20%20*head_ref%20%3D%20temp-%3Eprev%3B%0A%7D%20%20%20%20%20%0A%20%0A%20%0A%20%0A%2F*%20UTILITY%20FUNCTIONS%20*%2F%0A%2F*%20Function%20to%20insert%20a%20node%20at%20the%20beginging%20of%20the%20Doubly%20Linked%20List%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%20%20%20%20%0A%20%20%20%20%2F*%20since%20we%20are%20adding%20at%20the%20begining%2C%20%0A%20%20%20%20%20%20prev%20is%20always%20NULL%20*%2F%0A%20%20%20%20new_node-%3Eprev%20%3D%20NULL%3B%0A%20%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%20%20%20%20%0A%20%0A%20%20%20%20%2F*%20change%20prev%20of%20head%20node%20to%20new%20node%20*%2F%0A%20%20%20%20if((*head_ref)%20!%3D%20%20NULL)%0A%20%20%20%20%20%20(*head_ref)-%3Eprev%20%3D%20new_node%20%3B%20%20%20%20%0A%20%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20nodes%20in%20a%20given%20doubly%20linked%20list%20%0A%20%20%20This%20function%20is%20same%20as%20printList()%20of%20singly%20linked%20lsit%20*%2F%0Avoid%20printList(struct%20node%20*node)%0A%7B%0A%20%20while(node!%3DNULL)%0A%20%20%7B%0A%20%20%20printf(%22%25d%20%22%2C%20node-%3Edata)%3B%0A%20%20%20node%20%3D%20node-%3Enext%3B%0A%20%20%7D%0A%7D%20%0A%20%0A%2F*%20Drier%20program%20to%20test%20above%20functions*%2F%0Aint%20main()%0A%7B%0A%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%20%0A%20%20%2F*%20Let%20us%20create%20a%20sorted%20linked%20list%20to%20test%20the%20functions%0A%20%20%20Created%20linked%20list%20will%20be%2010-%3E8-%3E4-%3E2%20*%2F%0A%20%20push(%26head%2C%202)%3B%0A%20%20push(%26head%2C%204)%3B%0A%20%20push(%26head%2C%208)%3B%0A%20%20push(%26head%2C%2010)%3B%0A%20%20%0A%20%20printf(%22%5Cn%20Original%20Linked%20list%20%22)%3B%0A%20%20printList(head)%3B%0A%20%20%0A%20%20%2F*%20Reverse%20doubly%20linked%20list%20*%2F%0A%20%20reverse(%26head)%3B%0A%20%20%0A%20%20printf(%22%5Cn%20Reversed%20Linked%20list%20%22)%3B%0A%20%20printList(head)%3B%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%0A%20%20getchar()%3B%0A%7D\u201d message=\u201d\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<h3 id=\"output\"><span style=\"color: #008000;\">Output:<\/span><\/h3>\n<pre id=\"preOutput\" class=\"gb wf\">Original Linked list 10 8 4 2 \r\nReversed Linked list 2 4 8 10<\/pre>\n<p><strong><span style=\"color: #003300;\">Time Complexity:<\/span> O(n)<\/strong><\/p>\n<p>We can also swap data instead of <a href=\"https:\/\/www.wikitechy.com\/tutorials\/c++\/c++-pointers\" target=\"_blank\" rel=\"noopener\">pointers<\/a> to reverse the Doubly Linked List. Method used for reversing array can be used to swap data. <a href=\"https:\/\/www.wikitechy.com\/technology\/java-algorithm-swap-nodes-linked-list-without-swapping-data\/\" target=\"_blank\" rel=\"noopener\">Swapping data<\/a> can be costly compared to pointers if size of data item(s) is more.<\/p>\n<div id=\"company_tags\">\u00a0[ad type=\u201dbanner\u201d]<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Reverse a Doubly Linked List &#8211; Doubly Linked List &#8211; A simple method for reversing a Doubly Linked List. All we need to do is swap prev and next pointers.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,79479,79476],"tags":[81441,81440,81436,81443,81437,81439,81438,81442],"class_list":["post-27350","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-doubly-linked-list","category-linked-list","tag-doubly-linked-list-geeks-for-geeks","tag-reverse-a-circular-linked-list","tag-reverse-a-doubly-linked-list-hackerrank-solution","tag-reverse-a-doubly-linked-list-python","tag-reverse-doubly-linked-list-c-recursion","tag-reverse-doubly-linked-list-recursively","tag-reverse-of-linked-list-in-c","tag-reverse-the-doubly-linked-list-without-using-extra-space"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27350","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27350"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27350\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27350"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27350"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27350"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}