Ada for C/C++ Developers: Linked List

This installment in my Ada tutorial series is designed to show how to use records, pointers and exceptions.  Every C and C++ programmer probably remembers one of the first milestones in coming to grasp with pointers is the successful implementation of the linked list data structure.

First of all, after analyzing the source code of other Ada code on the Internet, it seems that the preferred method for naming variables and functions is The_Name and not TheName; use underscores instead of camel case.  Also make sure you use uppercase at the beginning of a word too.  This seems to be Ada style, so we might as well adopt it.

The program below should speak for itself, but I’ll just mention a few things.

  • Records like structures in C, and that is all there is to them.  In C++ structures are really just classes and the keyword is only there for C language compatibility.
  • Recursive data structures, such as lists and trees, require forward declaration of the types.  See the program below for details, but this should not be too much of a shock as C++ requires the same unless your working with templates, and even then…
  • Exceptions will be covered more in a later tutorial, but I thought I would add it to the linked list code just to demonstrate the concept.
  • The type keyword is also introduced, but we will cover it later.  For now just know that it declares a new data type.
  • Pointers in Ada are declared using the access keyword.  I particularly like this keyword, because if you read the code, it makes sense in English.  For example,  “type Link is access Node;” can be read “type Link is access to a Node.”
  • Pointers in Ada are implicitly dereferenced. If you want to explicitly dereference the pointer, use Ptr.all, but let’s not worry about it for now.
  • GNAT implements garbage collection, so we can create objects and let the run-time worry about cleaning up the memory.  Note that Ada implementations are not required to support garbage collection, and most have options for disabling the garbage collection.
  • Finally, not-equal is /=, but due to Ada’s readability, you can probably figure that out from the code

So, with no further delay, the source code is below.  I did test it with some simple scenarios, but I did not exhaustively test every possibility.  (possible unit testing topic in the future?)  Hopefully there are no bugs!

with Ada.Text_IO; use Ada.Text_IO;

procedure ListMech is
   --
   -- Define the list data structures
   --   Note: recursive data structs require forward declaration
   type Node;			-- forward declare
   type Link is access Node;	-- read literally: a "Link" accesses a "Node"

   type Node is			-- now declare the Node type
      record
         Node_Id: Integer;	-- prefer underbar to camel-case
         Next:    Link;
      end record;

   type List is
      record
         Head:   Link;		-- first node in list
         Tail:   Link;		-- last node in list
         Length: Integer := 0;	-- number of nodes in the list
      end record;

   Empty_Exception: exception;

   --
   -- Inserts an ID into the linked list
   --
   procedure Insert( Id: in Integer; Linked_List: in out List) is
   begin
      if Linked_List.Head = null then
         Linked_List.Head := new Node'(Id, null);
         Linked_List.Tail := Linked_List.Head;
         Linked_List.Length := 1;
         Put_Line("List empty => creating head node: " & Integer'Image(Id));
      else
         Put_Line("Creating node: "  & Integer'Image(Id));
         Linked_List.Tail.Next := new Node'(Id, null);
         Linked_List.Length := Linked_List.Length + 1;
         Linked_List.Tail := Linked_List.Tail.Next;
      end if;
   end Insert;

   --
   -- Removes and ID from the linked list (if available)
   --
   procedure Remove( Id: in Integer; Linked_List: in out List ) is
      Curr_Link: Link := Linked_List.Head;
      Prev_Link: Link := null;
      Found_Flag: Boolean := False;
   begin
      -- make sure list is not empty
      if Linked_List.Head = null then
         raise Empty_Exception;
      end if;

      while Curr_Link /= null loop
         if Curr_Link.Node_Id = Id then
            Put_Line("Removing node: "  & Integer'Image(Curr_Link.Node_Id));
            if Curr_Link = Linked_List.Head then
               Linked_List.Head := Curr_Link.Next;
            else
               Prev_Link.Next := Curr_Link.Next;
            end if;
            Found_Flag := true;
            Linked_List.Length := Linked_List.Length - 1;
            exit;
         else
            Prev_Link := Curr_Link;
            Curr_Link := Curr_Link.Next;
         end if;
      end loop;

      if Found_Flag /= true then
         Put_Line("Node not in list: "  & Integer'Image(Id));
      end if;
   end Remove;

   --
   -- Traverses the linked list and prints out the IDs at each node
   --
   procedure Walk( Linked_List: in List ) is
      Link_Index: Link := Linked_List.Head;
   begin
      Put_Line("Walking the list(" & Integer'Image(Linked_List.Length)& "): ");
      loop
         exit when Link_Index = null;
         Put_Line("--> " & Integer'Image(Link_Index.Node_Id));
         Link_Index := Link_Index.Next;
      end loop;
   end Walk;

   -- local variables
   Id_List: List;
   TestVector: array(Positive range <>) of Integer := (1, 2, 3, 4, 5);

begin

   for Index in TestVector'Range loop
      Insert( TestVector(Index), Id_List );
   end loop;
   New_Line;
   Walk( Id_List );
   New_Line;
   Remove( 1, Id_List );
   New_Line;
   Walk( Id_list );
   New_Line;
   for Index in TestVector'Range loop
      Remove( TestVector(Index), Id_List );
   end loop;

   -- list should be empty now
   New_Line;
   Remove( 9, Id_List );

exception
      when Empty_Exception => Put_Line("*** List is empty ***");
end ListMech;

The code is significantly longer this time, but I think we’re ready to move away from trivial programs.  After all, we’re programmers, right?  We fear nothing!

C:\work\ada\listmech>listmech.exe
List empty => creating head node:  1
Creating node:  2
Creating node:  3
Creating node:  4
Creating node:  5

Walking the list( 5):
-->  1
-->  2
-->  3
-->  4
-->  5

Removing node:  1

Walking the list( 4):
-->  2
-->  3
-->  4
-->  5

Node not in list:  1
Removing node:  2
Removing node:  3
Removing node:  4
Removing node:  5

*** List is empty ***

Copy the source code into an editor and try it out for yourself.  I am a better programmer than I was when I started with C++ years ago, but it felt very easy to develop this linked list code.  I’m starting to appreciate the verbosity of the syntax, the rigidity of the compiler, and the elegance of the language.  I hope you’re enjoying our endeavor too.

Advertisements

One thought on “Ada for C/C++ Developers: Linked List

  1. Ahem, GNAT has no garbage collection. You WILL leak memory, unless you free() the nodes.
    Look at unchecked_deallocation

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s