1.5.1 Pseudocode

There is a difference between knowing a programming language and understanding programming itself. The ultimate goal of studying data structures and algorithms is to develop programming skills, regardless of the language used.

To keep our examples accessible, this book uses pseudocode rather than a specific programming language like Python or Java. Pseudocode provides a structured yet informal way to describe algorithms, focusing on logic and flow without strict syntax rules. Its simplicity and use of common programming constructs, such as loops and conditionals, make it easy to understand and translate into actual code. The pseudocode in this book is designed to be straightforward to convert into real programming languages.

In the following sections, we will introduce fundamental programming concepts and, where applicable, specify the pseudocode conventions we use. For example, the following function is written in our pseudocode calculates the factorial of $n$:

function fact(n: Int) -> Int:
    res = 1
    for i = 2 to n:
        res = res * i
    return res

Our pseudocode includes the fundamental components of a programming language.

Variables

A variable is a name for a value, for which we use lower case alphabetic characters and allow underscore and numbers. A variable can have a type, but we don’t specify it when it does not matter or is evident from the context. We use the following notation: var: <type>. Note that type names begin with a capital letter.

Examples: res, n: Int, i, b0: Bool, intermediate_result

Types

A type defines a set of values along with the operations (or functions) that can be performed on them. For example, the Boolean type consists of the values true and false. Data types can be categorised as primitive or compound. Primitive types represent basic values, while compound types, such as arrays, tuples, and lists, are constructed using other types. For instance, an array is always an array of a specific type.

In our pseudocode, we sometimes use type variables to indicate that a compound data type is parameterised by another type. For example, List of A represents a list containing elements of some type A. To distinguish type variables, we use capital letters.

Examples: the primitive type Int or Bool, or the collection type Array of Bool

Literals

A literal is the representation of a value in concrete syntax (that is, in the source code). The value that a literal represents has a specific type.

Examples: the integer 1, the character '1', the floating point number 1.0, the boolean false

Operators

An operator is a symbol or keyword that represents an action or computation to be performed on one or more operands (which can be values or variables). The application of an operator is usually written infix, that is, the name of the operation is written between its operands. The mathematical operators have the usual precedence and in case of equal precedence we treat the as left associative.

Examples: +, *, %, <

Note that we use == for the equality operator, and = for assignment.

Expressions

An expression can be a variable, a literal, or an operation (or function) applied to one or more expressions, ultimately producing a value.

Examples: 1 + 2, true && false, (1 + 2) * n

Statements

We have the following kind of statements:

• Declaration: to declare a variable with a given name and value, and an optional type.
• Assignment: to assign a value to a variable.
• Conditional: execute a block of statements depending on a boolean expression, we use the common if-then or if-then-else statements.
• Loop: iteratively execute a block of statements, see below.
• Return: a return halts the execution of a function and returns a value to the caller of the function.

for i in 0 .. n-1:
    for j in i+1 .. n:
        do something with i and j

1.5.2 Data types

As mentioned earlier, a data type consists of a set of values and the operations that can be performed on them. Primitive data types are basic types provided by a programming language (including our pseudocode) and cannot be user-defined. Some data structures, such as arrays and lists, are built into many languages and organise collections of values, while compound data types, such as classes or algebraic data types, allow users to define their own structures. The next sections introduce the data types used in this book.

// Make a copy of the input array, and increment every value in the copied array.
// Return the copied array.
function addOne(input: Array of Int) -> Array of Int:
    output = new Array(input.size) of Int
    for i in 0 .. input.size-1:
        output[i] = input[i] + 1
    return output

a = new Array(3) of Int
a[0] = 10

b = a        // 'b' now refers to the same array as 'a'
b[0] = 20

print(a[0])  // Outputs 20, because 'a' and 'b' point to the same array

point = (3, 4)                // A tuple with two elements
person = ("Geert", 30, True)  // A tuple with different data types
print(point[0])               // Accessing first element
point[0] = 5                  // This is not allowed, tuples are immutable

1.5.3 Mutable and immutable data

For many algorithms, the ability to use mutable data can lead to more efficient solutions. However, mutability comes with its drawbacks: it increases the risk of making mistakes, and immutable data is often easier to reason about and debug.

In our pseudocode, we assume the following data types are immutable:

• Primitive data types (such as integers and characters),
• Strings
• Tuples

On the other hand, the following data types are mutable:

• Arrays
• Compound data types (see below)

1.5.4 Functions

We have already seen several examples of functions. A function starts with the keyword function, followed by its name. Functions can have zero or more parameters, and we assume a call-by-value evaluation strategy.

It is important to note that collection types (such as arrays) and compound data types are reference types. When assigning an array or a compound data type to a variable, what gets stored is a reference to the actual data, not a copy of the data itself. This means that if you pass an array as an argument to a function, the reference is copied, not the entire array. As a result, any modifications made to the array inside the function will persist when the function returns.

Functions can also be recursive, meaning they call themselves within their own body. Recursion is often used in divide-and-conquer algorithms, though it is not limited to them. When analysing recursive functions, it is important to remember that function calls are not free – they consume memory on the stack, which can become a limiting factor if recursion depth is too large.

1.5.5 Interfaces

In our pseudocode, we introduce the concept of an interface to distinguish between an abstract data type (ADT) and its concrete implementation. An interface defines a set of operations that a data type must support, without specifying how those operations are implemented. This allows us to describe the behaviour of a data type separately from its internal representation.

An abstract data type (ADT) is a high-level description of a data structure that focuses on what operations are available rather than how they are executed. For example, an ADT for a stack may define operations such as push and pop,but it does not specify whether the stack is implemented using an array or a linked list. A concrete implementation provides the actual data structure and the logic for performing the operations defined in the interface. Different implementations of the same interface can exist, each with different performance characteristics.

We use the following notation for interfaces in our pseudocode:

interface Stack of T:
    push(value: T)
    pop() -> T

Using an interface, we can define a data type’s expected behaviour and provide multiple implementations in our pseudocode. By using interfaces, we clarify the conceptual structure of a data type, making it easier to explain, compare, and analyse different implementations.

1.5.6 Compound data types

We often need to combine different data types to store complex information. These are known as compound data types. Nearly every programming language supports compound data types, although the specific implementation can vary between languages. For example, in Java, compound data types are typically created using classes, which allow you to combine instance variables of potentially different types. In Python, you can achieve this using classes, dataclasses, or dictionaries. In functional programming languages, such as Haskell, you can define algebraic data types to combine values in various ways.

Our goal is to keep things simple and explain the concept in a way that can be easily translated into the syntax of any programming language you prefer. For this reason, we have adopted a straightforward notation for compound data types in our pseudocode. Here is an example of how to define a dynamic array (see Section 6.7):

datatype ArrayStack of T implements Stack of T:
    data: Array of T
    size: int = 0

    constructor ArrayStack(capacity):
        data = new Array(capacity) of T

A datatype can also have “internal functions” (called methods in object-oriented languages), and they have access to the internal variables:

datatype ArrayStack ...:
    (...)

    push(value: T):
        data[size] = value
        size = size + 1

    pop() -> T:
        size = size - 1
        return data[size]

This example uses an array to store the stack elements and demonstrates how to define a compound data type. We define a new compound data type using the keyword datatype. A datatype can implement an interface, making it a subtype of the interface.

Note that we usually don’t write the keyword function when it appears within a datatype definition.

To create a concrete instance of a datatype, we use the following notation:

stack: Stack of Int = new ArrayStack(100) of Int

We can then call member functions like this:

next = stack.pop()

datatype ArrayStack(capacity) implements Stack:
    data: Array = new Array(capacity)
    size: int = 0

datatype ListNode of T:
    value: T
    next:  ListNode of T

datatype ListNode of T:
    value: T
    next:  ListNode of T

    constructor(value, next):
        value = value
        next = next

datatype DoubleNode extends ListNode:
    ...
    prev: ListNode

datatype TreeNode:
    value
    left:  TreeNode = null
    right: TreeNode = null

datatype TreeNode of T:
    value: T
    left:  TreeNode of T
    right: TreeNode of T

    constructor TreeNode(value, left=null, right=null):
        value = value
        left  = left
        right = right

datatype TreeNode:
    (...)

    // Return true if a node doesn't have any children.
    isLeaf() -> Bool:
        return left is null and right is null

    // Return the number of nodes, including myself.
    treeSize() -> Int:
        n = 1
        if left is not null:
            n = n + left.treeSize()
        if right is not null:
            n = n + right.treeSize()
        return n

function treeSize(node: TreeNode) -> Int:
    if node is null:
        return 0
    else:
        return 1 + treeSize(node.left) + treeSize(node.right)

1.5.7 Computer memory

To run a program we need to first load the program in memory before we can start executing. A program uses memory as well to store information that it needs for calculations. A program has access to two different memory regions: the stack and the heap. The stack is a memory region that stores local variables, function call information, and return values. When a function is called, its local variables and return address are pushed onto the stack, and when the function exits, they are removed. Since the stack follows a last-in, first-out (LIFO) order, memory allocation and deallocation happen in a predictable way, making it efficient.

The heap, on the other hand, is a more flexible memory area used for dynamic allocation. Memory allocated on the heap persists until explicitly freed or garbage-collected, making it useful for objects with longer lifetimes. Unlike the stack, the heap does not follow a strict order for allocation and deallocation, which can lead to fragmentation and slower access times. While stack allocation is fast and automatic, heap allocation requires more overhead and manual memory management.

The stack and heap are part of the so called internal memory and consists of high-speed storage components like Random Access Memory (RAM) and cache that are directly accessible by the CPU. This memory is volatile, meaning data is lost when power is turned off, and is used to store actively running programs and data. Because of its speed, internal memory is important for efficient program execution.

External memory, or secondary storage, includes non-volatile devices such as hard drives, solid-state drives, and USB storage. Unlike internal memory, it persists data even when the system is powered off and is used for long-term storage. External memory usually has a much larger capacity than internal memory, but it is significantly slower because data must be fetched and loaded into RAM before it can be processed.