Delphi - Linked Lists

Programs use several methods to store large amounts of related information

Linked lists: Used when the amount of information is determined at run time.
Static arrays: Used when the maximun amount of data is known at design time.
Dynamic arrays: Used were the amount of information is determined at run time.

Typically, each element of a linked list stores a pointer to (address of) the next item in the list. Double linked lists also store a pointer to the previous item.

By convention, in the last element of the list, next contains zero (nil in Delphi).

Each element of the list is allocated on the heap.

Normally, data is stored in these locations - the first 3 are located in RAM (which provides fast access), the last 2 are not (and are slower to access).

In the program: Global variables (including static arrays), constants (such as literal strings), and program resources are stored in the program memory area
On the stack: This is used to pass parameters to subroutines and to store local variables (variables defined in the subroutine, may also include static arrays)
In the Heap: Any time you use New or TSomeObject.Create, space is allocated here
On a disk dirve: Hard drive, floppy drive, CD drive, RAM drive, etc.
Database: When you truly have a lot of information

Example based on TScreen.Cursors | Example from the Help | Other Variable Length Lists of Data

Example based on TScreen.Cursors

This example is from forms.pas, the comments are added by me.

// This defines a list element - in this case it is a record,
// but it could also be a class

  PCursorRec = ^TCursorRec;
  TCursorRec = record
    Next: PCursorRec;
    Index: Integer;
    Handle: HCURSOR;
  end;


// This allocates storage for a pointer to the first element of the list
// (known as the head) - it is always required in the object
// that maintains the list

    FCursorList: PCursorRec;


// DeleteCursor locates an element in the list, tells Windows to free
// the associated object (a cursor), fixes the list pointers so that this
// element is no longer referenced, and releases the memory for the element

procedure TScreen.DeleteCursor(Index: Integer);
var
  P, Q: PCursorRec;
begin
  P := FCursorList;
  Q := nil;
  while (P <> nil) and (P^.Index <> Index) do
  begin
    Q := P;
    P := P^.Next;
  end;
  if P <> nil then
  begin
    DestroyCursor(P^.Handle);
    if Q = nil then FCursorList := P^.Next else Q^.Next := P^.Next;
    Dispose(P);
  end;
end;


// InsertCursor adds an element to the head (beginning) of the list
// New(P) allocates memory on the stack

procedure TScreen.InsertCursor(Index: Integer; Handle: HCURSOR);
var
  P: PCursorRec;
begin
  New(P);
  P^.Next := FCursorList;
  P^.Index := Index;
  P^.Handle := Handle;
  FCursorList := P;
end;


// GetCursors walks the list using P := P^.Next
// Notice that Index does not refer to a position in the list,
// instead, it refers to a value stored in the list element (record of 
// type TCursorRec)

function TScreen.GetCursors(Index: Integer): HCURSOR;
var
  P: PCursorRec;
begin
  Result := 0;
  if Index <> crNone then
  begin
    P := FCursorList;
    while (P <> nil) and (P^.Index <> Index) do P := P^.Next;
    if P = nil then Result := FDefaultCursor else Result := P^.Handle;
  end;
end;

Example from the Help

This example is from the help example for the New procedure - it adds one element to the head (beginning) of the list.

type

  PListEntry = ^TListEntry;
  TListEntry = record
    Next: PListEntry;
    Text: string;
    Count: Integer;
  end;
var
  List, P: PListEntry;
begin
  ...
  New(P);
  P^.Next := List;
  P^.Text := 'Hello world';
  P^.Count := 1;
  List := P;
  ...
end;

Other Variable Length Lists of Data

Delphi provides a number of list types so that you don't have to manage pointers to the next (and/or previous) objects. Instead, you just use an index, similar to an array.

Actually, the following are really just dynamic arrays - the allocated memory is always contiguous.

TList is a dynamic array of pointers to objects
TStringList is a dynamic array of pointers to strings and pointers to objects.

When either list needs to expand, a new contiguous block of memory is allocated on the heap, the existing data is copied to it, and the old block is deallocated.

Notice that the objects (and/or strings) are not stored in the list (just the pointers are stored) and are not contiguous in memory.

Though TMemo, TRichEdit, TComboBox, TListBox and the like access their data via a TStrings interface, they actually store their data using the Windows api (because they are actually wrappers for Windows Controls).

Author: Robert Clemenzi - clemenzi@cpcug.org