Pointer arrays and linked structures

A record that refers to another record of its own type is the oldest use of a pointer, and Fortran does it with a pointer component. The type names itself inside its own definition, the storage comes from allocate, the links are pointer assignments and the last thing a program has to do is walk the structure and free every node. This lesson builds a small list of reals, counts it, prints it and destroys it, and shows why the component has to be a pointer.

A node type

type :: node holds a value and a next that is a pointer to another node, initialised to null() so that a fresh node ends the list. The type refers to itself in its own definition, which the language allows only for a pointer component: a record of a fixed size cannot contain a record of the same size.

The file list.f90:

module lists implicit none private public :: node, push, walk, count_nodes, destroy type :: node real :: value = 0.0 type(node), pointer :: next => null() end type node contains subroutine push(head, v) type(node), pointer, intent(inout) :: head real, intent(in) :: v type(node), pointer :: fresh allocate(fresh) fresh%value = v fresh%next => head head => fresh end subroutine push subroutine walk(head) type(node), pointer, intent(in) :: head type(node), pointer :: cur cur => head do while (associated(cur)) print '(a,f6.1)', 'node ', cur%value cur => cur%next end do end subroutine walk function count_nodes(head) result(n) type(node), pointer, intent(in) :: head integer :: n type(node), pointer :: cur n = 0 cur => head do while (associated(cur)) n = n + 1 cur => cur%next end do end function count_nodes subroutine destroy(head) type(node), pointer, intent(inout) :: head type(node), pointer :: cur, nxt cur => head do while (associated(cur)) nxt => cur%next deallocate(cur) cur => nxt end do nullify(head) end subroutine destroy end module lists program listdemo use lists implicit none type(node), pointer :: head => null() call push(head, 1.0) call push(head, 2.0) call push(head, 3.0) print '(a,i0)', 'nodes = ', count_nodes(head) call walk(head) call destroy(head) print '(a,l1)', 'head after destroy = ', associated(head) print '(a,i0)', 'nodes = ', count_nodes(head) end program listdemo

gfortran -Wall -Wextra -std=f2018 list.f90 -o list
./list

nodes = 3
node 3.0
node 2.0
node 1.0
head after destroy = F
nodes = 0

Building the list

push allocates one node, fills it, points its next at the current head and then makes the new node the head. The order is the whole trick: the link is written before the head moves, so no state exists in which the list is broken. The result is a stack, which is why the walk prints three, two, one.

head is a pointer dummy with intent(inout), because head => fresh re-associates the caller's pointer. Without the pointer attribute the subroutine would receive a copy of the address and the caller would still point at the old head, with a fresh node leaking on the heap.

Walking it

The walk is a do while over associated(cur): a local pointer starts at the head and follows cur => cur%next until the last node, whose next is null. The same loop counts the nodes. Both take the head as intent(in), so the structure is read only and the pointers inside it are followed, not changed.

A recursive function that walks the list is possible and is the natural way to write a sum or a reverse; a list of a hundred thousand nodes needs the loop, because every level of recursion is a stack frame and the default stack is about eight megabytes. This is the same trade-off as lesson 064.

Freeing it

destroy has to save cur%next before it deallocates cur, because after the deallocation the node and its components are gone. The local nxt is what makes the loop legal, and the nullify(head) at the end is what leaves the caller with a defined status instead of a dangling pointer.

A linked structure of this kind has no automatic release: the nodes are not components of anything, so nothing frees them when the head goes out of scope. Valgrind on a program that forgets destroy reports one leak per node, which is lesson 116. A type with an allocatable array is the cheaper design when the structure is a sequence, and the next lesson compares the two.

An array of pointers

real, pointer :: col(:) declares a pointer to an array, which is one pointer with bounds; an array of pointers is a different thing and needs the pointer attribute inside the type system, as in type(node), pointer :: items(:), which is a pointer to an array of nodes. A genuine array whose every element is a pointer is not something Fortran provides; the usual substitute is an array of a small type that holds one pointer, which is the container pattern of lesson 076.

That distinction is worth keeping straight because the two look alike in a declaration and behave differently: items(3) of a pointer-to-array is an element of one array, while items(3)%p of an array of a type is a pointer that may each point somewhere else.

A node that contains itself

Remove the pointer attribute and a record would have to contain itself, which has no finite size:

program badrecursive implicit none type :: node real :: value = 0.0 type(node) :: next end type node type(node) :: first first%value = 1.0 print *, first%value end program badrecursive

gfortran -Wall -Wextra -std=f2018 badrecursive.f90 -o badrecursive

badrecursive.f90:6:22:

6 | type(node) :: next
| 1
Error: Component at (1) must have the POINTER attribute

The message is short because the rule is: inside a type, a component of that same type has to be a pointer. An allocatable component of the same type is allowed as well, and it gives a tree rather than a list, since an allocatable cannot be associated with a node that already exists elsewhere.

Rules for a linked structure

Four rules keep a hand-written structure correct. Initialise every pointer component with => null() so that a fresh node terminates the list. Write the link before you move the head, as push does. Save the next pointer before you free a node, as destroy does. And nullify the head after the last deallocation, so the caller's pointer has a defined status.

Everything else is the same as in any language: a list costs one allocation per element, a walk costs a pointer chase per element that the cache cannot predict, and an array costs none of that. For the sequences this course keeps meeting, the array wins every time; the list is for inserting in the middle, for a size nobody knows, and for the data structures that genuinely need one.

Exercises

  1. Write append(head, v) that adds a node at the end instead of the front. Which case does it have to test first?
  2. Add a sum_nodes(head) function and print the total for the three nodes.
  3. Call destroy(head) twice in a row. What does the second call do, and why is it safe?
  4. Remove the => null() from the next component and push three nodes. Does the walk still stop, and why?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Why must the next component be a pointer?

    Answer

    A record cannot contain itself by value, only by reference

    The component has to have the POINTER attribute.

  2. What does push do first?

    Answer

    Allocates a node and points its next at the current head

    The link is written before the head moves.

  3. What does this program print? module m implicit none type :: node integer :: v = 0 type(node), pointer :: next => null() end type node end module m program p use m implicit none type(node), pointer :: a => null(), b => null() allocate(a) allocate(b) a%v = 1 b%v = 2 b%next => a print *, b%v, b%next%v end program p

    Answer

    2 1

    b holds two and its next is the node with one.

  4. Why does destroy save cur%next before deallocating?

    Answer

    The node and its components are gone after the deallocation

    The link has to be read while the node still exists.

  5. What frees the nodes of a linked list?

    Answer

    Nothing automatic: the program has to walk and deallocate

    The nodes are not components of anything.

  6. What is type(node), pointer :: items(:)?

    Answer

    One pointer to an array of nodes

    It is a single pointer descriptor with bounds.

  7. What does gfortran report for a component of its own type without POINTER?

    Answer

    Error: Component must have the POINTER attribute

    A record of a fixed size cannot contain itself.

  8. Why does a walk use a loop rather than recursion?

    Answer

    Every level costs a stack frame, and the stack is finite

    A long list would overflow the stack.

  9. What does the walk print for the three pushes in the program?

    Answer

    three, two, one: the list is a stack

    Each push becomes the new head.

  10. What does nullify(head) at the end of destroy give the caller?

    Answer

    A defined status: the pointer is not associated

    Without it the head would dangle.

The programs on this page were built with GNU Fortran (Alpine 15.2.0) 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev