can't understand how to move a node of a linked list to another place on the same

can't understand how to move a node of a linked list to another place on the same

[Mehdi Saada]

I cannot understand the mechanism for moving a node of a list somewhere else on the same list. the piece always just disappears.

When called for two adjacent nodes, while it should have the effect of swapping them, the first just disappears.
I use the pointers before said place A and B because it's a single linked list.

let's have these definitions:
type t_element is new Character;
   type t_cell;
   type t_List is access t_cell;
   type t_cell is record
      value: t_element;
      next: t_list;
   end record;

 procedure insertion_A_on_place_B (Before_A, Before_B: in t_List) is
      A: constant t_List := Before_A.next;
      B: constant t_List := Before_B.next;
   begin
      Before_A.next := Before_A.next.next;
      A.next := B;
      Before_B.next := A;
   end insertion_A_on_place_B;

I fear I won't understand if I just read a snippet on the internet, I tried enough so that my brain just "blocks" and in that case I'll never see the issue by just trying again. Did it enough. Asperger. I know myself.
I tried reading on the internet, it "blocks"...

What are the correct instructions to move Element A at place B (of the same list) ? then I'll see where I block.

Re: can't understand how to move a node of a linked list to another place on the same

[Gautier write-only address]

> No, I'll run it on paper first, please don't bother yet.

That's actually the fun part with linked lists.

Re: can't understand how to move a node of a linked list to another place on the same

[Mehdi Saada]

Le jeudi 18 février 2021 à 08:06:57 UTC+1, gautier...@hotmail.com a écrit :
> > No, I'll run it on paper first, please don't bother yet.
> That's actually the fun part with linked lists.
 
> That's actually the fun part with linked lists. 
I hate that to no end.

I did put up quite the effort so non-ashamedly I beg for help.
Here's it running on paper. Of course it's wrong 'cause the actual result is still A disappearing.

   procedure insertion_X_on_place_Y (Before_X, Before_Y: in t_List) is
      A: constant t_List := Before_X.next;
      Y: constant t_List := Before_Y.next;
   Begin
      Before_X.next := Before_X.next.next;
      X.next := Y;
      Before_Y.next := X;
   end insertion_X_on_place_Y;

Before running:
X		(x)->(x+1)->..
Y		(y)->(y+1)->..
Before_X	(x-1)->(x)->(x+1)...->(Y-1)->(Y)->(y+1)..
Before_X.next	(x)->(x+1)...->(Y-1)->(Y)->(y+1)..
Before_Y	(Y-1)->(Y)->(y+1)..
Before_Y.next	(Y)->(y+1)..

But: I want (x-1)->(x+1)...->(Y-1)->(x)-> (Y)->(y+1)..

Before_X.next := X.next;

X		(x)->(x+1)->..
Y		(y)->(y+1)->..
Before_X	(x-1)-> (x+1)...->(Y-1)->(Y)->(y+1)..
Before_X.next	(x+1)...->(Y-1)->(Y)->(y+1)..
Before_Y	(Y-1)->(Y)->(y+1)..
Before_Y.next	(Y)->(y+1)..

X.next := Y;

X		(x)->(y)->(y+1)->..
Y		(y)->(y+1)->..
Before_X	(x-1)-> (x+1)...->(Y-1)->(Y)->(y+1)..
Before_X.next	(x+1)...->(Y-1)->(Y)->(y+1)..
Before_Y	(Y-1)->(Y)->(y+1)..
Before_Y.next	(Y)->(y+1)..

Before_Y.next := X;

X		(x)->(y)->(y+1)->..
Y		(y)->(y+1)->..
Before_X	(x-1)-> (x+1)...->(Y-1)->(x)->(y)->(y+1)->..
Before_X.next	(x+1)...->(Y-1)->(x)->(y)->(y+1)->..
Before_Y	(Y-1)->(x)->(y)->(y+1)->..
Before_Y.next	(x)->(y)->(y+1)->..
It SHOULD be ok.

then I display it:
insertion_A_on_place_b(List, List.next);
   ITERATOR := List;
   while ITERATOR /= null loop
      Put(ITERATOR.value'Image & ' ');
      ITERATOR := ITERATOR.next;
   end loop;

'1' 
'3' 
'4' 
'5' 

PLEASE HELP.

Re: can't understand how to move a node of a linked list to another place on the same

[Jeffrey R. Carter]

On 2/18/21 1:54 PM, Mehdi Saada wrote:
> 
>     procedure insertion_X_on_place_Y (Before_X, Before_Y: in t_List) is
>        A: constant t_List := Before_X.next;
>        Y: constant t_List := Before_Y.next;
>     Begin
>        Before_X.next := Before_X.next.next;
>        X.next := Y;
>        Before_Y.next := X;
>     end insertion_X_on_place_Y;

What is X?

-- 
Jeff Carter
"I was hobbling along, minding my own business, all of a
sudden, up he comes, cures me! One minute I'm a leper with
a trade, next minute my livelihood's gone! Not so much as a
'by your leave!' You're cured, mate. Bloody do-gooder!"
Monty Python's Life of Brian
76

Re: can't understand how to move a node of a linked list to another place on the same

[Simon Wright]

Mehdi Saada <00120260a@gmail.com> writes:

> insertion_A_on_place_b(List, List.next);

I think your algorithm works provided that Before_A and Before_B aren't
too close together; i.e. if Before_A.Next is equal to Before_B.

Re: can't understand how to move a node of a linked list to another place on the same

[Mehdi Saada]

Dammit ! I meant to replace all A by X.
X means the node of place X, that I want moved before the node of place Y.

Yes it works in this case, Simon. But can't it too, when it comes switching two adjacent nodes ?
what I wrote on paper with X and Y should work in all cases... 

Re: can't understand how to move a node of a linked list to another place on the same

[Simon Wright]

Mehdi Saada <00120260a@gmail.com> writes:

> X means the node of place X, that I want moved before the node of
> place Y.

I don't think it does that; I think it moves it _after_. Weren't you
just having a conversation about clarity of purpose?

May I say that a simple linked list isn't a good structure if you want
to do this sort of thing to it! as you (and I) have found.

Consider a list [p q r s t] and you want to move r after s. I'm going to
use w -> x to mean that the node whose value is 'w' has Next pointing to
the node whose value is 'y'; personally I find it easier to draw the
nodes on paper, it's hard work typing the equivalent. YMMV.

Using your original naming, Before_A -> q, Before_B -> r.

   procedure Insertion_A_On_Place_B (Before_A, Before_B: in T_List) is
      A: constant T_List := Before_A.Next;
      --  r
      B: constant T_List := Before_B.Next;
      --  s
   begin
      Before_A.Next := A.Next;
      --  q -> s
      A.Next := B;
      --  r -> s (no change!)
      Before_B.Next := A;
      --  r -> r
   end Insertion_A_On_Place_B;

and the list is now [p q s t], with r left dangling and pointing to
itself.

Re: can't understand how to move a node of a linked list to another place on the same

[Mehdi Saada]

Indeed you're entirely right (though it seems harder on paper to me ? lack of habit ? dunno).
I feel a little bit relieved but then that doesn't fit in my Insertion sort routine.
Thanks. But I'm through with this, I'll meet linked lists again in the Knuth, so until then I don't care, I do other things.
Sometimes it's good to acknowledge defeat, to better come back.

Re: can't understand how to move a node of a linked list to another place on the same

[Simon Wright]

Simon Wright <simon@pushface.org> writes:

> Consider a list [p q r s t] and you want to move r after s. I'm going to
> use w -> x to mean that the node whose value is 'w' has Next pointing to
> the node whose value is 'y'; personally I find it easier to draw the
> nodes on paper, it's hard work typing the equivalent. YMMV.

obvs w -> x is meant to mean that the node whose value is 'w' has Next
pointing to the node whose value is 'x'