{"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<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">\/* Program to reverse a doubly linked list *\/<br\/>#include &lt;stdio.h&gt;<br\/>#include &lt;stdlib.h&gt;<br\/> <br\/>\/* a node of the doubly linked list *\/<br\/>struct node<br\/>{<br\/>  int data;<br\/>  struct node *next;<br\/>  struct node *prev;    <br\/>};<br\/> <br\/>\/* Function to reverse a Doubly Linked List *\/<br\/>void reverse(struct node **head_ref)<br\/>{<br\/>     struct node *temp = NULL;  <br\/>     struct node *current = *head_ref;<br\/>      <br\/>     \/* swap next and prev for all nodes of <br\/>       doubly linked list *\/<br\/>     while (current !=  NULL)<br\/>     {<br\/>       temp = current-&gt;prev;<br\/>       current-&gt;prev = current-&gt;next;<br\/>       current-&gt;next = temp;              <br\/>       current = current-&gt;prev;<br\/>     }      <br\/>      <br\/>     \/* Before changing head, check for the cases like empty <br\/>        list and list with only one node *\/<br\/>     if(temp != NULL )<br\/>        *head_ref = temp-&gt;prev;<br\/>}     <br\/> <br\/> <br\/> <br\/>\/* UTILITY FUNCTIONS *\/<br\/>\/* Function to insert a node at the beginging of the Doubly Linked List *\/<br\/>void push(struct node** head_ref, int new_data)<br\/>{<br\/>    \/* allocate node *\/<br\/>    struct node* new_node =<br\/>            (struct node*) malloc(sizeof(struct node));<br\/>  <br\/>    \/* put in the data  *\/<br\/>    new_node-&gt;data  = new_data;<br\/>     <br\/>    \/* since we are adding at the begining, <br\/>      prev is always NULL *\/<br\/>    new_node-&gt;prev = NULL;<br\/>  <br\/>    \/* link the old list off the new node *\/<br\/>    new_node-&gt;next = (*head_ref);    <br\/> <br\/>    \/* change prev of head node to new node *\/<br\/>    if((*head_ref) !=  NULL)<br\/>      (*head_ref)-&gt;prev = new_node ;    <br\/>  <br\/>    \/* move the head to point to the new node *\/<br\/>    (*head_ref)    = new_node;<br\/>}<br\/> <br\/>\/* Function to print nodes in a given doubly linked list <br\/>   This function is same as printList() of singly linked lsit *\/<br\/>void printList(struct node *node)<br\/>{<br\/>  while(node!=NULL)<br\/>  {<br\/>   printf(&quot;%d &quot;, node-&gt;data);<br\/>   node = node-&gt;next;<br\/>  }<br\/>} <br\/> <br\/>\/* Drier program to test above functions*\/<br\/>int main()<br\/>{<br\/>  \/* Start with the empty list *\/<br\/>  struct node* head = NULL;<br\/>  <br\/>  \/* Let us create a sorted linked list to test the functions<br\/>   Created linked list will be 10-&gt;8-&gt;4-&gt;2 *\/<br\/>  push(&amp;head, 2);<br\/>  push(&amp;head, 4);<br\/>  push(&amp;head, 8);<br\/>  push(&amp;head, 10);<br\/>  <br\/>  printf(&quot;\\n Original Linked list &quot;);<br\/>  printList(head);<br\/>  <br\/>  \/* Reverse doubly linked list *\/<br\/>  reverse(&amp;head);<br\/>  <br\/>  printf(&quot;\\n Reversed Linked list &quot;);<br\/>  printList(head);           <br\/>  <br\/>  getchar();<br\/>}<\/code><\/pre> <\/div>\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=&#8221;banner&#8221;]<\/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}]}}