Linked lists are traditionally built in Pascal using pointers (they can also be built using arrays but pointers are more natural). A pointer type is declared and this pointer type is then used inside a record type to link one record to another. In this simple example we will construct a simple linked list with one data element, a string, inside each node:
type
datatype=string[10];
TNameListPointer=^TNameListNode;
TNameListNode=record
name:datatype;
next:TNameListPointer;
end;
The '^' (caret) symbol is used to denote a pointer type. A pointer type holds an address in memory of the data linked to it; the details of the memory location are kept away from the user. A pointer type can have a special value of nil, where the pointer does not point to a node in a list.
This simple idea, a pointer within a record to the next record in the list, can be used to create a wide range of complex structures that are dynamic in nature, that is they can be developed at run-time rather than using a static structure such as an array.
Examples of data structures produced by pointers include a linked list, a stack, a queue, a double-linked list (pointers pointing backwards as well as forwards) and various tree structures including binary trees.
Each node in a binary tree has two pointers, one to the left child and one to the right child. Data structures of this type are less common now as the relational database model has replaced models based on links and pointers, though they are still found in applications such as operating systems.
We define a form with some basic controls to take input from the user and display the state of the list:
For the code that follows we need to declare the first pointer in a list:
var
Form1: TForm1;
firstpointer:TNameListPointer;
Here 'firstpointer' is used as an abbreviation for 'first_pointer', the first node in the list. The first state of a linked list is that firstpointer is set to nil:
procedure TForm1.FormCreate(Sender: TObject);
begin
firstpointer:=nil;
end;
When we add a new item to a linked list we need to search for the place where it will be inserted. The linked list we are building will be sorted so any new item inserted will have to be placed in the correct place. For example if a list contains 'Dan' and 'Tom' then 'Ian' will be inserted between them, 'Andy' will be inserted before 'Dan' and 'Walter' will be inserted after 'Tom'.
The code to search for the correct place to insert an item is as follows:
procedure TForm1.search(firstpointer:TNameListPointer; name:datatype; var
predecessorpointer, currentpointer:TNameListPointer);
var found:Boolean;
begin
currentpointer:=firstpointer;
predecessorpointer:=nil;
found:=false;
while not(found) and (currentpointer <> nil) do
if currentpointer^.name >= name
then found := true
else
begin
predecessorpointer:=currentpointer;
currentpointer:=currentpointer^.next;
end;
end;
This procedure searches for the insertion point in a list by starting at the beginning of the list (currentpointer:=firstpointer;) and comparing the current item with the name being inserted. If the current item in the list is greater than or equal to the new item then the insertion point has been found and the values of predecessorpointer and currentpointer will be returned with their current values. If the insertion point has not been found then the pointers will be changed by setting the predecessor of current to currentpointer and setting currentpointer to the item in the list (currentpointer^.next). The search procedure returns the values of predecessorpointer and currentpointer to the point from which they are called because they are needed there (predecessorpointer=predecessor pointer).
Now that the insertion point has been found we can insert the new item:
procedure TForm1.insert(var
firstpointer:TNameListPointer; predpointer, currentpointer:TNameListPointer);
var newnamenode : TNameListPointer;
begin
new(newnamenode);
newnamenode^.name:=edit1.text;
if predpointer=nil then
begin
newnamenode^.next:=firstpointer;
firstpointer:=newnamenode;
end
else
begin
newnamenode^.next:=currentpointer;
predpointer^.next:=newnamenode;
end;
end;
This procedure returns the value of firstpointer to the point from which it is called. It uses the values of predecessorpointer and currentpointer, which were set in the search procedure, to assign the correct pointer values as the new item is inserted. The new procedure is used to create a new node and the value of name is set to the text in the editbox on the form. If there was no predecssor pointer then the the pointer of the new item is set to the previous first item (firstpointer) and the new node is set to firstpointer. If there was a predecessor then the new node must fit between it and currentpointer so the next field of the new node is set to currentpointer and the predecessor pointer's next field is set to the new pointer.
If the list contains 'Dan' and 'Tom' and 'Ian' is to be inserted then Ian's next field will be set to Tom and Dan's next field will be set to Ian.
The two routines above are called when the user signals an insert operation by clicking on the button:
procedure TForm1.Button1Click(Sender: TObject);
var currentpointer, predpointer:TNameListPointer;
begin
listbox1.clear;
if not (edit1.text='') then
begin
name:=edit1.Text;
search(firstpointer, name, predpointer, currentpointer);
insert (firstpointer, predpointer, currentpointer);
end;
display;
edit1.Clear;
edit1.SetFocus;
end;
The listbox is updated by calling the display routine:
procedure TForm1.display;
var currentpointer:TNameListPointer;
begin
listbox1.clear;
currentpointer:=firstpointer;
while currentpointer<>nil do
begin
listbox1.Items.add(currentpointer^.name);
currentpointer:=currentpointer^.next;
end;
end;
This routine uses firstpointer to set currentpointer and then traverses the list by changing the value of currentpointer^.next to point to the next item. When the last item is reached its pointer will be nil and the process will stop (the value of nil is set in the line newnamenode^.next:=firstpointer); in the insert procedure: the last item in the list will have its next pointer set to nil.
In this example three items have been added in order Tom, Dan, Ian:
Deletions from the list are carried out in a similar fashion except that a node is removed from the list (using the dispose procedure).
procedure TForm1.delete(predpointer, currentpointer:
TNameListPointer);
begin
if predpointer=nil then
firstpointer:=firstpointer^.next
else
predpointer^.next:=currentpointer.next; //skip over element to be deleted
(currentpointer)
dispose(currentpointer);
end;
procedure TForm1.DeleteButtonClick(Sender: TObject);
var
currentpointer, predpointer:TNameListPointer;
i:integer;
begin
if listbox1.ItemIndex<0 then
showmessage('Select an item to delete')
else
begin
i:=listbox1.ItemIndex;
search(firstpointer, listbox1.Items[i], predecessorpointer, currentpointer);
delete(predpointer,currentpointer);
end;
display;
end;
The DeleteButton procedure checks that the user has selected an item in the listbox and then uses the search procedure described above to find the item to delete. The delete procedure checks whether the item to be removed is the first in the list (predecessorpointer=nil): if so then the firstpointer of the list will be set to the first node's next pointer. If the item to be removed is not the first node in the list then predecessorpointer has a value other than nil and its pointer is set to the next pointer in currentpointer, the item to be deleted.
If the list contains Dan, Ian and Tom and Dan is to be deleted then firstpointer becomes Dan^.next (i.e. Ian).
If the list contains Dan, Ian and Tom and Ian is to be deleted then firstpointer stays the same (Dan) and predecessorpointer.next becomes Ian^.next (i.e. Tom).
In this screen shot Ian and Tom have been deleted from the list shown above:
Using these routines an ordered list can be maintained without the need for arrays and sorting. The list can grow and shrink dynamically and it will only ever use the amount of memory that the current nodes require. It is not restricted in size by a static declaration such as array[1..100] and can grow to a size restricted by memory. The area of memory from which blocks are taken for the nodes is known as 'the heap'.
The basic operations here could be enhanced by copying the list to a file and providing a routine to read a list from a file (see the TList example for details).
To save to file and open from we need to amend the form:
To save a file we declare a type and a variable:
TNodeFile=file of TNameListNode; //after record declaration
myfile: TNodeFile; //make it global
procedure TForm1.Button5Click(Sender: TObject);
var currentpointer:TNameListPointer;
filerecord: TNameListNode;
begin
assignfile(myfile,'list.dat');
rewrite(myfile);
currentpointer:=firstpointer;
while currentpointer <> nil do
begin
filerecord.name:=currentpointer^.name;
filerecord.next:=currentpointer^.next;
write(myfile, filerecord);
currentpointer:=currentpointer^.next;
end;
closefile(myfile);
end;
This code does the following:
Here is the code:
procedure TForm1.Button6Click(Sender: TObject);
var currentpointer:TNameListPointer;
filerecord: TNameListNode;
newnamenode: TNameListPointer;
counter:integer;
begin
counter:=1;
assignfile(myfile,'list.dat');
reset(myfile);
while not (eof(myfile)) do
begin
read(myfile, filerecord);
new(newnamenode); //make a new node to put the record in
newnamenode^.name:=filerecord.name; //set the name of the new node
newnamenode^.next:=filerecord.next; //and the pointer
if counter = 1 then firstpointer:=newnamenode;
inc (counter);
end;
closefile(myfile);
display;
end;
This code does the following: