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).
Example based on TScreen.Cursors
// 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
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
Actually, the following are really just dynamic arrays - the allocated memory is always contiguous.
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