head -> node1 <-> node2 <- node3 <-> node4 -> node5 <-> node6 <->
^ missing right ^missing left
node7 <- tail
now head and tail are given..is there any way to fix the pointers again?
On Wed, Aug 31, 2011 at 11:07 PM, Chris <lokr...@gmail.com> wrote:
> 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.
>
>
--
*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.
