A linked list is a sequence of list elements or nodes in which each node is linked or connected to the node following it. A linked list with three nodes follows:
Each node in this list has two fields: the first field contains data, and the
second field is a pointer to the next node. There is a pointer
(Head) to the first node or list head. The last node always
has a NULL pointer value, indicated as usual by a diagonal line.
Lists are an important data structure because they can be modified easily,
regardless of how many elements may be in the list. For example, a new node
containing the string "Bye" can be inserted between the strings
"Boy" and "Cat" by changing only one pointer value
(the one from "Boy") and setting the pointer from the new node to
point to "Cat":
Similarly, it is easy to delete a list element. Only one pointer value has
to be changed--the pointer that currently points to the element being deleted.
For example, we can delete the string "Boy" from the previous
linked list by changing the pointer from the node "Ace". The node
containing string "Boy" is effectively disconnected from the list
since there is no longer a pointer to it. The new list consists of the strings
"Hat", "Bye", "Cat":
In
Section
14.1, we saw how to connect three nodes with pointer fields. The data
structure shown in
Figure
14.6 could be considered a list of three nodes with pointer variable
R as the pointer to its head. Each node has two data fields
(Power and Volts) and one pointer field
(Next). The pointer value NULL is once again drawn as
a diagonal line:
This section and the ones that follow will treat some common list-processing operations and describe how they are implemented using access types and variables. We will start out with a simple package specification shown in Program 14.1.
Program 14.1
PACKAGE Singly_Linked_Lists IS
------------------------------------------------------------------------
--| Specification for simple linked lists with a single pointer
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
SUBTYPE WordType IS String(1..3);
TYPE List IS PRIVATE;
PROCEDURE AddToFront (L: IN OUT List; Word: IN WordType);
-- Pre: Word is defined; L may be empty
-- Post: Word is inserted at the beginning of L
PROCEDURE AddToEnd (L: IN OUT List; Word: IN WordType);
-- Pre: Word is defined; L may be empty
-- Post: Word is appended to the end of L
FUNCTION Copy(L: IN List) RETURN List;
-- Pre: L may be empty
-- Post: returns a complete copy of the list L
PROCEDURE Display (L: IN List);
-- Pre: L may be empty
-- Post: displays the contents of L's Word fields, in the
-- order in which they appear in L
PRIVATE
TYPE ListNode;
TYPE List IS ACCESS ListNode;
TYPE ListNode IS RECORD
Word: WordType := "###";
Next: List;
END RECORD;
END Singly_Linked_Lists;
This package provides a PRIVATE type List:
SUBTYPE WordType IS String(1..3);
TYPE List IS PRIVATE;
The type declarations in the PRIVATE part are as
follows:
TYPE ListNode;
TYPE List IS ACCESS ListNode;
TYPE ListNode IS RECORD
Word: WordType := "###";
Next: List;
END RECORD;
The package provides four operations:
AddToFront, which adds a new node to the beginning of a list
Display, which displays all the values in the list, in the
order in which the nodes occur
AddToEnd, which adds a new value to a list by first storing
the value in a node, then connecting this node to the end of the list, and
Copy, which returns a complete copy of the list
Given a list L1 as follows:
Display displays
Hat...Boy...Cat...
and the statement
AddToEnd(L1, "Dog");
changes L1 as follows:
Program 14.2 is an illustration of these linked list operations.
Program 14.2
WITH Ada.Text_IO; USE Ada.Text_IO; WITH Singly_Linked_Lists; USE Singly_Linked_Lists; PROCEDURE Test_Lists IS ------------------------------------------------------------------------ --| Illustrates the singly linked list package operations --| Author: Michael B. Feldman, The George Washington University --| Last Modified: September 1995 ------------------------------------------------------------------------ L1: List; L2: List; BEGIN -- Test_Lists -- first test the traverse and copy operations for empty list Ada.Text_IO.Put_Line(Item => "--------"); Display(L1); Ada.Text_IO.New_Line; L2 := Copy(L1); Display(L2); Ada.Text_IO.New_Line; Ada.Text_IO.Put_Line(Item => "--------"); -- add to end of empty list AddToEnd(L1, "Hat"); Display(L1); Ada.Text_IO.New_Line; L2 := Copy(L1); Display(L2); Ada.Text_IO.New_Line; Ada.Text_IO.Put_Line(Item => "--------"); -- add to end of nonempty list AddToEnd(L1, "Boy"); Display(L1); Ada.Text_IO.New_Line; Ada.Text_IO.Put_Line(Item => "--------"); -- add again to end of nonempty list AddToEnd(L1, "Cat"); Display(L1); Ada.Text_IO.New_Line; Ada.Text_IO.Put_Line(Item => "--------"); -- add to front of nonempty list and copy result AddToFront(L1, "Top"); Display(L1); Ada.Text_IO.New_Line; L2 := Copy(L1); Display(L2); Ada.Text_IO.New_Line; Ada.Text_IO.Put_Line(Item => "--------"); END Test_Lists;Sample Run
-------- -------- Hat... Hat... -------- Hat...Boy... -------- Hat...Boy...Cat... -------- Top...Hat...Boy...Cat... Top...Hat...Boy...Cat... --------
Program 14.3
gives the body of the package. In order to show the bodies of the various
operations as separate programs, we have used Ada subunits. Subunits
provide a way to write the subprograms of a package as a collection of separate
files. In the package body, we indicate by the words IS SEPARATE
that each procedure or function body is given in a separate file.
Program 14.3
WITH Ada.Text_IO; PACKAGE BODY Singly_Linked_Lists IS ------------------------------------------------------------------------ --| Skeleton of package body for singly linked lists; --| the operations are provided as subunits of the package. --| Author: Michael B. Feldman, The George Washington University --| Last Modified: September 1995 ------------------------------------------------------------------------ PROCEDURE AddToFront (L: IN OUT List; Word: IN WordType) IS SEPARATE; PROCEDURE AddToEnd (L: IN OUT List; Word: IN WordType) IS SEPARATE; FUNCTION Copy(L: IN List) RETURN List IS SEPARATE; PROCEDURE Traverse(L: IN List) IS SEPARATE; END Singly_Linked_Lists;We are now ready to examine how the various linked list operations are implemented. For absolute clarity in this set of program illustrations, we include the explicit dereferencing operations (the
.ALLs). Be
certain you understand exactly how each operation works before moving to the
next.
Program
14.4 shows the implementation of AddToFront. We need to
indicate to the Ada compiler that this procedure is indeed the subunit referred
to in the package body. The first line of the program,
SEPARATE (Singly_Linked_Lists)
accomplishes this.
Program 14.4
SEPARATE (Singly_Linked_Lists) PROCEDURE AddToFront (L: IN OUT List; Word: IN WordType) IS ------------------------------------------------------------------------ --| --| subunit of singly linked list package --| --| Author: Michael B. Feldman, The George Washington University --| Last Modified: September 1995 --| ------------------------------------------------------------------------ Temp: List; BEGIN -- AddToFront Temp := NEW ListNode; Temp.ALL.Word := Word; Temp.ALL.Next := L; L := Temp; END AddToFront;
This procedure is simple and straightforward, but one must be very careful, in writing operations like this, to get the order of statements exactly right:
Temp.
L--pointing to the first node in
the list, if any--to the Next field of our new node.
Temp's value back into L, which makes
L point to the new first node.Suppose we wrote these statements in the wrong order, for example, we copied
Temp to L before copying L to
Temp. This would overwrite L's old value, and we'd
lose access to the entire list!
In writing linked list operations, one must always ask whether the operation
behaves properly if its list parameter is empty. In this case, if
L is initially empty, it's NULL value is copied into
the Next field of the new node, and all is well.
In the next two sections we implement the remaining three operations, first recursively and then iteratively.
SYNTAX DISPLAY
Subunit
SEPARATE(Package Name)
PROCEDURE P(Parameters) IS ...
SEPARATE(Package Name)
FUNCTION F (Parameters) RETURN ReturnType IS ...
SEPARATE(Singly_Linked_Lists)
PROCEDURE AddToFront
( L: IN OUT List; Word: IN WordType) IS ...
SEPARATE does not end with a
semicolon.
Linked lists are sometimes called recursive data structures because each node contains a pointer to a node of the same type, which is a bit like a recursive procedure containing a call to the same procedure. Indeed, linked list operations can be easily implemented as recursive subprograms.
Program
14.5 gives the implementation of Display.
Program 14.5
SEPARATE (Singly_Linked_Lists)
PROCEDURE Display(L: IN List) IS
------------------------------------------------------------------------
--| Recursive implementation of Display;
--| subunit of singly linked list package
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
BEGIN -- Display
IF L = NULL THEN
RETURN; -- stopping case
ELSE
Ada.Text_IO.Put(Item => L.ALL.Word);
Ada.Text_IO.Put(Item => "...");
Display(L => L.ALL.Next); -- recursion
END IF;
END Display;
Note
carefully that like every recursive subprogram, Display has a
stopping case, namely, the end of the list is reached when a NULL
link is encountered. If the link is not NULL, we are not yet at
the end of the list, so we display the value in the node, then invoke
Display recursively for a smaller set of the data, that is, the
remainder of the list following the first node.
Program
14.6 shows the recursive implementation of AddToEnd.
Program 14.6
AddToEnd
SEPARATE (Singly_Linked_Lists)
PROCEDURE AddToEnd (L: IN OUT List; Word: IN WordType) IS
------------------------------------------------------------------------
--| Recursive implementation of AddToEnd;
--| subunit of singly linked list package
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
BEGIN
IF L = NULL THEN
L := NEW ListNode'(Word,NULL); -- stopping case
ELSE
AddToEnd(L.ALL.Next, Word); -- recursive case
END IF;
END AddToEnd;
Note
again that it has the required stopping case, namely, that its parameter is
NULL. In this stopping case, the IN OUT parameter
representing the list is simply made to point to a new list node containing the
desired word. The syntax of the line
L := NEW ListNode'(Word,NULL);
warrants explanation. Here we are calling NEW and
plugging in the fields of the newly allocated block with a record aggregate
(Word, NULL). The apostrophe preceding the aggregate it is
required; the construct
ListNode'(Word,NULL)
is called a qualified aggregate.
Returning to
Program
14.6, if we are not at the stopping case, that is, not yet at the end of
the list, we make a recursive call of AddToEnd, which attempts to
add the new value to the end of a list that is shorter by one node.
Now consider the Copy operation. You might think that
Copy is a very simple, almost trivial operation. Suppose we
implemented Copy with the following body:
SEPARATE (SinglyLinkedLists)
FUNCTION Copy(L: IN List) RETURN List IS
BEGIN
RETURN L;
END Copy;
Would a client program with the line
L2 := Copy( L1);
receive a correct result in L2? No indeed! Simply
copying the access value in L1 does not copy the list--it
only copies the pointer to the beginning of the list! The result would be that
L1 and L2 would both point to the same node. Now
suppose a modification is made to L1, for example, a new node is
added to its end. Since L2 points to the same list, changing the
list headed by L1 would also change the list headed by
L2 because they are exactly the same list.
This is not what "copying" a value usually means in programming. If you copy
an array A into another one B of the same type,
A and B are distinct, and changing a value in
A does not change B at all. In order to get a
faithful copy of a list, we must copy the entire list, that is, the word in
each node of the original must be copied to a newly allocated node of the
result.
Program
14.7 shows a recursive implementation of Copy. In the stopping
case, the parameter is NULL, so we just return that value. If the
parameter is nonnull, the result of the recursive call is a node whose word
value is copied from the original and whose link is a pointer to a copy of the
remainder of the original.
Program 14.7
Copy
SEPARATE (Singly_Linked_Lists)
FUNCTION Copy(L: IN List) RETURN List IS
------------------------------------------------------------------------
--| Recursive implementation of Copy;
--| subunit of singly linked list package
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
BEGIN
IF L = NULL THEN
RETURN NULL; -- stopping case
ELSE
RETURN -- recursive case
NEW ListNode'(L.ALL.Word, Copy(L.ALL.Next));
END IF;
END Copy;
If you are having any trouble understanding this, there is nothing more effective than pretending you are the copy function and drawing a picture of the input list and the result list as it is constructed at each level of recursion.
It is still possible with our package to write, for two lists
L1 and L2, a statement like
L2 := L1;
This is very misleading because it implies that the list is
copied, whereas in fact only the pointer to the first node is copied. Indeed,
modifying a node in the list pointed to by L2 will also modify
that node in the list pointed to by L1 because the two pointers
point to the same list! In
Section
14.5 we will present an approach using LIMITED PRIVATE types
that prohibits a package user of a package from writing such a misleading copy
operation.
Iterative Implementation of Linked List Operations
Recursively implemented linked list operations are clean and sometimes even elegantly simple. On the other hand, in most real applications of linked lists, iterative operations are used, so we show iterative versions in this section. The price we pay for eliminating the recursion is that the iterative versions are often more complicated, and sometimes more difficult to understand, than their recursive counterparts.
Program
14.8 shows an iterative version of AddToEnd.
Program 14.8
AddToEnd
SEPARATE (Singly_Linked_Lists)
PROCEDURE AddToEnd (L: IN OUT List; Word: IN WordType) IS
------------------------------------------------------------------------
--| Iterative implementation of AddToEnd;
--| we must do a linear search to find the end of the list
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: September 1995
------------------------------------------------------------------------
Current: List; -- designates each node of input list in turn
BEGIN -- AddToEnd
IF L = NULL THEN
L := NEW ListNode'(Word,NULL);
ELSE
-- initialize the loop
Current := L;
-- search until the end
WHILE Current.ALL.Next /= NULL LOOP
Current := Current.ALL.Next;
END LOOP;
-- we found the end; Current designates last node
-- so attach a new node to the node Current designates
Current.ALL.Next := NEW ListNode'(Word, NULL);
END IF;
END AddToEnd;
Iterative
list operations generally consist of a main WHILE loop and, in
fact, are generally quite similar to many array algorithms. Recall from
Chapter
6 that every WHILE loop must contain three distinct features:
WHILE
WHILE statement itself, for
continuing the loop
These three features are present in
Program
14.8: A pointer Current, declared to serve as the loop
variable, is initialized by
Current := L;
which sets Current to point to the beginning of
the list. The test to continue the loop is
WHILE Current.ALL.Next /= NULL LOOP
because, after the loop is finished, we need
Current not to be null but rather to be pointing to the last node
of the list This is so that we can connect the new node to the last node's
Next field. This is accomplished by the statement
Current.ALL.Link := NEW ListNode'(Word, NULL);
Finally, the incrementation step is
Current := Current.ALL.Next;
in which Current is dereferenced and set to the
Next value in the designated node.
Program
14.8 contains a special case to see whether the head pointer L
itself needs to be modified; this will happen only if L is
initially empty. Assuming L is nonempty, we have another
WHILE loop, with Current initialized as in
Display to the start of the list. In this case, the loop body
consists only of the incrementation step because we are simply searching to
find the end of the list.
To be certain you understand AddToEnd, practice tracing its
execution. Draw a pointer variable Current and move it down the
list during each loop iteration. Start with the following list and add
"Art" to its end:
We leave it as an exercise to develop iterative versions of
Copy and Display.
Display as an iterative procedure.
Copy.
Copyright © 1996 by Addison-Wesley Publishing Company, Inc.