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
- Write append(head, v) that adds a node at the end instead of the front. Which case does it have to test first?
- Add a sum_nodes(head) function and print the total for the three nodes.
- Call destroy(head) twice in a row. What does the second call do, and why is it safe?
- 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.
-
Why must the
nextcomponent be a pointer?Answer
A record cannot contain itself by value, only by reference
The component has to have the POINTER attribute.
-
What does
pushdo first?Answer
Allocates a node and points its next at the current head
The link is written before the head moves.
-
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 pAnswer
2 1
b holds two and its next is the node with one.
-
Why does
destroysavecur%nextbefore deallocating?Answer
The node and its components are gone after the deallocation
The link has to be read while the node still exists.
-
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.
-
What is
type(node), pointer :: items(:)?Answer
One pointer to an array of nodes
It is a single pointer descriptor with bounds.
-
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.
-
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.
-
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.
-
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