Fortran linked lists, stacks and queues
last modified November 14, 2026
An array stores its elements next to each other, so inserting one in the middle moves everything after it. A linked list stores each value in a separate node that also holds a pointer to the next node; the values may sit anywhere in memory and the list is followed from one node to the next. Insertion and deletion are then a matter of changing two pointers, at the cost of losing direct access by index and of one allocation per value. This article builds a singly linked list from a self-referential type, adds and removes nodes, keeps the list sorted, and turns the same idea into a stack and a queue.
A node and a list
The type node contains a value and a pointer to another
node, which is legal even though the type is still being defined.
The list type keeps a pointer to the first node and a count, and its
append procedure allocates a fresh node and links it after the
last one. Because there is no index, finding the last node means walking from
the head, so an append costs time proportional to the current length.
module linked
implicit none
private
public :: node, list
type :: node
integer :: value = 0
type(node), pointer :: next => null()
end type node
type :: list
type(node), pointer :: head => null()
integer :: count = 0
contains
procedure :: append => list_append
procedure :: show => list_show
procedure :: total => list_total
procedure :: clear => list_clear
end type list
contains
subroutine list_append(self, value)
class(list), intent(inout) :: self
integer, intent(in) :: value
type(node), pointer :: cur, fresh
allocate (fresh)
fresh%value = value
if (.not. associated(self%head)) then
self%head => fresh
else
cur => self%head
do while (associated(cur%next))
cur => cur%next
end do
cur%next => fresh
end if
self%count = self%count + 1
end subroutine list_append
subroutine list_show(self)
class(list), intent(in) :: self
type(node), pointer :: cur
cur => self%head
do while (associated(cur))
write (*, '(i0, 1x)', advance='no') cur%value
cur => cur%next
end do
print *
end subroutine list_show
integer function list_total(self) result(s)
class(list), intent(in) :: self
type(node), pointer :: cur
s = 0
cur => self%head
do while (associated(cur))
s = s + cur%value
cur => cur%next
end do
end function list_total
subroutine list_clear(self)
class(list), intent(inout) :: self
type(node), pointer :: cur, nxt
cur => self%head
do while (associated(cur))
nxt => cur%next
deallocate (cur)
cur => nxt
end do
nullify (self%head)
self%count = 0
end subroutine list_clear
end module linked
program n1
use linked
implicit none
type(list) :: numbers
integer :: i
do i = 1, 5
call numbers%append(i * 10)
end do
print *, 'count:', numbers%count
call numbers%show()
print *, 'total:', numbers%total()
call numbers%clear()
print *, 'after clear:', numbers%count, associated(numbers%head)
end program n1
Five appends give a list of five nodes, the display shows the values in the
order they were added, and the total is 150. The traversal follows
next until it meets a node whose pointer is null, which is the
standard way to visit a list of unknown length. clear must save
the next pointer before deallocating the current node, since the node itself
is what held that pointer; the same order appears in every routine that frees a
whole list.
$ gfortran n1.f90 -o n1 $ ./n1 count: 5 10 20 30 40 50 total: 150 after clear: 0 F
Inserting at the head
Adding a value at the front is the cheapest operation of all: allocate a node,
point its next at the current head, and make the new node the
head. Nothing is walked and nothing is shifted. The price is that a sequence of
prepends produces the reverse of the order in which the values were supplied,
which is exactly what a stack wants.
module linked
implicit none
private
public :: node, list
type :: node
integer :: value = 0
type(node), pointer :: next => null()
end type node
type :: list
type(node), pointer :: head => null()
integer :: count = 0
contains
procedure :: prepend => list_prepend
procedure :: show => list_show
procedure :: clear => list_clear
end type list
contains
subroutine list_prepend(self, value)
class(list), intent(inout) :: self
integer, intent(in) :: value
type(node), pointer :: fresh
allocate (fresh)
fresh%value = value
fresh%next => self%head
self%head => fresh
self%count = self%count + 1
end subroutine list_prepend
subroutine list_show(self)
class(list), intent(in) :: self
type(node), pointer :: cur
cur => self%head
do while (associated(cur))
write (*, '(i0, 1x)', advance='no') cur%value
cur => cur%next
end do
print *
end subroutine list_show
subroutine list_clear(self)
class(list), intent(inout) :: self
type(node), pointer :: cur, nxt
cur => self%head
do while (associated(cur))
nxt => cur%next
deallocate (cur)
cur => nxt
end do
nullify (self%head)
self%count = 0
end subroutine list_clear
end module linked
program n2
use linked
implicit none
type(list) :: numbers
integer :: i
do i = 1, 5
call numbers%prepend(i)
end do
print *, 'count:', numbers%count
call numbers%show()
call numbers%clear()
end program n2
The values 1 to 5 are prepended one after another, so the list reads 5 down to 1. Each node was allocated once and linked once, and the count is still five. Compare this with the append of the previous section: both operations are correct, but prepend does not depend on the length of the list, while append grows slower as the list grows.
$ gfortran n2.f90 -o n2 $ ./n2 count: 5 5 4 3 2 1
Deleting a node
Deletion needs two pointers: prev remembers the node before the
current one, because removing the current node means making its predecessor
point past it. The first node has no predecessor, so that case updates the head
instead. Once the links are fixed, the removed node is deallocated and the
count decreases; the order matters, since the link to the successor must be
saved before the node disappears.
module linked
implicit none
private
public :: node, list
type :: node
integer :: value = 0
type(node), pointer :: next => null()
end type node
type :: list
type(node), pointer :: head => null()
integer :: count = 0
contains
procedure :: append => list_append
procedure :: remove => list_remove
procedure :: show => list_show
procedure :: clear => list_clear
end type list
contains
subroutine list_append(self, value)
class(list), intent(inout) :: self
integer, intent(in) :: value
type(node), pointer :: cur, fresh
allocate (fresh)
fresh%value = value
if (.not. associated(self%head)) then
self%head => fresh
else
cur => self%head
do while (associated(cur%next))
cur => cur%next
end do
cur%next => fresh
end if
self%count = self%count + 1
end subroutine list_append
subroutine list_remove(self, value)
class(list), intent(inout) :: self
integer, intent(in) :: value
type(node), pointer :: cur, prev, dead
prev => null()
cur => self%head
do while (associated(cur))
if (cur%value == value) then
if (associated(prev)) then
prev%next => cur%next
else
self%head => cur%next
end if
dead => cur
cur => cur%next
deallocate (dead)
self%count = self%count - 1
return
end if
prev => cur
cur => cur%next
end do
end subroutine list_remove
subroutine list_show(self)
class(list), intent(in) :: self
type(node), pointer :: cur
cur => self%head
do while (associated(cur))
write (*, '(i0, 1x)', advance='no') cur%value
cur => cur%next
end do
print *
end subroutine list_show
subroutine list_clear(self)
class(list), intent(inout) :: self
type(node), pointer :: cur, nxt
cur => self%head
do while (associated(cur))
nxt => cur%next
deallocate (cur)
cur => nxt
end do
nullify (self%head)
self%count = 0
end subroutine list_clear
end module linked
program n3
use linked
implicit none
type(list) :: numbers
integer :: i
do i = 1, 6
call numbers%append(i)
end do
call numbers%show()
call numbers%remove(1)
print *, 'removed head 1:'
call numbers%show()
call numbers%remove(4)
print *, 'removed middle 4:'
call numbers%show()
call numbers%remove(6)
print *, 'removed tail 6:'
call numbers%show()
print *, 'count:', numbers%count
call numbers%remove(99)
print *, 'remove missing, count:', numbers%count
call numbers%clear()
end program n3
Removing the first, a middle and the last value all work, and a value that is
not in the list leaves the count at three. The routine returns as soon as it
deletes one node, so several copies of the same value need several calls. Note
that prev starts as a null pointer rather than as some arbitrary
node, because the test associated(prev) is what distinguishes the
head case from the rest.
$ gfortran n3.f90 -o n3 $ ./n3 1 2 3 4 5 6 removed head 1: 2 3 4 5 6 removed middle 4: 2 3 5 6 removed tail 6: 2 3 5 count: 3 remove missing, count: 3
Keeping the list sorted
Insertion into a sorted list combines the walk of append with the
two-pointer technique of deletion: the walk stops at the first node whose value
is not smaller than the new one, and the new node is linked between
prev and cur. When no such node exists the new value
goes at the end, and when the walk stops at the head the head itself is
replaced. One rule covers all three cases.
module linked
implicit none
private
public :: node, list
type :: node
integer :: value = 0
type(node), pointer :: next => null()
end type node
type :: list
type(node), pointer :: head => null()
integer :: count = 0
contains
procedure :: insert => list_insert
procedure :: show => list_show
procedure :: clear => list_clear
end type list
contains
subroutine list_insert(self, value)
class(list), intent(inout) :: self
integer, intent(in) :: value
type(node), pointer :: cur, prev, fresh
prev => null()
cur => self%head
do while (associated(cur))
if (cur%value >= value) exit
prev => cur
cur => cur%next
end do
allocate (fresh)
fresh%value = value
fresh%next => cur
if (associated(prev)) then
prev%next => fresh
else
self%head => fresh
end if
self%count = self%count + 1
end subroutine list_insert
subroutine list_show(self)
class(list), intent(in) :: self
type(node), pointer :: cur
cur => self%head
do while (associated(cur))
write (*, '(i0, 1x)', advance='no') cur%value
cur => cur%next
end do
print *
end subroutine list_show
subroutine list_clear(self)
class(list), intent(inout) :: self
type(node), pointer :: cur, nxt
cur => self%head
do while (associated(cur))
nxt => cur%next
deallocate (cur)
cur => nxt
end do
nullify (self%head)
self%count = 0
end subroutine list_clear
end module linked
program n4
use linked
implicit none
type(list) :: sorted
integer :: value
do value = 1, 5
call sorted%insert(value * 10)
end do
call sorted%insert(25)
call sorted%insert(5)
call sorted%insert(99)
print *, 'count:', sorted%count
call sorted%show()
call sorted%clear()
end program n4
The eight values come out in ascending order even though they were inserted in an arbitrary order: 5 becomes the new head, 25 lands between 20 and 30, and 99 goes to the end. Equal values would be kept apart as well, each in a node of its own, because the walk stops only at a value that is not smaller. A sorted list gives up the fast append but makes the smallest value available at the head, which is the basis of a priority queue when the number of values is small.
$ gfortran n4.f90 -o n4 $ ./n4 count: 8 5 10 20 25 30 40 50 99
A stack
A stack is a list that only grows and shrinks at one end: the last value pushed is the first one popped, a rule known as LIFO, for last in, first out. With a linked list the top of the stack is simply the head, so push is a prepend and pop removes the head and returns its value. The array-based stack of the type-bound procedures article keeps the same rule with a fixed capacity; this version grows with the data.
module stackmod
implicit none
private
public :: node, stack
type :: node
integer :: value = 0
type(node), pointer :: next => null()
end type node
type :: stack
type(node), pointer :: top => null()
integer :: count = 0
contains
procedure :: push => stack_push
procedure :: pop => stack_pop
procedure :: show => stack_show
procedure :: clear => stack_clear
end type stack
contains
subroutine stack_push(self, value)
class(stack), intent(inout) :: self
integer, intent(in) :: value
type(node), pointer :: fresh
allocate (fresh)
fresh%value = value
fresh%next => self%top
self%top => fresh
self%count = self%count + 1
end subroutine stack_push
integer function stack_pop(self) result(value)
class(stack), intent(inout) :: self
type(node), pointer :: dead
if (.not. associated(self%top)) then
print *, 'pop from empty stack'
value = -1
return
end if
value = self%top%value
dead => self%top
self%top => self%top%next
deallocate (dead)
self%count = self%count - 1
end function stack_pop
subroutine stack_show(self)
class(stack), intent(in) :: self
type(node), pointer :: cur
cur => self%top
do while (associated(cur))
write (*, '(i0, 1x)', advance='no') cur%value
cur => cur%next
end do
print *
end subroutine stack_show
subroutine stack_clear(self)
class(stack), intent(inout) :: self
type(node), pointer :: cur, nxt
cur => self%top
do while (associated(cur))
nxt => cur%next
deallocate (cur)
cur => nxt
end do
nullify (self%top)
self%count = 0
end subroutine stack_clear
end module stackmod
program n5
use stackmod
implicit none
type(stack) :: s
integer :: i
do i = 1, 4
call s%push(i * i)
end do
print *, 'size:', s%count
call s%show()
print *, 'pop:', s%pop()
print *, 'pop:', s%pop()
print *, 'size:', s%count
call s%show()
call s%clear()
end program n5
Four squares are pushed and the stack prints them from top to bottom, so 16
comes first. The two pops return 16 and 9, and the remaining stack shows 4 and
1. Popping from an empty stack is guarded by an associated test
that returns a sentinel value; a production program would rather return a
logical status alongside the value, so that a legitimate value can never be
confused with the sentinel.
$ gfortran n5.f90 -o n5 $ ./n5 size: 4 16 9 4 1 pop: 16 pop: 9 size: 2 4 1
A queue
A queue is the opposite rule: the first value added is the first one
removed, or FIFO for first in, first out. A list with only a head pointer would
make every enqueue walk to the end, so the queue keeps a tail
pointer as well. Adding a value links it after the tail and moves the tail
forward, both in constant time; removing a value takes the head and moves it to
the next node, and an empty queue has both pointers null.
module queuemod
implicit none
private
public :: node, queue
type :: node
integer :: value = 0
type(node), pointer :: next => null()
end type node
type :: queue
type(node), pointer :: head => null(), tail => null()
integer :: count = 0
contains
procedure :: enqueue => queue_enqueue
procedure :: dequeue => queue_dequeue
procedure :: show => queue_show
procedure :: clear => queue_clear
end type queue
contains
subroutine queue_enqueue(self, value)
class(queue), intent(inout) :: self
integer, intent(in) :: value
type(node), pointer :: fresh
allocate (fresh)
fresh%value = value
if (.not. associated(self%head)) then
self%head => fresh
else
self%tail%next => fresh
end if
self%tail => fresh
self%count = self%count + 1
end subroutine queue_enqueue
integer function queue_dequeue(self) result(value)
class(queue), intent(inout) :: self
type(node), pointer :: dead
if (.not. associated(self%head)) then
print *, 'dequeue from empty queue'
value = -1
return
end if
value = self%head%value
dead => self%head
self%head => self%head%next
deallocate (dead)
if (.not. associated(self%head)) nullify (self%tail)
self%count = self%count - 1
end function queue_dequeue
subroutine queue_show(self)
class(queue), intent(in) :: self
type(node), pointer :: cur
cur => self%head
do while (associated(cur))
write (*, '(i0, 1x)', advance='no') cur%value
cur => cur%next
end do
print *
end subroutine queue_show
subroutine queue_clear(self)
class(queue), intent(inout) :: self
type(node), pointer :: cur, nxt
cur => self%head
do while (associated(cur))
nxt => cur%next
deallocate (cur)
cur => nxt
end do
nullify (self%head, self%tail)
self%count = 0
end subroutine queue_clear
end module queuemod
program n6
use queuemod
implicit none
type(queue) :: q
integer :: i
do i = 1, 4
call q%enqueue(i)
end do
print *, 'size:', q%count
call q%show()
print *, 'dequeue:', q%dequeue()
print *, 'dequeue:', q%dequeue()
call q%enqueue(5)
call q%show()
print *, 'size:', q%count
call q%clear()
print *, 'empty:', .not. associated(q%head)
end program n6
The queue starts with 1 to 4, gives back 1 and 2, and then accepts 5 at the end, so the display shows 3, 4, 5. The tail pointer is what makes the enqueue independent of the queue length, and nullifying it when the last node leaves is what keeps the structure consistent. A queue is the natural container for print jobs, breadth-first searches and any producer that must be served in arrival order.
$ gfortran n6.f90 -o n6 $ ./n6 size: 4 1 2 3 4 dequeue: 1 dequeue: 2 3 4 5 size: 3 empty: T
Reversing a list in place
Reversing a linked list needs no new nodes and no second list. Three pointers
walk the list once: cur is the node being processed,
nxt saves its successor, and prev is the part of the
list already reversed. Each step turns one next pointer around,
and after the last node prev points at the new head.
module linked
implicit none
private
public :: node, list
type :: node
integer :: value = 0
type(node), pointer :: next => null()
end type node
type :: list
type(node), pointer :: head => null()
integer :: count = 0
contains
procedure :: append => list_append
procedure :: reverse => list_reverse
procedure :: show => list_show
procedure :: clear => list_clear
end type list
contains
subroutine list_append(self, value)
class(list), intent(inout) :: self
integer, intent(in) :: value
type(node), pointer :: cur, fresh
allocate (fresh)
fresh%value = value
if (.not. associated(self%head)) then
self%head => fresh
else
cur => self%head
do while (associated(cur%next))
cur => cur%next
end do
cur%next => fresh
end if
self%count = self%count + 1
end subroutine list_append
subroutine list_reverse(self)
class(list), intent(inout) :: self
type(node), pointer :: cur, prev, nxt
prev => null()
cur => self%head
do while (associated(cur))
nxt => cur%next
cur%next => prev
prev => cur
cur => nxt
end do
self%head => prev
end subroutine list_reverse
subroutine list_show(self)
class(list), intent(in) :: self
type(node), pointer :: cur
cur => self%head
do while (associated(cur))
write (*, '(i0, 1x)', advance='no') cur%value
cur => cur%next
end do
print *
end subroutine list_show
subroutine list_clear(self)
class(list), intent(inout) :: self
type(node), pointer :: cur, nxt
cur => self%head
do while (associated(cur))
nxt => cur%next
deallocate (cur)
cur => nxt
end do
nullify (self%head)
self%count = 0
end subroutine list_clear
end module linked
program n7
use linked
implicit none
type(list) :: numbers
integer :: i
do i = 1, 5
call numbers%append(i)
end do
call numbers%show()
call numbers%reverse()
print *, 'reversed:'
call numbers%show()
call numbers%reverse()
print *, 'reversed again:'
call numbers%show()
call numbers%clear()
end program n7
The first reversal turns 1, 2, 3, 4, 5 into 5, 4, 3, 2, 1, and the second restores the original order, which shows that the operation is its own inverse. Every assignment changes only a pointer, so the values never move. The loop is the same shape as a traversal, with the extra statement that redirects each link before moving on.
$ gfortran n7.f90 -o n7 $ ./n7 1 2 3 4 5 reversed: 5 4 3 2 1 reversed again: 1 2 3 4 5
Next steps
The pointers article explains the association,
associated and nullify statements that every routine
here relies on, and the type-bound
procedures article shows the array-based stack whose interface this one
copies. The binary trees article builds a
search tree from the same node idea, with two pointers per node instead of one,
and the derived types article covers the
components and constructors used to create the nodes.
Source
Fortran 2018 standard (J3/18-007r1)
Fortran-lang: learning resources
In this article we have defined a self-referential node type, appended, prepended, deleted and inserted values while keeping the links correct, freed a whole list node by node, built a stack and a queue on the same structure, and reversed a list by turning its pointers around. The previous article, Fortran pointers, introduces the pointer assignment and the association tests used here.
Author
List all Fortran tutorials.