Reverse linked list in Ada

Admin 1
Viewed 171

so as you can see I am trying to make a procedure to reverse a linked list, here is the code and the records of the list and the node, I am only obtaining the first number of the list and I think that it could be because pre is null and the head (Current) is pointing to null but I am not sure and I do not know how to solve this, thank you.

Type Node;
Type List is access Node;
Type Node is record
    Info: Integer;
    nx: List;
end record;


 procedure reverselist (L: in out List) is
      Current: List:=L ;
      Pre: List:=null;
      Next: List:=null;
   begin
      if Current.nx /= null then
         while Current.nx /= null loop
            Next:= Current.nx;
            Current.nx:= Pre;
            Pre:= Current;
            Current:= Next;
         end loop;
      end if;
      
   end reverselist;
ada list
3 Answers
if Current /= null then
         while Current.nx /= null loop
            Next:= Current.nx;
            Current.nx:= Pre;
            Pre:= Current;
            Current:= Next;
         end loop;
         Next:= null;
         Current.nx:= Pre;
         L:= Current;
end if;
Admin1

I would start by just popping the head off the list repeatedly and building it back in reverse order:

procedure Reverse_List (L : in out list) is 
    Temp : List := null;  -- Holds a "popped" head
    Head : List := null;  -- This is the head of the reversed list
begin
    while L /= null loop
        Temp := L;        -- Pop the head of the list off
        L := L.nx;        -- Set the list head to the next item
        Temp.nx := Head;  -- Attach the popped node to the reversed head
        Head := Temp;     -- Reset the reverse head to the new node
    end loop;
    L := Head; -- Now set the input list pointer to the newly reversed list
end Reverse_List;

Full test program:

with Ada.Text_IO; use Ada.Text_IO;
procedure Hello is

    Type Node;
    Type List is access Node;
    Type Node is record
        Info: Integer;
        nx: List;
    end record;

    procedure Reverse_List (L : in out list) is 
        Temp : List := null;  -- Holds a "popped" head
        Head : List := null;  -- This is the head of the reversed list
    begin
        while L /= null loop
            Temp := L;        -- Pop the head of the list off
            L := L.nx;        -- Set the list head to the next item
            Temp.nx := Head;  -- Attach the popped node to the reversed head
            Head := Temp;     -- Reset the reverse head to the new node
        end loop;
        L := Head; -- Now set the input list pointer to the newly reversed list
    end Reverse_List;

    nodes : array (1..5) of List := 
        (new Node'(Info => 1, nx =>null),
         new Node'(Info => 2, nx =>null),
         new Node'(Info => 3, nx =>null),
         new Node'(Info => 4, nx =>null),
         new Node'(Info => 5, nx =>null));
         
         
    procedure Print(L : List) is
        C : List := L;
    begin
        while C /= null loop
            Put_Line(C.Info'Image);
            C := C.nx;
        end loop;
    end Print;
    
    L : List := nodes(1);

begin
    Put_Line("Hello, world!");
    nodes(1).nx := nodes(2);
    nodes(2).nx := nodes(3);
    nodes(3).nx := nodes(4);
    nodes(4).nx := nodes(5);
    
    Put_Line("Before:");
    Print(L);
    New_Line(2);
    Put_Line("After:");
    Reverse_List(L);
    Print(L);
end Hello;

Output:

$gnatmake -o hello *.adb
gcc -c hello.adb
gnatbind -x hello.ali
gnatlink hello.ali -o hello
$hello
Hello, world!
Before:
 1
 2
 3
 4
 5


After:
 5
 4
 3
 2
 1
user_96049660

Going forward, also consider the convenience of a doubly linked list such as Ada.Containers.Doubly_Linked_Lists. Given an instance of the package for Integer,

package Integer_Lists is new Doubly_Linked_Lists (Integer);
use Integer_Lists;

A Reverse_List procedure can traverse the list in reverse, as discussed in Iteration, to create a new reversed list. Compare this approach to @Jere's Reverse_List.

procedure Reverse_List (L : in out List) is
   T : List;
begin
   for E of reverse L loop
      T.Append (E);
   end loop;
   L := T;
end Reverse_List;

As an alternative to copying elements, the package also offers Reverse_Elements, which "Reorders the elements of Container in reverse order."

Reverse_Elements (L);

Complete example:

with Ada.Containers.Doubly_Linked_Lists; use Ada.Containers;
with Ada.Text_IO;                        use Ada.Text_IO;

procedure DLL is

   package Integer_Lists is new Doubly_Linked_Lists (Integer);
   use Integer_Lists;

   procedure Reverse_List (L : in out List) is
      T : List;
   begin
      for E of reverse L loop
         T.Append (E);
      end loop;
      L := T;
   end Reverse_List;

   procedure Print (L : List) is
   begin
      for E of L loop
         Put_line (Integer'Image (E));
      end loop;
   end Print;

   L : List;

begin

   L.Append (1);
   L.Append (2);
   L.Append (3);

   Put_line ("Before:");
   Print (L);
   --Reverse_List(L);
   Reverse_Elements (L);
   Put_line ("After:");
   Print (L);
end DLL;

Console:

Before:
 1
 2
 3
After:
 3
 2
 1
user_2305130
Related