With a basic linked list that really only builds the list and prints it out, let’s add another function to reverse the list. The procedure below works by extracting the head element repeatedly and building it back in reverse.
procedure reverseList(head: in out list) is
temp: list := null;
revl: list := null;
while head /= null loop
temp := head;
head := head.next;
temp.next := revl;
revl := temp;
head := revl;
What is happening here? The list temp holds the extracted item, while revl holds the reversed list. Line 5 loops through the list. Line 6 extracts a node the list (head). Line 7 sets the list head to the next item, and Line 8 adds the extracted node to the reverse list. Finally Line 9 sets the input list pointer to the reversed list. Finally on Line 11, the input list pointer is set to the reversed list.
For something a little more interesting, here’s the recursive version of the procedure:
function reverseListR(head: in list) return list is
if head = null or else head.next = null then
rest := reverseListR(head.next);
head.next.next := head;
head.next := null;
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 list is access node;
type node is record
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 := new node'(word=>aword, next=>null);
newNode.next := head;
head := newNode;
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 := head;
exit when scanPtr = null;
scanPtr := scanPtr.next;
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
exit when aword = "q";
put_line("the list as read :");
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 list as read :
hat the on sat cat the