Being a doubly linked list you should have a head and tail (kinda the
reason why you'd use a doubly linked list in the first place). If you
don't then I'm not sure how you'd fix that as the rest of the list
after the first missing right pointer would essentially be orphaned in
memory with no valid pointers allowing you to fix the rest of the
list.
head -> node1 <-> node2 -> node3 <-> node4 <- node5 <-> node6 <->
node7 <- tail
^ missing left ^
missing right.
Given this example, using the forward traversing while loop you would
be able to fix the link between node2 and node3, but would end on
node4 without any way to fix the missing right pointer since nothing
would be able to access the rest of the list without a tail. And
without a tail pointer, we would not know that any nodes in memory
actually point back at node4 so we would just think that's the end of
the list... Short of scanning the entire heap to find some memory that
contains node4's address (somehow) that data is just inaccessible and
orphaned now.
On Aug 31, 10:44 am, Dheeraj Sharma <dheerajsharma1...@gmail.com>
wrote:
> i get more clear to my quest..
> 1.Doubly Linked List
> 2.Firstly some right pointer is missing....and lately..some left pointer is
> missing
> 3.Head of pointer is given.
> 4.Repair the list..
>
>
>
>
>
>
>
>
>
> On Wed, Aug 31, 2011 at 10:12 PM, Sanjay Rajpal <srn...@gmail.com> wrote:
> > Chris : he said first, right pointer is missing, how can u repair that left
> > pointer first as you can't go forward ?
>
> > Sanju
> > :)
>
> > On Wed, Aug 31, 2011 at 9:39 AM, Chris <lokr...@gmail.com> wrote:
>
> >> When you say missing, I assume the left or right pointer is null. If
> >> that's the case, this could be a possible solution:
>
> >> // this fixes the missing left pointers traversing from the head
> >> node* curr = head;
> >> while (curr->right != null ) {
> >> if (curr->right->left == null) {
> >> curr->right->left = curr;
> >> }
> >> curr = curr->right;
> >> }
>
> >> // reverse the logic to fix pointers in the other direction starting
> >> at the end of the list
> >> node* curr = tail;
> >> while (curr->left != null) {
> >> if (curr->left->right == null) {
> >> curr->left->right = curr;
> >> }
> >> curr = curr->left;
> >> }
>
> >> On Aug 31, 10:23 am, Dheeraj Sharma <dheerajsharma1...@gmail.com>
> >> wrote:
> >> > A doubly linked list has one Left pointer missing and at some
> >> point..one
> >> > Right pointer missing..how to repair the doubly linked list?
> >> > ?
>
> >> > --
> >> > *Dheeraj Sharma*
> >> > Comp Engg.
> >> > NIT Kurukshetra
> >> > +91 8950264227
>
> >> --
>
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> *Dheeraj Sharma*
> Comp Engg.
> NIT Kurukshetra
> +91 8950264227
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
