Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 36 ยท Records, Arrays and Pointers

Linked Lists and Trees with Pointers in Pascal

Build linked data structures in Pascal: singly linked lists, push and pop stacks, insertion and deletion, a binary search tree with recursion, traversal and freeing nodes safely.

An array has a fixed size and inserting in the middle means shifting everything. A linked structure keeps its items in separate heap-allocated nodes, each holding a value and a pointer to the next node. Adding or removing a node only changes a few pointers. Linked lists, stacks, queues and trees all use this idea, and they are the best practice you can get for pointers.

Pascal code is read-only; the runnable demos are C stand-ins using the same node-and-pointer logic. This lesson finishes the records, arrays and pointers chapter.

A node and a list

A node is a record with a value and a pointer to another node of the same type. Pascal's rule that a pointer type may precede its target makes this possible:

PASCAL
type
  PNode = ^TNode;
  TNode = record
    Value: Integer;
    Next: PNode;       { nil marks the end of the list }
  end;

The list itself is just a pointer to its first node, the head:

PASCAL
var
  head: PNode;
begin
  head := nil;         { an empty list }
end.
flowchart LR
    H["head"] --> A["10 | next"] --> B["20 | next"] --> C["30 | nil"]

Figure: a singly linked list. The last node's Next is nil.

Inserting at the front

PASCAL
procedure PushFront(var head: PNode; value: Integer);
var
  node: PNode;
begin
  New(node);
  node^.Value := value;
  node^.Next := head;   { new node points at the old first node }
  head := node;         { head now points at the new node }
end;

The var parameter is essential: the routine changes the caller's head. Calling PushFront(head, 30), PushFront(head, 20), PushFront(head, 10) builds the list shown above.

Walking the list

PASCAL
procedure PrintList(head: PNode);
var
  cur: PNode;
begin
  cur := head;
  while cur <> nil do
  begin
    Write(cur^.Value, ' ');
    cur := cur^.Next;
  end;
  WriteLn;
end;

This prints 10 20 30. The head parameter here is a value parameter, so moving cur along the list never disturbs the caller's head. Never write head := head^.Next in a traversal unless you mean to drop nodes.

Appending, searching and deleting

Appending at the end needs a walk to the last node (or a second tail pointer to avoid it):

PASCAL
procedure Append(var head: PNode; value: Integer);
var
  node, cur: PNode;
begin
  New(node);
  node^.Value := value;
  node^.Next := nil;
  if head = nil then
    head := node
  else
  begin
    cur := head;
    while cur^.Next <> nil do
      cur := cur^.Next;
    cur^.Next := node;
  end;
end;

function Find(head: PNode; value: Integer): PNode;
begin
  Result := head;
  while (Result <> nil) and (Result^.Value <> value) do
    Result := Result^.Next;
end;

Find relies on short-circuit evaluation: when Result is nil, the second test is never evaluated. Deleting the first node whose value matches takes a trailing pointer:

PASCAL
procedure Remove(var head: PNode; value: Integer);
var
  cur, prev: PNode;
begin
  prev := nil;
  cur := head;
  while (cur <> nil) and (cur^.Value <> value) do
  begin
    prev := cur;
    cur := cur^.Next;
  end;
  if cur = nil then
    Exit;                        { not found }
  if prev = nil then
    head := cur^.Next            { removing the head }
  else
    prev^.Next := cur^.Next;     { bypass the node }
  Dispose(cur);
end;

Freeing the whole list

When you are done, every node must be released, or you leak memory. Save the next pointer before disposing:

PASCAL
procedure FreeList(var head: PNode);
var
  next: PNode;
begin
  while head <> nil do
  begin
    next := head^.Next;
    Dispose(head);
    head := next;
  end;
end;

A stack and a queue

A stack is last in, first out: pushing and popping at the front of a linked list is exactly the stack discipline.

PASCAL
function Pop(var head: PNode): Integer;
var
  node: PNode;
begin
  node := head;
  Result := node^.Value;
  head := node^.Next;
  Dispose(node);
end;

A queue (first in, first out) adds at the tail and removes from the head, so keep both a head and a tail pointer.

A binary search tree

A binary tree node has two pointers. In a binary search tree (BST) everything in the left subtree is smaller and everything in the right is larger, so searching halves the remaining work at each step on a balanced tree.

PASCAL
type
  PTree = ^TTree;
  TTree = record
    Key: Integer;
    Left, Right: PTree;
  end;

procedure Insert(var root: PTree; key: Integer);
begin
  if root = nil then
  begin
    New(root);
    root^.Key := key;
    root^.Left := nil;
    root^.Right := nil;
  end
  else if key < root^.Key then
    Insert(root^.Left, key)
  else if key > root^.Key then
    Insert(root^.Right, key);
end;

procedure InOrder(root: PTree);
begin
  if root = nil then
    Exit;
  InOrder(root^.Left);
  Write(root^.Key, ' ');
  InOrder(root^.Right);
end;

Inserting 50, 30, 70, 20, 40 and then calling InOrder prints 20 30 40 50 70: an in-order walk of a BST visits keys in sorted order. The recursion from Recursion and Nested Routines fits trees perfectly: each subtree is itself a tree.

flowchart TD
    R["50"] --> L["30"]
    R --> Rr["70"]
    L --> L1["20"]
    L --> L2["40"]

Figure: the tree built by inserting 50, 30, 70, 20, 40.

Choosing a structure

Need Array Linked list
Fast access by position Yes No (walk the list)
Insert or remove in the middle Slow (shifts) Fast if you hold the node
Memory overhead None One pointer per item
Cache friendliness Excellent Poor

In production Delphi code you would use TList<T>, TQueue<T> or TDictionary; writing your own lists teaches you how they work.

Stand-ins in C

The following are C versions of the same nodes. The first prints the list and removes a node; the second builds the BST.

C C stand-in: linked list push, remove and free

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

C C stand-in: binary search tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why can a record type contain a pointer to its own type in Pascal?

    Declaring PNode = ^TNode before TNode lets the record contain a PNode field, which is the basis of linked structures.
  2. 2. Why does PushFront take its head parameter as var?

    The new node becomes the new head, so the routine must modify the caller's variable.
  3. 3. When freeing a list, why save Next before calling Dispose?

    Reading a field of a disposed node is a dangling-pointer bug. Save the next pointer first.
  4. 4. What does an in-order traversal of a binary search tree produce?

    Left subtree, node, right subtree visits smaller keys before larger ones, giving sorted order.

Summary

  • A linked node is a record holding a value and a pointer to the next node; nil ends the list.
  • Pass the head as a var parameter when a routine may change it; walk with a separate cur pointer.
  • Insert, remove and free by rewiring pointers; always save Next before Dispose.
  • A binary search tree keeps smaller keys left and larger right; recursion makes insertion and traversal short.

Next: Units and the uses Clause