A basic linked list of words in Ada (i)

Amazingly linked lists in Ada are no different than they are in C, except actually they may be somewhat easier to interpret. You can find out about basic pointers in Ada here (although in Ada they are termed “access values”.

Let’s jump right in and create a linked list, in this case to store a series of words. We will start out with some declarations.

type node;

type list is access node;

type node is record
   word: unbounded_string;
   next: list;
end record;

head: list;

For some people the declaration of node on Line 1 will seem a little odd, but it helps resolve the circularity of the definitions. The declaration on Line 3 refers to node, and the declaration of node (Line 5) refers to list. Line 1 is somewhat of an incomplete declaration as it simply tells the compiler that node is the name of a type of some sort so that the name can be used on Line 3. Nothing else very exciting here – Lines 5-8 declares node to be a record containing the data (word), and the pointer to the next node (next).

Next, we’ll create a procedure buildList() which will create the list, adding one word at a time. There isn’t anything magical here, just a stock-standard list implementation. Remember, lists are LIFO structures, so the last term that gets added is the head of the list.

procedure buildList(head: in out list; aword: in unbounded_string) is
   newNode: list;
begin
   newNode := new node'(word=>aword, next=>null);
   newNode.next := head;
   head := newNode;
end buildList;

On Line 4, the new node is created using new, which takes a free block of memory from the heap and reserves it for use as a node type variable. At the same time it assigns the string (aword), to word, and sets next to null. Lines 5 and 6 insert the new item into the list.

Next, we are going to add a procedure, printList(), to print the list.

procedure printList(head: in list) is
   scanPtr: list;
begin
   scanPtr := head;
   loop
      exit when scanPtr = null;
      put(scanPtr.word);
      scanPtr := scanPtr.next;
      put(" ");
   end loop;
end printList;

The variable scanPtr is a node used to scan the list. Line 5 is the exit strategy for the loop, exiting when the list becomes empty. Line 7 prints the word, and line 8 goes to the next word. Now we need some code to actually run the program.

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Strings.unbounded; use Ada.Strings.unbounded;
with Ada.Strings.unbounded.text_io; use Ada.Strings.unbounded.text_io;

procedure linkedlist is

   -- code from above goes here
   aword: unbounded_string;

begin
   loop
      put("> ");
      get_line(aword);
      exit when aword = "q";
      buildList(head, aword);
   end loop;

   put_line("the list as read :");
   printList(head);
   new_line;

end linkedlist;

Nothing special here. Lines 11-16 provides a loop, prompting the user for words, and building the list until “q” is entered, terminating the input. Here is the programming running:

> the
> cat
> sat
> on
> the
> hat
> q
the list as read :
hat the on sat cat the