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