One method of storing a collection of data items is by placing them in an array. Each element of the array is accessed by referencing the array name with a subscript. With many programming languages (including Pascal) this requires knowledge of how many elements are to be stored before the program is executed.
But: What if we don't know the number of elements that will be stored? We could take a guess, but if we don't allow enough space then we are in trouble. We could allow more memory than we really need but this is wasteful, and how can you be sure that you have enough room?
An array is a set of continuous (one follows the other in order) memory locations reserved at compile time. For example: an array of 5 elements, X[5], looks like this:
A linked list is a set of non-continuous memory locations allocated at run time.
An array is reserved at compile time. "Reserved" means that you have a fixed number of items, and "at compile time" means that you cannot change the number of items while the program is running.
A linked list is allocated at run time. "Allocated" means that you create the necessary space only as you need it. "At run time" means that you can change the linked list as the program is running.
While array elements follow one after the other in memory (continuous), linked lists are randomly placed in memory (non-continuous) and connected using pointers. Pointers are simply a connection from one element in the list to the next element in the list. They can be thought of as a highway on a road map. Once you reach one city then the map shows you the route to the next city. Each city can be thought of as an element in the linked list, and the highway can be thought of as the pointers.
There are two major disadvantages of linked lists:
1) Pointers take up extra storage space as well as the elements in the list
2) Extra program overhead (in terms of extra Pascal code) is necessary to process the linked list
There are four major advantages of linked lists:
1) Linked lists allows us to allocate memory space as needed, while the program is running ("on the fly")
2) Linked lists make sure that we only have as much memory as we need, therefore no wasted space
3) You can expand or reduce the memory locations as necessary. You cannot do this with arrays as they are fixed in size
4) It is easy to add and delete elements in between other elements in a linked list. This is an automatic feature of linked lists, and is not possible for arrays unless you have special code designed to perform inserting and deleting
A linked list consists of several components:
The data element is the location of the information you wish to store. In the examples in this chapter we will use integer numbers.
The pointer (or link) is the connection to the next data element. Since the data is stored randomly (non-continuous) in memory, we need a pointer to locate the next data element. The pointer "points" to the next data element using its address in memory. The concept of an address in memory is similar to the concept of addresses in SML, but in Pascal we have a large number of addresses that we can use.
Together, the data element and it's pointer are called a node. Note that the pointer is not the pointer to this data element, it is the pointer to THE NEXT DATA ELEMENT.
The head, or headpointer, is the pointer to the start of the linked list (the first node in the list). Since the linked list is stored randomly in memory, you have to know where to start. The headpointer tells you where to start.
WARNING: Be careful that you don't lose the headpointer! If you lose the headpointer then all your data is lost! The information is lost because you do not know where it starts. If you lose the headpointer, the linked list is still in memory...somewhere...but you cannot search for the information. The headpointer is your only connection to the list.
The nil, or null pointer, is used to end the list. If you find a pointer that is equal to nil, then you have reached the end of the linked list.
As with integers, real numbers, strings, characters, boolean variables, and other types of information you must initialize the variables first before you use them. With linked lists, you must initialize them as pointers to memory that have certain characteristics.
For example: lets say we want to create a linked list of integer numbers. Using the previous diagrams we can say that the node consists of two things: an integer data element, and a pointer. This is the Pascal code to set up the information:
type
node = @integernode; (* Define 'node' as the links *)
integernode = record
number : integer; (* the data element *)
next : node; (* the pointer *)
end;
Now that we have the node created, we need to define some pointers with this type so that they can be used properly:
var
headpointer, currpointer, temppointer : node;
This defines three variables (headpointer, currpointer, and temppointer) as a type node, which is a node in the linked list. The headpointer always points to the first node in the list, while currpointer (current pointer) and temppointer (temporary pointer) are used periodically to add nodes, delete nodes, or perform some functions with a particular node in the list.
In Pascal, when you define an integer, real, boolean, and so on, Pascal performs two steps.
var
counter : integer;
First, Pascal creates a variable called (in the above example) counter, that can be used as an integer. Second, Pascal reserves some space in memory so the integer can be used. Storing information in counter makes Pascal store that information in the memory reserved for counter.
In addition, different types of variables require different amounts of memory space. For example, a real number requires more memory storage than an integer number. Pascal knows how much memory to reserve based on what type of variable you are using. Integers cause Pascal to reserve X bytes, while real numbers cause Pascal to reserve Y bytes.
When you use linked lists, Pascal DOESN'T KNOW how much memory you are using. Therefore: PASCAL DOES NOT RESERVE MEMORY FOR YOUR POINTERS! You must reserve this memory yourself. The process of reserving memory is called allocating memory.
Pascal provides a function for allocating memory, called NEW. For example, if you wanted to allocate memory for the headpointer above, you would place this line in your Pascal code BEFORE YOU USE THE HEADPOINTER:
NEW(headpointer);
Pascal knows how much memory to allocate because you have previously declared headpointer as type node (in the var statement).
When you are done using a node of a linked list, you must also delete the memory from the list, and free the reserved memory. The process of freeing previously reserved memory is called deallocating memory.
Pascal provides a function for deallocating memory, called DISPOSE. For example, if you wanted to deallocate the memory for the headpointer, you would place this line in your Pascal code:
DISPOSE(headpointer);
You must always use NEW and DISPOSE in combination with your linked lists in order to set aside the memory that you need.
Lets assume that we want to access the information in the following node:
We can refer to the data in this node as: currpointer@.number (in this case currpointer@.number = 24) and the pointer to the next node is currpointer@.next. The pointer to this specific node is currpointer.
One of the functions most commonly performed is inserting a node into a linked list. The linked list may be empty, or may have nodes already in the list. Either way, the insertion process is similar. For example, given the following:
We wish to add the number 47 after the number 83.
First, we need to set the current pointer so we have a reference point to use in future steps:
The Pascal code to perform this is:
currpointer := headpointer;
Second, we create a new node to store the number 47. We will store the pointer to this new node in temppointer:
The Pascal code to perform this is:
NEW(temppointer);
Third, we need to place the number 47 in the new node:
The Pascal code to perform this function is:
temppointer@.number := 47;
Fourth, we need to start inserting the node in the linked list. Up to now, temppointer has not been connected to the linked list. To insert the new node into the linked list, we must first take the next node after currpointer (currpointer@.next) and connect it so that it is now the next node after temppointer (temppointer@.next):
The Pascal code to perform this function is:
temppointer@.next := currpointer@.next;
Fifth, we must connect the new node after the current node:
The Pascal code to perform this function is:
currpointer@.next := temppointer;
This links the nodes together and finishes the insertion process.
The deletion process is basically the reverse of the insertion process. In the example below, lets delete the number 83 from the linked list.
First, we need to locate the node BEFORE the node we wish to delete, and set it to currpointer:
Second, we need to set temppointer to the node we wish to delete:
The Pascal code to perform this function is:
temppointer := currpointer@.next;
Third, we need to connect all the nodes after temppointer to all the nodes before temppointer. We perform this step before deleting the node. If we were to delete the node first, we would lose the pointer to the rest of the linked list.
The Pascal code to perform this function is:
currpointer@.next := temppointer@.next;
Fourth, we delete the node.
The Pascal code to perform this function is:
DISPOSE (temppointer);
and we get:
The process of jumping from node to node, starting at the headpointer, and continuing on to the end of the linked list, is called traversing the list. Typical reasons for traversing a linked list are: printing out the linked list, searching for a particular node, or performing some function on a node or a set of nodes in the linked list.
The following Pascal code demonstrates how to traverse a linked list, starting at the headpointer, and continuing on until the end of the list. At each node we print out the number in the node.
currpointer := headpointer; (*Start at the head of the linked list*)
repeat
begin
writeln(currpointer@.data); (*Print out the number in the node*)
if (currpointer@.next <> nil)
then currpointer := currpointer @.next;
end;
until (currpointer@.next = nil); (*Until we reach the end of the list*)
The following file (called LLEXAMPL PASCAL) is a complete sample program that demonstrates insertion, deletion, and printing nodes. Pay special attention to the way node pointers are passed to the printlist() procedure and how the searching is performed when you wish to delete a node.
(********************************************************************)<> (* CS200: Linked Lists *)
(* *)
(* This is a sample program showing you how to insert, print, and *)
(* delete nodes from or to a linked list. *)
(********************************************************************)<>
program llexampl(input,output);
(* The type section sets up a node so that it can store integers *)
type
node = @integernode;
integernode = record
number : integer;
next : node;
end;
(* The var section sets up several variables used to access the linked
list:
headpointer - ALWAYS points to the top of the linked list
currpointer - used to point to the current node
temppointer - for adding and deleting nodes (temporary pointer)
prevpointer - used for keeping track of the pointer to the
previous node in the linked list *)
var
headpointer, currpointer, temppointer, prevpointer : node;
(* This procedure is used to print out each node in the linked list.
You usually start printing from the top of the list (headpointer),
but you can actually start printing from any node. *)
procedure printlist(pointer:node);
begin
while (pointer <> nil) do (* Continue until the end of the list *)
begin
writeln(pointer@.number); (* Print out the node *)
pointer := pointer@.next; (* Go to the next node *)
end;
end;
begin
termout(output);
(* Start the Linked list with the number 100. Note that the Pascal
code below for inserting 100 is different than the code for
inserting the other numbers. This is because the linked list
has not yet been created and you must specially set up the
first node in a linked list. *)
NEW(headpointer);
headpointer@.number := 100;
headpointer@.next := nil;
(* Insert the number 95 after the number 100 in the linked list *)
currpointer := headpointer;
NEW(temppointer);
temppointer@.number := 95;
temppointer@.next := currpointer@.next;
currpointer@.next := temppointer;
(* Insert the number 83 after the number 95 in the linked list *)
currpointer := temppointer;
NEW(temppointer);
temppointer@.number := 83;
temppointer@.next := currpointer@.next;
currpointer@.next := temppointer;
(* Insert the number 47 after the number 83 in the linked list *)
currpointer := temppointer;
NEW(temppointer);
temppointer@.number := 47;
temppointer@.next := currpointer@.next;
currpointer@.next := temppointer;
(* Now that we have a linked list we can print out the nodes *)
writeln('The Linked List is:');
printlist(headpointer);
(* Delete the number 83 from the linked list *)
(* Step 1: We have to find the number (Searching) *)
currpointer := headpointer;
while ((currpointer@.number <> 83) and (currpointer <> nil)) do
begin
prevpointer := currpointer;
currpointer := currpointer@.next;
end;
(* The node we were searching for is the previous one, so: *)
if (currpointer <> nil)
then currpointer := prevpointer;
(* Step 2: Now that we have found the node containing the number
83, we can delete that node *)
if (currpointer <> nil) then
begin
temppointer := currpointer@.next;
currpointer@.next := temppointer@.next;
DISPOSE(temppointer);
end;
(* Print out the linked list again to show that 83 was deleted *)
writeln('The Linked List (after deleting 83) is:');
printlist(headpointer);
end.
The following is a console of the program after it has been run:
The Linked List is:
100
95
83
47
The Linked List (after deleting 83) is:
100
95
47
Ready;