Chapter 14: Pointers and Dynamic Memory — Understanding the Heap

"A pointer is an address. An address is a number. A number is something we understand. Do not be afraid." — Adapted from common Pascal teaching wisdom

Every program we have written so far has a limitation we have not yet confronted. When we declared an array of 100 elements in Chapter 9, we committed to exactly 100 slots — no more, no less. When we defined a record in Chapter 11, each variable held exactly one record. The compiler knew, before our program ever ran, precisely how much memory every variable would occupy and exactly when that memory would appear and vanish. This is static allocation, and it has served us well. But it cannot serve us forever.

What happens when a user wants to store 10 expenses today and 10,000 tomorrow? What happens when we need a data structure that grows and shrinks as the program runs? What happens when the size of our data is not known — and cannot be known — until the program is already executing?

The answer is pointers and dynamic memory allocation. This chapter introduces the most powerful — and most dangerous — concept in systems programming. Pointers let us reach into the computer's memory, claim space on demand, link pieces of data together in arbitrary ways, and release that space when we are done. They are the foundation upon which linked lists, trees, graphs, and virtually every sophisticated data structure is built.

This is a threshold concept. Once you understand pointers and indirection, you will see programming differently. The mental model you build here — of memory as a landscape of numbered addresses, of variables as labels on those addresses, of pointers as arrows from one address to another — will transfer to every language you ever learn: C, C++, Rust, Go, Java, Python. Pascal's pointer system is deliberately simpler and safer than C's, which makes it the ideal place to build that mental model for the first time.

Let us begin.

14.1 Why Pointers? The Limitations of Static Allocation

Consider the programs we have written in previous chapters. Every variable we declared — whether an integer, a string, an array of records, or a set — followed the same lifecycle:

1. The compiler sees the declaration.
2. The compiler calculates exactly how many bytes that variable needs.
3. When the variable's scope is entered at runtime (a procedure is called, or the program begins), those bytes are allocated automatically.
4. When the scope is exited, the bytes are released automatically.

This is clean, safe, and efficient. The compiler handles everything. But it imposes three constraints that become increasingly painful as programs grow in complexity:

Constraint 1: Fixed Size. An array[1..1000] of Integer always occupies space for 1,000 integers, even if the user only enters 3. Conversely, if the user needs 1,001, the program cannot accommodate them. We must guess a maximum at compile time and live with that guess.

Constraint 2: Fixed Lifetime. A local variable exists from the moment its procedure is called until the moment that procedure returns. We cannot create a piece of data inside a procedure and have it survive after the procedure ends — not without copying it into a global variable, which introduces its own problems.

Constraint 3: Fixed Relationships. With static variables, the relationships between data items are determined by their position in arrays or their fields in records. We cannot easily say "this record points to that record" or "these records form a chain." We can use array indices as crude stand-ins for pointers, but this is clumsy, error-prone, and limited.

Pointers remove all three constraints. With a pointer, we can:

• Allocate memory at runtime, requesting exactly as much space as we need, when we need it.
• Control the lifetime of data, keeping it alive as long as we want, regardless of which procedure created it.
• Create arbitrary links between data items, building chains, trees, networks, and other structures that would be impossible or impractical with arrays alone.

The price is responsibility. When the compiler managed memory for us, it could guarantee that every byte allocated would eventually be freed, that no variable would be used after its memory was reclaimed, and that every variable would be initialized before use. With pointers, all of these guarantees disappear. We must allocate. We must free. We must avoid using memory after it has been freed. The compiler will not save us. This is why pointer bugs — memory leaks, dangling pointers, null dereferences — are among the most common and most difficult bugs in all of software engineering.

Pascal was designed by Niklaus Wirth to be a teaching language, and its pointer system reflects this. Pascal pointers are typed (a pointer to an integer cannot accidentally be used as a pointer to a string), bounded (there is no pointer arithmetic that lets you wander into arbitrary memory), and explicit (you must consciously allocate and free). This makes Pascal an excellent environment in which to learn the concepts before encountering the wilder world of C and C++.

💡 Insight: Pascal's pointer restrictions are not limitations — they are guardrails. Master pointers here, and you will have the discipline to handle them safely in any language.

14.2 Memory Layout: Stack vs. Heap

Before we can understand pointers, we need a clear mental model of how a running program's memory is organized. When your compiled Pascal program executes, the operating system gives it a block of memory. That memory is divided, conceptually, into several regions. The two most important for our purposes are the stack and the heap.

The Stack

The stack is the region of memory used for local variables, parameters, and return addresses. Every time a procedure or function is called, a new stack frame is pushed onto the stack. That frame contains space for all the procedure's local variables and parameters. When the procedure returns, its frame is popped off the stack, and the memory is instantly reclaimed.

┌─────────────────────────┐  ← Top of stack (grows downward)
│  Local vars of Proc C   │  ← Current frame
├─────────────────────────┤
│  Local vars of Proc B   │  ← Caller's frame
├─────────────────────────┤
│  Local vars of Proc A   │  ← Grandcaller's frame
├─────────────────────────┤
│  Global / main vars     │  ← Bottom of stack
└─────────────────────────┘

The stack is fast (allocation and deallocation are just moving a pointer up or down), automatic (the compiler generates all the push/pop code), and deterministic (you always know when memory will be freed — when the procedure returns). But the stack is also limited in size (typically 1 to 8 megabytes) and rigid (everything on the stack lives and dies with its enclosing scope).

If you recall Chapter 8's discussion of recursion and the call stack, you already understand this model. Each recursive call adds a frame; each return removes one. A stack overflow occurs when there are too many frames for the stack's limited memory.

The Heap

The heap is the region of memory used for dynamically allocated data — data that the programmer explicitly requests at runtime and explicitly releases when done. The heap is typically much larger than the stack (hundreds of megabytes to gigabytes), and data on the heap has no automatic lifetime. It exists from the moment you allocate it until the moment you free it, regardless of which procedures are active.

┌─────────────────────────┐
│                         │
│       HEAP              │  ← Dynamic memory (grows as needed)
│   ┌───┐   ┌───┐        │
│   │ A │   │ B │        │  ← Allocated blocks (may not be contiguous)
│   └───┘   └───┘        │
│         ┌───┐           │
│         │ C │           │
│         └───┘           │
│                         │
├─────────────────────────┤
│       (free space)      │
├─────────────────────────┤
│       STACK             │  ← Automatic memory (see above)
└─────────────────────────┘

Key differences between stack and heap:

When we use New to allocate memory, we are claiming a block on the heap. When we use Dispose to free it, we are returning that block to the heap's free list. The pointer variable itself — the variable that holds the address of the heap block — lives on the stack (or in global memory). This is a crucial distinction: the pointer is on the stack; the data it points to is on the heap.

STACK                        HEAP
┌──────────┐                ┌──────────┐
│ p: ──────────────────────►│ 42       │
│ (address)│                │ (Integer)│
└──────────┘                └──────────┘

In this diagram, p is a pointer variable sitting on the stack. It contains an address — a number — that refers to a location on the heap where the integer value 42 is stored. The arrow represents the indirection: p does not contain 42; p points to 42.

A Concrete Example: Where Does Everything Live?

Let us trace a short program and identify exactly what lives where:

program MemoryMap;
var
  x: Integer;          { Global — lives in the data segment (similar to stack) }
  p: ^Integer;         { Global pointer — lives in the data segment }

procedure DoWork;
var
  localY: Integer;     { Local — lives on the stack, in DoWork's frame }
  q: ^Integer;         { Local pointer — lives on the stack }
begin
  localY := 10;
  New(q);              { q (on stack) now points to a heap block }
  q^ := localY;       { The heap block contains 10 }
  Dispose(q);          { Heap block is freed; q is dangling }
  q := nil;            { q is safe again }
end;                   { localY and q are destroyed (stack frame popped) }

begin
  x := 5;
  New(p);              { p points to a heap block }
  p^ := x;            { Heap block contains 5 }
  DoWork;              { DoWork's frame is pushed, then popped }
  Dispose(p);          { Heap block freed }
  p := nil;
end.

When DoWork is executing, the memory layout looks like this:

DATA SEGMENT               STACK (DoWork frame)        HEAP
┌──────────┐              ┌──────────┐                ┌──────┐
│ x = 5    │              │ localY=10│                │  5   │ ← p points here
│ p: ──────────────────────────────────────────────► └──────┘
└──────────┘              │ q: ────────────────────► ┌──────┐
                          └──────────┘                │ 10   │
                                                      └──────┘

After DoWork returns, its stack frame (containing localY and q) is destroyed. But the heap block that p points to survives — because heap data has no connection to any particular stack frame. This is precisely the power that heap allocation gives us: data that outlives the procedure that created it.

Heap Fragmentation

One important concept is heap fragmentation. On the stack, memory is allocated and freed in strict last-in-first-out (LIFO) order, so there are never gaps. On the heap, blocks can be allocated and freed in any order. Over time, this can create a pattern like this:

HEAP:  [USED][free][USED][free][free][USED][free][USED]

Even though there may be plenty of total free memory, it may be broken into small pieces that are too small individually to satisfy a large allocation request. This is fragmentation, and it is one reason why heap allocation is slower and more complex than stack allocation. The heap manager must search for a suitable free block, possibly splitting or merging blocks. This overhead is the price we pay for flexibility.

📊 Spaced Review (from Chapter 8): Draw the call stack for a program where Main calls ProcA, which calls ProcB, which calls ProcC. How many stack frames exist when execution is inside ProcC? (Answer: four — Main, ProcA, ProcB, ProcC.)

14.3 Declaring Pointer Types

In Pascal, a pointer is declared using the caret (^) symbol. The syntax is:

type
  PInteger = ^Integer;      { Pointer to an Integer }

This declares a new type, PInteger, which is "pointer to Integer." A variable of type PInteger does not store an integer value — it stores the memory address of an integer value.

The Naming Convention

By convention in Pascal (and enforced as a community standard in Free Pascal), pointer type names begin with the letter P, and the record types they point to begin with T:

type
  PStudent = ^TStudent;     { Pointer to a TStudent record }
  TStudent = record
    Name: string[50];
    GPA: Real;
  end;

Notice something remarkable here: PStudent is declared before TStudent, and it refers to TStudent in its definition. This is the one place in Pascal where a forward reference is legal — a pointer type can refer to a record type that has not yet been declared, as long as both declarations appear in the same type block. This forward reference capability is essential, because without it, we could never declare a record that contains a pointer to itself (which is exactly what we need for linked lists).

Typed vs. Untyped Pointers

The pointer types we have seen so far are typed pointers. A PInteger can only point to an Integer. A PStudent can only point to a TStudent. The compiler enforces this — you cannot assign a PInteger to a PStudent without an explicit cast.

Pascal also provides an untyped pointer type called simply Pointer:

var
  GenericPtr: Pointer;      { Can point to anything }

An untyped Pointer can hold the address of any data, but you cannot dereference it directly — you must cast it to a typed pointer first. In practice, you should almost never use untyped pointers. They exist primarily for interfacing with operating system calls and low-level libraries. Typed pointers are safer, clearer, and catch more bugs at compile time.

The nil Value

Every pointer type has a special value: nil. A pointer that equals nil does not point to any valid memory. It is the pointer equivalent of "nothing" or "nowhere."

var
  p: PInteger;
begin
  p := nil;                 { p points to nothing }
  if p = nil then
    WriteLn('Pointer is nil — no data allocated.');
end.

You should always initialize pointer variables to nil before use, and you should always check whether a pointer is nil before dereferencing it. These two habits will prevent an enormous number of bugs.

⚠️ Warning: An uninitialized pointer does not equal nil. It contains whatever garbage value happened to be in its memory location. Dereferencing an uninitialized pointer produces undefined behavior — your program might crash, or it might silently corrupt unrelated data. Always initialize.

14.4 New and Dispose: Allocating and Freeing Memory

The two fundamental operations on dynamic memory in Pascal are New (allocate) and Dispose (free).

New

The New procedure takes a typed pointer variable and allocates enough heap memory to hold the type it points to:

var
  p: PInteger;
begin
  New(p);                   { Allocate sizeof(Integer) bytes on the heap }
  { p now points to a valid (but uninitialized!) Integer on the heap }

After New(p), the pointer p contains the address of a freshly allocated block of memory on the heap. That block is large enough to hold one Integer. However, the value stored in that block is uninitialized — it contains whatever random bits happened to be in that memory region. You must assign a value before reading it:

  p^ := 42;                { Store 42 in the heap location p points to }
  WriteLn(p^);             { Prints 42 }

For records, New allocates enough space for the entire record:

var
  student: PStudent;
begin
  New(student);
  student^.Name := 'Alice';
  student^.GPA := 3.85;

Dispose

The Dispose procedure takes a pointer and frees the heap memory it points to:

  Dispose(p);               { Free the heap memory p pointed to }

After Dispose(p), the memory that p pointed to has been returned to the heap's free list. The pointer variable p itself still exists (it is a stack variable), and it still contains the old address — but that address is no longer valid. It is good practice to set the pointer to nil immediately after disposing:

  Dispose(p);
  p := nil;                 { Defensive: mark pointer as invalid }

What Happens Under the Hood

When you call New, the Pascal runtime's memory manager (Free Pascal uses a sophisticated heap manager based on the FPC heap manager or cmem) performs these steps:

1. Search the free list for a block of sufficient size.
2. Split the block if it is larger than needed (returning the excess to the free list).
3. Return the address of the allocated block, which is stored in the pointer variable.

When you call Dispose, the reverse occurs:

1. The block is marked as free and returned to the free list.
2. Adjacent free blocks may be coalesced (merged) to reduce fragmentation.
3. The memory is not zeroed — the old data remains until overwritten by a future allocation.

This is why reading from a disposed pointer sometimes appears to "work" — the old data may still be there. But this is a dangerous illusion. The memory manager may reallocate that block for a completely different purpose at any time. This is the core of the dangling pointer bug, which we will examine in detail in Section 14.8.

GetMem and FreeMem: The Low-Level Alternative

Pascal also provides a lower-level pair of memory management routines: GetMem and FreeMem. While New and Dispose work with typed pointers and always allocate exactly the right amount of memory for the declared type, GetMem and FreeMem let you specify an arbitrary number of bytes:

var
  p: Pointer;
begin
  GetMem(p, 256);       { Allocate 256 bytes of raw memory }
  { ... use the memory ... }
  FreeMem(p, 256);      { Free 256 bytes }
end.

GetMem is useful when you need to allocate a block whose size is not known at compile time — for example, when reading a variable-length record from a file, or when implementing your own memory management layer. However, GetMem sacrifices type safety: it works with untyped Pointer values, and you must remember the block size yourself.

For the vast majority of your work in this course, New and Dispose are the correct choice. They are type-safe, they handle size calculations automatically, and they make your code clearer. Reserve GetMem and FreeMem for advanced situations where you need precise control over block sizes.

The Golden Rule of Dynamic Memory

✅ Rule: Every New must have a corresponding Dispose. Every allocation must have a deallocation. Every claim on the heap must eventually be released. No exceptions.

If you allocate memory and never free it, you have a memory leak. If you free memory and then continue to use the pointer, you have a dangling pointer. If you free the same memory twice, you have a double free. All three are serious bugs. We will devote an entire section (14.8) to identifying and preventing them.

14.5 Dereferencing: The ^ Operator

The caret (^) operator in Pascal serves double duty. In a type declaration, ^Type means "pointer to Type." In an expression, Pointer^ means "the value that the pointer points to." This second usage is called dereferencing.

var
  p: ^Integer;
begin
  New(p);
  p^ := 100;               { Dereference p, store 100 at the location }
  WriteLn(p^);             { Dereference p, read the value: prints 100 }
  WriteLn(p^ + 50);       { Dereference, then add: prints 150 }
  p^ := p^ * 2;           { Read 100, multiply by 2, store 200 }
  Dispose(p);
end.

Think of the ^ as saying "follow the arrow." If p is an arrow pointing to a box containing 100, then p^ is the contents of that box.

Dereferencing Record Pointers

When a pointer points to a record, you dereference and then access fields using the dot operator:

var
  student: PStudent;
begin
  New(student);
  student^.Name := 'Bob';   { Dereference student, access Name field }
  student^.GPA := 3.2;      { Dereference student, access GPA field }
  WriteLn(student^.Name, ': ', student^.GPA:0:2);
  Dispose(student);
end.

The expression student^.Name reads as: "follow the pointer student to the record it points to, then access that record's Name field."

A Visual Model

Let us trace through a short program step by step, drawing the memory state at each point.

program PointerTrace;
var
  a, b: ^Integer;
begin
  { State 1: both pointers uninitialized (dangerous!) }

  New(a);
  { State 2: a points to an uninitialized Integer on the heap }
  { STACK: a → HEAP[?]  }

  a^ := 10;
  { State 3: the heap location now contains 10 }
  { STACK: a → HEAP[10] }

  New(b);
  b^ := 20;
  { State 4: two separate heap allocations }
  { STACK: a → HEAP[10]    b → HEAP[20] }

  b^ := a^;
  { State 5: copied the VALUE, not the pointer }
  { STACK: a → HEAP[10]    b → HEAP[10] }
  { (Two separate heap locations, both containing 10) }

  b := a;
  { State 6: copied the POINTER (the address) }
  { STACK: a → HEAP[10]    b → HEAP[10] (SAME location!) }
  { WARNING: the old HEAP[10] that b pointed to is now LEAKED! }

  Dispose(a);
  a := nil;
  { State 7: freed the shared location }
  { STACK: a = nil    b → FREED MEMORY (dangling pointer!) }

  Dispose(b);  { BUG: double free! }
end.

This example is deliberately buggy to illustrate critical concepts. Study each state transition carefully:

• State 5 vs. State 6 demonstrates the difference between copying a value (b^ := a^) and copying a pointer (b := a). This distinction is fundamental. Copying a value duplicates the data. Copying a pointer creates a second arrow to the same data — an alias.
• State 6 shows a memory leak: the old heap block that b pointed to is now unreachable. No pointer refers to it, so it can never be freed.
• State 7 shows a dangling pointer: b still holds the address of freed memory.
• The final Dispose(b) is a double free: attempting to free memory that was already freed via a.

🔗 Connection to Theme 2 (Discipline Transfers): The distinction between copying values and copying pointers exists in every programming language. In C, it is the difference between *b = *a and b = a. In Java and Python, assigning one object reference to another creates an alias, not a copy. The discipline you build here — asking "am I copying data or copying a reference?" — will prevent bugs in every language you use.

14.6 Pointer Arithmetic and Comparisons

What Pascal Allows

Standard Pascal and Free Pascal (in default mode) do not support pointer arithmetic. You cannot write:

p := p + 1;    { ILLEGAL in standard Pascal }

This is a deliberate safety feature. In C, pointer arithmetic is legal and common — you can increment a pointer to step through memory one element at a time. This power is also the source of a vast category of C bugs: buffer overflows, out-of-bounds reads, and memory corruption. Pascal's designers chose safety over power here.

Comparisons

What Pascal does allow is comparing pointers:

if p = nil then ...          { Is p a nil pointer? }
if p <> nil then ...         { Does p point to something? }
if p = q then ...            { Do p and q point to the same location? }
if p <> q then ...           { Do p and q point to different locations? }

Note that p = q tests whether two pointers contain the same address — whether they point to the same heap location. It does not compare the values at those locations. To compare values, you must dereference: p^ = q^.

New(p); New(q);
p^ := 42;
q^ := 42;
WriteLn(p = q);    { FALSE: different addresses }
WriteLn(p^ = q^);  { TRUE: same value }

Free Pascal's {$POINTERMATH} Directive

While standard Pascal forbids pointer arithmetic, Free Pascal provides a compiler directive {$POINTERMATH ON} that enables C-style pointer arithmetic for typed pointers. When enabled, you can write:

{$POINTERMATH ON}
var
  p: PInteger;
begin
  GetMem(p, 5 * SizeOf(Integer));
  p[0] := 10;
  p[1] := 20;
  p[2] := 30;
  { p + 2 points to the third element }
  FreeMem(p, 5 * SizeOf(Integer));
end.

We mention this for completeness, but we strongly recommend leaving {$POINTERMATH} off. Pointer arithmetic bypasses Pascal's safety guarantees and opens the door to the same buffer overflow bugs that plague C programs. If you need array-like behavior, use an actual array. If you need dynamic sizing, use the linked structures we are about to build.

The nil Check Pattern

The most important pointer comparison is the nil check. You should perform it before every dereference in any context where the pointer might be nil:

procedure PrintValue(p: PInteger);
begin
  if p = nil then
    WriteLn('(no value)')
  else
    WriteLn('Value: ', p^);
end;

This pattern is so common that it becomes second nature. In Chapter 15 (linked lists), you will write nil checks in virtually every procedure.

A Common Pattern: Swapping Pointers vs. Swapping Values

Understanding the difference between pointer operations and value operations is essential. Consider swapping two values through pointers:

{ Swap the VALUES that p and q point to }
procedure SwapValues(p, q: PInteger);
var
  temp: Integer;
begin
  temp := p^;
  p^ := q^;
  q^ := temp;
end;

{ Swap the POINTERS themselves }
procedure SwapPointers(var p, q: PInteger);
var
  temp: PInteger;
begin
  temp := p;
  p := q;
  q := temp;
end;

SwapValues exchanges the data in two heap locations — after the swap, each location holds what the other used to hold. SwapPointers exchanges the addresses stored in two pointer variables — after the swap, each pointer points where the other used to point. The heap data does not move. Both operations are useful, but they are fundamentally different. Drawing a box-and-arrow diagram for each will make the difference clear.

📊 Spaced Review (from Chapter 12): How are Pascal sets implemented at the machine level? (Answer: as bit vectors, where each possible element corresponds to one bit. If the bit is 1, the element is in the set; if 0, it is not.)

14.7 The @ Operator: Getting the Address of a Variable

While New creates a new heap allocation and returns its address, the @ operator returns the address of an existing variable — one that already lives on the stack or in global memory.

var
  x: Integer;
  p: PInteger;
begin
  x := 99;
  p := @x;                  { p now points to x's stack location }
  WriteLn(p^);             { Prints 99 }
  p^ := 200;               { Modifies x through the pointer }
  WriteLn(x);              { Prints 200 }
end.

Here, p does not point to the heap. It points to x on the stack. This is perfectly legal, but it carries a risk: if x goes out of scope (e.g., a procedure returns), the pointer becomes dangling. And unlike heap pointers, you must not call Dispose on a pointer obtained via @ — that memory is managed by the stack, not the heap.

When to Use @

The @ operator is most useful when:

1. Passing data to procedures that expect pointers. Some library functions and operating system APIs require pointer arguments. You can use @ to pass the address of a local variable.
2. Implementing callback patterns. When a procedure needs to modify a variable in the caller's scope, passing a pointer (via @) is one approach (though var parameters are usually preferred in Pascal).
3. Interfacing with C libraries. When calling external C functions from Free Pascal, you often need to pass addresses of Pascal variables.

When NOT to Use @

Do not use @ to create a pointer that outlives the variable it points to. This is a classic source of dangling pointers:

function DangerousPointer: PInteger;
var
  local: Integer;
begin
  local := 42;
  DangerousPointer := @local;  { BUG: local will be destroyed on return }
end;

The pointer returned by this function points to a stack location that is freed the moment the function returns. Using the returned pointer produces undefined behavior.

⚠️ Warning: Never return a pointer obtained via @ from a function if the pointed-to variable is local to that function. Use New to allocate on the heap instead.

14.8 Common Pointer Bugs

Pointer bugs are notoriously difficult to debug because their symptoms often appear far from their cause. A memory leak may not cause a crash for hours. A dangling pointer may work correctly 99 times and crash on the 100th. Let us catalog the four most common pointer bugs, learn to recognize them, and develop habits that prevent them.

Bug 1: Memory Leak

A memory leak occurs when heap memory is allocated but never freed. The memory remains claimed but unreachable — no pointer refers to it, so Dispose can never be called on it.

procedure LeakyProcedure;
var
  p: PInteger;
begin
  New(p);        { Allocate }
  p^ := 42;
  { Procedure ends without Dispose(p) — LEAK! }
end;

Every call to LeakyProcedure leaks sizeof(Integer) bytes. Call it a million times, and you have leaked megabytes. In a long-running program (a server, a game, a desktop application), memory leaks cause the program to consume more and more memory over time until it crashes or the operating system kills it.

Prevention: Ensure every New has a matching Dispose. Use a systematic approach: when you write New(p), immediately write the corresponding Dispose(p) and then fill in the code between them. In complex programs, consider writing dedicated "cleanup" or "destroy" procedures for each data structure.

Bug 2: Dangling Pointer

A dangling pointer is a pointer that refers to memory that has already been freed.

New(p);
p^ := 42;
Dispose(p);
WriteLn(p^);     { BUG: p points to freed memory }

After Dispose(p), the memory manager may reuse that block for a completely different allocation. Reading p^ might return 42 (if the memory has not been reused yet), or it might return garbage, or it might crash the program. Writing to p^ is even worse — it corrupts whatever data now occupies that memory, causing bugs that may not manifest until much later.

Prevention: Set pointers to nil immediately after calling Dispose. Then check for nil before dereferencing:

Dispose(p);
p := nil;
{ ... later ... }
if p <> nil then
  WriteLn(p^);

Bug 3: Nil Dereference

A nil dereference occurs when you attempt to access the data at a nil pointer.

var
  p: PInteger;
begin
  p := nil;
  WriteLn(p^);   { BUG: dereferencing nil — runtime error }
end.

This is actually the safest of the pointer bugs, because it (usually) causes an immediate crash with a clear error message: "Access violation" or "SIGSEGV." It is much easier to debug than a dangling pointer, which may silently corrupt data.

Prevention: Always check for nil before dereferencing, especially when dealing with pointers that might not have been initialized or might have been freed.

Bug 4: Double Free

A double free occurs when Dispose is called twice on the same heap block.

New(p);
q := p;          { q and p now point to the same block }
Dispose(p);
Dispose(q);      { BUG: double free — q points to already-freed memory }

A double free corrupts the heap manager's internal data structures. It can cause crashes, mysterious memory corruption, or security vulnerabilities. In C, double frees are a common attack vector for exploits.

Prevention: After calling Dispose, set the pointer to nil. Since Dispose(nil) is well-defined (it does nothing in most Pascal implementations), a nil check prevents accidental double frees. More fundamentally, be careful with pointer aliases: if two pointers refer to the same block, only one of them should "own" the block and be responsible for freeing it.

The Ownership Discipline

The concept of ownership is the single most powerful tool for preventing pointer bugs. The rule is simple: every heap-allocated block has exactly one owner — one pointer that is responsible for eventually calling Dispose. Other pointers may temporarily point to the same block (as aliases or "borrowers"), but they do not own it and must not free it.

This discipline is so important that Rust, a modern systems language, enforces it at the compiler level. Pascal does not enforce it, but you should follow it by convention. When you allocate with New(p), p is the owner. If you assign q := p, decide clearly: does ownership transfer to q (in which case set p := nil), or does p retain ownership (in which case q is a temporary alias that must not call Dispose)?

🔗 Connection to Theme 2 (Discipline Transfers): This ownership concept is exactly what you will encounter in C++ (std::unique_ptr), Rust (the borrow checker), and Swift (ARC). Learning it now, in Pascal, gives you a conceptual foundation that maps directly to these more advanced systems.

14.9 Building Your First Linked Structure

Now that we understand the mechanics of pointers — allocation, deallocation, dereferencing, and the bugs to avoid — we can build something meaningful. A linked structure is a collection of dynamically allocated nodes where each node contains a pointer to the next node.

The Node Type

type
  PNode = ^TNode;
  TNode = record
    Value: Integer;
    Next: PNode;
  end;

This is the forward reference we discussed in Section 14.3. PNode is declared before TNode, referring to it. TNode contains a field Next of type PNode. Each node therefore contains both data (Value) and a link to another node (Next).

Creating a Simple Chain

Let us build a chain of three nodes containing the values 10, 20, and 30:

program SimpleChain;
type
  PNode = ^TNode;
  TNode = record
    Value: Integer;
    Next: PNode;
  end;

var
  Head, Temp: PNode;
begin
  { Create first node }
  New(Head);
  Head^.Value := 10;

  { Create second node, link it }
  New(Head^.Next);
  Head^.Next^.Value := 20;

  { Create third node, link it }
  New(Head^.Next^.Next);
  Head^.Next^.Next^.Value := 30;
  Head^.Next^.Next^.Next := nil;  { Terminate the chain }

  { Traverse and print }
  Temp := Head;
  while Temp <> nil do
  begin
    WriteLn(Temp^.Value);
    Temp := Temp^.Next;
  end;

  { Free all nodes (must traverse again) }
  while Head <> nil do
  begin
    Temp := Head;
    Head := Head^.Next;
    Dispose(Temp);
  end;
end.

Let us trace the memory state after creating all three nodes:

STACK                    HEAP
┌──────┐               ┌────────────┐    ┌────────────┐    ┌────────────┐
│ Head ──────────────► │ Value: 10  │    │ Value: 20  │    │ Value: 30  │
│      │               │ Next: ─────────►│ Next: ─────────►│ Next: nil  │
└──────┘               └────────────┘    └────────────┘    └────────────┘

The traversal using Temp follows the chain of Next pointers, starting at Head and stopping when it reaches nil (the end of the chain).

The deallocation loop is more subtle. We cannot simply Dispose(Head) and move on — that would free the first node but lose our only reference to the second and third nodes (memory leak!). Instead, we must save a reference to the next node before freeing the current one:

1. Temp := Head          (save pointer to first node)
2. Head := Head^.Next    (advance Head to second node)
3. Dispose(Temp)         (free the first node)
4. Repeat until Head = nil

This pattern — save, advance, free — is the standard idiom for deallocating a linked structure. You will use it constantly in Chapter 15.

Why Not Just Use an Array?

At this point, you might reasonably ask: why go through all this complexity when an array would be simpler? For three integers, an array is indeed better. But consider:

• Variable size. A linked chain can grow to hold 10 items or 10 million items without declaring a maximum in advance.
• Efficient insertion. To insert a new node at the beginning of a chain, we allocate one node and adjust one pointer — O(1). To insert at the beginning of an array, we must shift every element — O(n).
• Efficient deletion. To remove a node from a chain, we adjust pointers and free one node — O(1) once located. To delete from an array, we must shift elements.

The trade-off is that linked structures have no random access (you cannot jump to the 5th element without traversing from the head) and use more memory per element (each node carries a pointer in addition to its data). Let us quantify the memory overhead. For our TNode record:

• Value field: 4 bytes (for a 32-bit Integer)
• Next field: 4 or 8 bytes (depending on 32-bit or 64-bit system)
• Heap manager bookkeeping: typically 8–16 bytes per allocation

So each node costs roughly 16–28 bytes to store a 4-byte integer. That is 4 to 7 times the memory of a plain array element. For large datasets of small elements, this overhead matters. For records of meaningful size (like our TExpenseRec at ~110 bytes), the pointer overhead is a small percentage.

These trade-offs are the heart of data structure design, and we will explore them thoroughly in Chapter 15 (linked lists), Chapter 16 (stacks and queues), and Chapter 17 (binary trees).

Searching a Linked Chain

Before we move on, let us implement one more fundamental operation: searching. Given a chain of nodes, we want to find the first node whose Value matches a given target:

function FindNode(Head: PNode; Target: Integer): PNode;
var
  Current: PNode;
begin
  Current := Head;
  while Current <> nil do
  begin
    if Current^.Value = Target then
    begin
      FindNode := Current;   { Found it — return a pointer to this node }
      Exit;
    end;
    Current := Current^.Next;
  end;
  FindNode := nil;            { Not found }
end;

This function returns a PNode — a pointer to the matching node. The caller can then read or modify the node's data through the returned pointer. If the target is not found, the function returns nil. Notice the familiar traversal pattern: start at Head, follow Next pointers, stop at nil.

The caller uses it like this:

var
  result: PNode;
begin
  result := FindNode(Head, 30);
  if result <> nil then
    WriteLn('Found: ', result^.Value)
  else
    WriteLn('Not found.');
end;

This search is linear — O(n) — because in the worst case, we must visit every node. There is no way to "jump to the middle" of a linked chain. This is the fundamental limitation of linked structures compared to arrays, where we can access any element by index in O(1) time. Chapter 17 will introduce binary search trees, which maintain a sorted structure that allows O(log n) search on average — the best of both worlds.

💡 Insight: The linked node is the atom from which linked lists, stacks, queues, trees, and graphs are all built. Master this simple two-field record — a value and a pointer to the next node — and you have the building block for all of them.

14.10 Pointers in Other Languages

One of the recurring themes of this textbook is that Pascal teaches you concepts that transfer. Nowhere is this more true than with pointers. Let us briefly survey how other languages handle the same ideas.

C and C++

C's pointer model is essentially Pascal's model with the safety guards removed:

C adds pointer arithmetic (you can add an integer to a pointer to step through an array) and void pointers (which can be cast to any type without the compiler objecting). These make C more flexible and more dangerous. Buffer overflows — one of the most common security vulnerabilities in all of computing — are a direct consequence of unchecked pointer arithmetic.

C++ adds smart pointers (std::unique_ptr, std::shared_ptr) that automate deallocation. A unique_ptr embodies the ownership concept from Section 14.8: it automatically calls delete when it goes out of scope, and it cannot be copied (only moved). This is essentially the compiler enforcing the discipline we practiced manually in Pascal.

Java and C

Java and C# hide pointers behind the concept of references. Every object variable is a reference (pointer) to a heap-allocated object, but you cannot see or manipulate the address directly. There is no & or @ operator, no pointer arithmetic, and no manual free/Dispose.

Instead, Java and C# use garbage collection: a runtime system that periodically scans memory, identifies heap objects that are no longer reachable by any reference, and frees them automatically. This eliminates memory leaks (mostly) and dangling pointers (entirely), but at the cost of occasional "GC pauses" where the program halts briefly while the collector runs.

Python

Python works similarly to Java: all objects are heap-allocated and accessed via references. Python uses reference counting plus a cycle-detecting garbage collector to manage memory. You never call malloc or free; memory management is entirely automatic.

However, understanding pointers is still essential for Python programmers. The distinction between copying a value and copying a reference — which we saw in Section 14.5 — is the source of one of the most common Python bugs:

a = [1, 2, 3]
b = a            # b is an alias, NOT a copy
b.append(4)
print(a)         # [1, 2, 3, 4]  — surprise!

This is exactly the same concept as b := a for pointer variables in Pascal. A Pascal programmer who has internalized the difference between b^ := a^ (copy value) and b := a (copy pointer) will immediately recognize this Python behavior.

Rust

Rust is the language that takes the ownership model from Section 14.8 and makes it a compile-time guarantee. Every value in Rust has exactly one owner. When ownership is transferred (moved), the original variable becomes invalid. References (borrows) can be immutable (many readers) or mutable (one writer), enforced by the compiler. This eliminates entire categories of bugs — dangling pointers, double frees, data races — with zero runtime overhead.

If you master the ownership discipline in Pascal, you will find Rust's borrow checker intuitive rather than frustrating.

🔗 Theme 2 (Discipline Transfers): Pascal → C (same model, fewer guards) → C++ (smart pointers automate discipline) → Rust (compiler enforces discipline). The concepts are identical; only the enforcement mechanism changes.

14.11 Project Checkpoint: PennyWise Dynamic List

It is time to apply everything we have learned. In previous chapters, PennyWise stored expenses in a fixed-size array. That worked, but it imposed a hard limit on the number of expenses. Now we will replace the array with a dynamically allocated linked list of expense records.

Design

We define our data types using the standard Pascal pointer convention:

type
  PExpenseNode = ^TExpenseNode;

  TExpenseRec = record
    Description: string[80];
    Amount: Real;
    Category: string[20];
    Day: Integer;
    Month: Integer;
    Year: Integer;
  end;

  TExpenseNode = record
    Data: TExpenseRec;
    Next: PExpenseNode;
  end;

Each TExpenseNode contains a TExpenseRec (the expense data) and a Next pointer to the next node. The list is headed by a PExpenseNode pointer called Head, initialized to nil (empty list).

Operations

Our PennyWise linked list needs four operations:

1. AddExpense — Allocate a new node, fill in the data, and insert it at the head of the list.
2. PrintAllExpenses — Traverse the list from head to tail, printing each expense.
3. TotalExpenses — Traverse the list, summing the Amount fields.
4. FreeAllExpenses — Traverse the list, disposing of every node (the save-advance-free pattern from Section 14.9).

Adding an Expense (Head Insertion)

procedure AddExpense(var Head: PExpenseNode;
                     const Desc: string; Amt: Real;
                     const Cat: string; D, M, Y: Integer);
var
  NewNode: PExpenseNode;
begin
  New(NewNode);
  NewNode^.Data.Description := Desc;
  NewNode^.Data.Amount := Amt;
  NewNode^.Data.Category := Cat;
  NewNode^.Data.Day := D;
  NewNode^.Data.Month := M;
  NewNode^.Data.Year := Y;
  NewNode^.Next := Head;   { New node points to old head }
  Head := NewNode;          { Head now points to new node }
end;

Notice that Head is a var parameter — we need to modify the caller's pointer. After this procedure, the new node is at the front of the list, and its Next pointer leads to what was previously the first node. This is O(1) — constant time, regardless of list size.

Traversing and Printing

procedure PrintAllExpenses(Head: PExpenseNode);
var
  Current: PExpenseNode;
  Count: Integer;
begin
  if Head = nil then
  begin
    WriteLn('No expenses recorded.');
    Exit;
  end;

  Count := 0;
  Current := Head;
  while Current <> nil do
  begin
    Inc(Count);
    with Current^.Data do
      WriteLn(Count:3, '. ', Description:30, ' $', Amount:8:2,
              '  [', Category, ']  ', Month, '/', Day, '/', Year);
    Current := Current^.Next;
  end;
end;

The while Current <> nil pattern is the standard linked-list traversal. We follow the chain of Next pointers until we reach nil, which marks the end.

Computing the Total

function TotalExpenses(Head: PExpenseNode): Real;
var
  Current: PExpenseNode;
  Sum: Real;
begin
  Sum := 0.0;
  Current := Head;
  while Current <> nil do
  begin
    Sum := Sum + Current^.Data.Amount;
    Current := Current^.Next;
  end;
  TotalExpenses := Sum;
end;

Freeing the Entire List

procedure FreeAllExpenses(var Head: PExpenseNode);
var
  Temp: PExpenseNode;
begin
  while Head <> nil do
  begin
    Temp := Head;
    Head := Head^.Next;
    Dispose(Temp);
  end;
  { Head is now nil — the list is empty and all memory is freed }
end;

This is the save-advance-free pattern. Head is a var parameter so that after the procedure returns, the caller's head pointer is nil.

Putting It Together

The main program creates an empty list, adds several expenses through user input (or hardcoded test data), prints them, shows the total, and then frees all memory:

var
  ExpenseList: PExpenseNode;
begin
  ExpenseList := nil;  { Empty list }

  { Add test expenses }
  AddExpense(ExpenseList, 'Groceries', 67.50, 'Food', 15, 3, 2026);
  AddExpense(ExpenseList, 'Electric bill', 142.00, 'Utilities', 1, 3, 2026);
  AddExpense(ExpenseList, 'Coffee beans', 18.99, 'Food', 10, 3, 2026);
  AddExpense(ExpenseList, 'Internet', 79.99, 'Utilities', 5, 3, 2026);

  WriteLn('=== PennyWise Expense Tracker ===');
  WriteLn;
  PrintAllExpenses(ExpenseList);
  WriteLn;
  WriteLn('Total: $', TotalExpenses(ExpenseList):0:2);

  { Clean up }
  FreeAllExpenses(ExpenseList);
  WriteLn;
  WriteLn('All memory freed. ExpenseList = nil: ',
          ExpenseList = nil);
end.

Expected output:

=== PennyWise Expense Tracker ===

  1. Internet                        $   79.99  [Utilities]  3/5/2026
  2. Coffee beans                    $   18.99  [Food]  3/10/2026
  3. Electric bill                   $  142.00  [Utilities]  3/1/2026
  4. Groceries                       $   67.50  [Food]  3/15/2026

Total: $308.48

All memory freed. ExpenseList = nil: TRUE

Notice that the expenses print in reverse order of insertion — the most recently added appears first. This is because we are inserting at the head. In Chapter 15, we will implement tail insertion and sorted insertion to give us control over ordering.

💡 Insight: We have replaced a fixed array[1..MAX_EXPENSES] with a linked list that can hold any number of expenses. The only limit is available memory. This is the power of dynamic allocation.

📊 Spaced Review (from Chapter 10): What function converts an integer to a string in Free Pascal? (Answer: Str(intValue, stringVar) or IntToStr(intValue) from the SysUtils unit.)

14.12 Chapter Summary

This chapter introduced the most consequential concept in systems programming: pointers and dynamic memory allocation. Let us review the key ideas.

Core Concepts

Memory layout. A running program's memory is divided into the stack (automatic, fast, limited, scope-bound) and the heap (manual, slower, large, programmer-controlled). Pointer variables live on the stack; the data they point to lives on the heap.

Pointer types. A pointer is declared with ^Type syntax: PInteger = ^Integer. Pointers store memory addresses. The special value nil means "points to nothing."

Allocation and deallocation. New(p) allocates heap memory and stores its address in p. Dispose(p) frees that memory. Every New must have a corresponding Dispose.

Dereferencing. The ^ operator follows a pointer to the data it points to. p^ is the value at the address stored in p. For records: p^.FieldName.

The @ operator. Returns the address of an existing variable. Use with caution — never return a pointer to a local variable.

Pointer comparison. p = q tests whether two pointers hold the same address (point to the same location). p^ = q^ tests whether the values at two locations are equal.

The Four Deadly Bugs

1. Memory leak: Allocated memory never freed. Prevention: match every New with a Dispose.
2. Dangling pointer: Using a pointer after its memory was freed. Prevention: set pointers to nil after Dispose.
3. Nil dereference: Accessing data through a nil pointer. Prevention: check p <> nil before p^.
4. Double free: Freeing the same memory twice. Prevention: ownership discipline — one owner, one free.

The Ownership Principle

Every heap-allocated block should have exactly one owner responsible for freeing it. Other pointers may temporarily reference the same block, but they do not own it and must not call Dispose on it. This discipline, practiced manually in Pascal, is automated by C++ smart pointers and enforced by Rust's compiler.

Linked Structures

A linked node — a record containing data and a pointer to the next node — is the building block of linked lists, stacks, queues, trees, and graphs. Creating a chain of nodes requires careful allocation, linking, traversal, and deallocation.

Transferable Skills

Pascal's pointer model — typed, explicit, without pointer arithmetic — is the safest environment in which to learn these concepts. The mental model you have built here (addresses, indirection, ownership, the four bugs) transfers directly to C, C++, Java, Python, Rust, and every other language you will encounter.

What Comes Next

In Chapter 15, we will take the simple linked structure from this chapter and build it into a full singly linked list with insertion, deletion, search, and sorting. In Chapter 16, we will use linked lists to implement stacks and queues. In Chapter 17, we will extend the idea to binary trees, where each node has two pointers instead of one. The journey from this chapter's humble PNode to a balanced binary search tree is shorter than you might think — it is all built from the same fundamental idea: a record, a pointer, and the discipline to manage them safely.

✅ Threshold Concept Achieved: You now understand pointers and indirection. You know that a pointer is an address, that dereferencing follows the address to the data, that heap memory must be manually managed, and that ownership discipline prevents bugs. This understanding changes how you think about every program you write. Variables are no longer abstract names — they are labels on memory locations. Data structures are no longer monolithic blocks — they are networks of nodes connected by pointers. Welcome to the other side of the threshold.

In the next chapter, we will build complete linked list operations — insertion at any position, deletion by value, searching, and counting — transforming the simple chain we built here into a versatile, production-quality data structure.