# Normal view

Before yesterdayNews from the Ada programming language world

25 February 2023 at 16:26

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;
begin
temp.next := revl;
revl := temp;
end loop;
end reverselist;
```

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
rest: list;
begin
end if;
return rest;
end reverselistR;
```
• 25 February 2023 at 16:26

23 February 2023 at 16:29

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;

```

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);
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
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;

-- code from above goes here
aword: unbounded_string;

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

new_line;

```

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