Lesson 10 · 10 of 20

A linked list · Pascal

Build a linked list in Pascal with records and pointers: create nodes, insert in the middle without moving anything and free all the memory.

Pascal · A linked list in DMarlon Studio: the example's code and its output in the terminal

A linked list keeps each element in a separate node that points to the next one. Here each node is a bus stop, TStop, with its name and a Next field. The PStop type is declared before the record it points to: Pascal allows this for pointers as long as the record follows in the same type block, and it is needed here because the record refers to itself through the pointer.

NewStop allocates a node with New(Result), fills it in and returns its address. Because it takes the next node as a parameter, the nested calls build the route back to front: first Moncloa (pointing to nil, the end), then Gran Via and finally Sol, which ends up in route.

Insertion is the big win: route^.Next := NewStop('Callao', route^.Next) creates a node that points to whatever came after Sol and hooks Sol onto the new one. No element moves, unlike an array, where every later element would have to shift.

ToText walks the list recursively: a stop's text is its name plus the text of the rest, until it reaches nil, which returns end. Finally, the while loop frees the nodes one by one, saving Next in next first, because once Dispose(route) runs that field can no longer be read.

Code · main.pas

program main;type  PStop = ^TStop;  // the pointer type may come before its record  TStop = record    Name: String;    Next: PStop;  end;function NewStop(const name: String; next: PStop): PStop;begin  New(Result);  Result^.Name := name;  Result^.Next := next;end;function ToText(stop: PStop): String;begin  if stop = nil then Exit('end');  Result := stop^.Name + ' > ' + ToText(stop^.Next);  // this stop, then the restend;var route, next: PStop;begin  route := NewStop('Sol', NewStop('Gran Via', NewStop('Moncloa', nil)));  WriteLn(ToText(route));  route^.Next := NewStop('Callao', route^.Next);  // insert after Sol  WriteLn(ToText(route));  while route <> nil do  // free every node, front to back  begin    next := route^.Next;    Dispose(route);    route := next;  end;end.

Output · fpc main.pas && ./main

Sol > Gran Via > Moncloa > end
Sol > Callao > Gran Via > Moncloa > end

Key points

Each node holds a value and a pointer to the next; nil marks the end.
The pointer type may come before its record, in the same type block.
Inserting only changes pointers: nothing moves.
When freeing, save Next before Dispose.
Walking a list lends itself to recursion.

Exercise

Remove the Gran Via stop from the route: make Callao point to Moncloa, release the leftover node with Dispose and print the route again.