Chapter 14 Exercises: Pointers and Dynamic Memory

Part A: Conceptual Understanding (Exercises 1–5)

Exercise 1 — Stack vs. Heap Classification For each of the following, state whether the data resides on the stack or the heap. Explain your reasoning.

a) A local variable x: Integer declared inside a procedure. b) The pointer variable p: PInteger declared inside a procedure. c) The integer value that p points to after calling New(p). d) A global variable name: string[50] declared in the main program. e) A TStudent record allocated via New(studentPtr).

Exercise 2 — Pointer vs. Value Copy Consider the following code:

var
  a, b: ^Integer;
begin
  New(a);
  New(b);
  a^ := 10;
  b^ := 20;
  a^ := b^;     { Line X }
  a := b;        { Line Y }
end.

a) After Line X executes, what value does a^ contain? What value does b^ contain? Do a and b point to the same memory location? b) After Line Y executes, do a and b point to the same memory location? Is there a memory leak? Explain.

Exercise 3 — Lifetime Analysis Draw a timeline showing when each piece of memory is allocated and freed in this program. Identify any bugs.

program LifetimeQuiz;
var
  p, q: ^Integer;
begin
  New(p);       { Event 1 }
  p^ := 5;
  q := p;       { Event 2 }
  New(p);       { Event 3 }
  p^ := 10;
  Dispose(q);   { Event 4 }
  Dispose(p);   { Event 5 }
end.

Is there a memory leak? A dangling pointer? A double free?

Exercise 4 — Forward References Explain why the following code compiles successfully, even though PNode references TNode before TNode is declared:

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

What would happen if you tried to put PNode and TNode in separate type blocks?

Exercise 5 — Ownership Identification In each scenario below, identify which pointer is the "owner" (responsible for Dispose) and which is a "borrower" (temporary alias).

a) New(p); q := p; { ... use q to read data ... } Dispose(p); p := nil; b) A linked list where Head points to the first node, and Current is used for traversal. c) A function that receives a PStudent parameter, reads data from it, and returns.

Part B: Code Tracing (Exercises 6–10)

Exercise 6 — Trace the Values Trace the following code and state the output:

var
  p, q: ^Integer;
begin
  New(p);
  New(q);
  p^ := 3;
  q^ := 7;
  p^ := p^ + q^;
  WriteLn(p^);
  WriteLn(q^);
  q^ := p^ - 1;
  WriteLn(q^);
  Dispose(p);
  Dispose(q);
end.

Exercise 7 — Trace the Chain Draw the memory state after each numbered comment:

type
  PNode = ^TNode;
  TNode = record
    Value: Integer;
    Next: PNode;
  end;
var
  Head, Temp: PNode;
begin
  Head := nil;               { 1 }

  New(Temp);
  Temp^.Value := 30;
  Temp^.Next := Head;
  Head := Temp;              { 2 }

  New(Temp);
  Temp^.Value := 20;
  Temp^.Next := Head;
  Head := Temp;              { 3 }

  New(Temp);
  Temp^.Value := 10;
  Temp^.Next := Head;
  Head := Temp;              { 4 }
end.

What values does the chain contain at step 4, reading from Head to nil?

Exercise 8 — Predict the Bug What is wrong with this code? What will happen when it runs?

var
  p: ^Integer;
begin
  p^ := 42;
  WriteLn(p^);
  Dispose(p);
end.

Exercise 9 — Predict the Output What does this program print? Trace carefully.

var
  a, b: ^Integer;
begin
  New(a);
  a^ := 100;
  b := a;
  b^ := 200;
  WriteLn(a^);
  WriteLn(b^);
  WriteLn(a = b);
  Dispose(a);
  a := nil;
  b := nil;
end.

Exercise 10 — Count the Leaks How many bytes are leaked by this code? Assume sizeof(Integer) = 4.

var
  p: ^Integer;
  i: Integer;
begin
  for i := 1 to 5 do
  begin
    New(p);
    p^ := i * 10;
  end;
  Dispose(p);
end.

Part C: Short Programs (Exercises 11–17)

Exercise 11 — Swap via Pointers Write a procedure SwapInts(a, b: ^Integer) that swaps the values pointed to by a and b using a temporary variable. Write a main program that demonstrates it.

Exercise 12 — Dynamic Array Simulation Write a program that: a) Asks the user how many integers they want to store (call it n). b) Allocates n individual integer pointers (stored in a static array of pointers). c) Reads n values from the user. d) Prints all values. e) Frees all allocated memory.

Exercise 13 — Maximum Finder with Pointers Write a function FindMax(Head: PNode): Integer that traverses a linked chain of TNode records (as defined in Section 14.9) and returns the maximum Value. Handle the case where Head is nil by printing an error message.

Exercise 14 — Node Counter Write a function CountNodes(Head: PNode): Integer that returns the number of nodes in a linked chain.

Exercise 15 — Build a Chain from User Input Write a program that repeatedly asks the user for an integer (0 to stop). Each integer is stored in a new node, inserted at the head of a linked chain. After the user enters 0, the program prints all values, the count, and then frees all memory.

Exercise 16 — Reverse Print Given a linked chain built by head insertion (so values are in reverse order of entry), write a recursive procedure PrintReverse(Node: PNode) that prints the values in the original order of entry. (Hint: recurse first, then print.)

Exercise 17 — Safe Dispose Wrapper Write a procedure SafeDisposeInt(var p: ^Integer) that: a) Checks if p is nil. If so, does nothing. b) Otherwise, calls Dispose(p) and sets p := nil.

Demonstrate that calling SafeDisposeInt twice on the same pointer does not cause a double free.

Part D: Analysis and Problem-Solving (Exercises 18–22)

Exercise 18 — Memory Leak Detector (Thought Exercise) Design (in pseudocode or English) a system that tracks every New and Dispose call in a program. When the program ends, it reports any allocations that were never disposed. What data structure would you use to track the allocations? (Hint: think about storing the addresses returned by New.)

Exercise 19 — Comparing Approaches You need to store a list of student names where: - Students can be added and removed frequently. - The total number of students varies between 0 and 100,000. - You need to print all students in order.

Compare three approaches: (a) a static array of 100,000 elements, (b) a dynamically allocated linked list, (c) a dynamically allocated array (using GetMem/FreeMem with a known size). For each approach, discuss memory usage, insertion/deletion efficiency, and implementation complexity.

Exercise 20 — Bug Hunt The following program has three distinct pointer bugs. Find all three and explain how to fix each:

program BugHunt;
type
  PData = ^TData;
  TData = record
    Name: string[30];
    Score: Integer;
  end;
var
  a, b: PData;
begin
  New(a);
  a^.Name := 'Alice';
  a^.Score := 95;

  b := a;                    { Bug area 1 }
  b^.Name := 'Bob';
  WriteLn(a^.Name);          { What prints? }

  New(b);
  b^.Name := 'Carol';
  b^.Score := 88;

  Dispose(a);
  Dispose(b);
  WriteLn(a^.Name);          { Bug area 2 }
  Dispose(a);                { Bug area 3 }
end.

Exercise 21 — The @ Operator Danger Explain why the following function is dangerous. What could happen when the caller uses the returned pointer?

function MakePointer: ^Integer;
var
  local: Integer;
begin
  local := 42;
  MakePointer := @local;
end;

Rewrite the function to be safe by using New instead of @.

Exercise 22 — Ownership Transfer Design a procedure TransferOwnership(var source, dest: PNode) that: a) Moves the ownership of a node from source to dest. b) After the transfer, source is nil and dest points to the node. c) If dest already points to a node, that node is first freed (to prevent a leak).

Write the procedure and a test program demonstrating it.

Part E: Extended Challenges (Exercises 23–25)

Exercise 23 — Sorted Insertion Extend the linked chain from Section 14.9 to support sorted insertion. Write a procedure InsertSorted(var Head: PNode; Value: Integer) that inserts a new node at the correct position to maintain ascending order. Test with the values 30, 10, 50, 20, 40 and verify the chain prints as 10, 20, 30, 40, 50.

Exercise 24 — Delete by Value Write a procedure DeleteByValue(var Head: PNode; Value: Integer) that finds the first node with the given value and removes it from the chain, properly disposing of it. Handle the special cases: (a) the value is in the first node, (b) the value is in a middle or last node, (c) the value is not found.

Exercise 25 — PennyWise: Delete and Search Extend the PennyWise project from Section 14.11 with two new operations:

a) DeleteExpense(var Head: PExpenseNode; const Desc: string) — Removes the first expense whose Description matches Desc. Frees the node properly. b) FindExpense(Head: PExpenseNode; const Desc: string): PExpenseNode — Returns a pointer to the first matching node, or nil if not found.

Write a menu-driven test program that lets the user add, search, delete, and print expenses.

Part M: Mastery Challenges

Exercise M1 — Double-Ended Chain Implement a linked chain that maintains both a Head and a Tail pointer. Write procedures for: (a) insert at head, (b) insert at tail, (c) delete from head, (d) print forward. Discuss why deletion from the tail is difficult with a singly-linked structure.

Exercise M2 — Memory Pool Simulation Simulate a simple memory pool. Create 100 TNode records in a static array (the "pool"). Maintain a free list (a linked chain of available nodes, using array indices instead of pointers). Implement PoolNew (returns the index of an available node) and PoolDispose (returns a node to the free list). This exercise demonstrates how memory managers work internally.

Exercise M3 — Stack as Linked List Implement an integer stack using a linked list (not an array). Provide Push(var Top: PNode; Value: Integer), Pop(var Top: PNode; var Value: Integer): Boolean, Peek(Top: PNode; var Value: Integer): Boolean, and IsEmpty(Top: PNode): Boolean. Test with a sequence of pushes and pops. (Preview: this is exactly what Chapter 16 will cover in depth.)