Notes on Linked Lists II
This set of notes will analyze the program presented at the end of the previous set of notes. This program shows the data types and methods necessary to implement a linked list of integers. This program uses only struct's and functions. It does not use a class. However, it can be easily modified to implement linked lists that contain different data types.
The Type Declarations
The typedef construct allows the programmer to define synonyms or
abbreviations for a data type. The defined type may be used anywhere in
the file after the statement appears. The statement
typedef int LISTTYPE;
equates the user-defined symbol LISTTYPE to the type int. Throughout the file, LISTTYPE is used to refer to the type of data stored in the list. This type can be changed by simply changing the statement above. Sometimes other changes may be required, but the use of the typedef avoids the changing of the data type in many separate places throughout the program file.
Next a struct is defined to represent a linked-list node. The node consists of a place called info for the information to be stored in that node, declared as LISTTYPE( int in this case ), and a place called next for a pointer to the node on the list that follows this node, declared by the statement
noderec * next;
next is the name of the variable which is declared to be of type "pointer to noderec". noderec is the name of the actual struct that contains this pointer. Such a declaration is allowed in C++. The struct is sometimes said to be self-referential.
Finally, since you will often want to refer to pointers to nodes, another typedef that equates the data type "node *" to the symbol PTR is included. Remember that PTR will be the shorthand for the data type for a pointer to a linked list node throught these notes.
The newnode Method
This method encapsulates the dynamic allocation of memory to hold one list
node from the heap. It uses the new method and returns a pointer to
the node that is allocated. Other methods will call this method
whenever memory for a new node is required.
The create Method
Each linked list is identified by a pointer to its first node. When
the list is empty, this pointer has the value NULL. This method
encapsulates the creation of a new list by setting the pointer that is passed to
it as a parameter to NULL. Note that the parameter must be a reference
because the pointer takes on a new value as a result of the action of the
method.
The push Method
This method inserts a new value at the beginning of a linked list. It
receives a pointer to the beginning of the list and the value to be
inserted. The list will be modified as a result of this function's action
so the pointer to the beginning of the list must be a reference. The
action caused by this method is illustrated in the following diagram, assuming
that a new node that contains the value 8 is to be placed at the beginning of
the list. After the method allocates memory for a new node and places the
value into the info portion of the node, two other steps are
necessary. They are as follows.
p->next = h; // Step 1
h =
p;
// Step 2
These steps are labeled in the diagram.
Inserting a New Node At The Beginning of A Linked List
The insafter method
Any node inserted at any point other than the beginning of the list must be
inserted following some node. This method accepts a pointer to a node and
a value to be inserted and inserts that value following the given node.
Note that this method does not choose which node that the value will be inserted
after. The pointer q to that node must be provided by the calling
method. After acquiring memory for the node and having the address
of that memory placed into the variable named p and then placing the
value provided into the node, the method performs two steps. They are
listed here.
p->next =
q->next; // Step 1
q->next =
p;
// Step 2
These steps are shown in the diagram below, assuming that a new node with value 35 is to be inserted between the nodes that contain 30 and 40, respectively.
Inserting A New Node Following Another Node On A Linked List
The findpos Method
The diagrams drawn so far in these notes show a linked list of integers that
is in ascending order. When working with this type of list, it is often
necessary to locate the proper position for insertion of a new node when you
know the value to be stored there. This operation is a variation on a
linear search. The operation should return a pointer to the node prior to
where the new node is to be inserted. At this point, you must realize that
the linked lists you are working with are "forward linked
lists". This means that every node contains a pointer to the node
that follows it, but there is no pointer to the preceding node. You must
compensate for this missing pointer by using a trailing pointer that always
follows the current pointer when you are moving through a list looking for an
element.
This method accepts a pointer to the beginning of a linked list and a value whose position on the list is to be located. It returns a pointer to the preceding node. If the proper position is prior to the first node, the pointer returned has NULL as a value. Thus, when you call this function, you must check the value of the pointer returned to see if it is NULL. If it is NULL, you must call the push method to insert the new value. If it is not NULL, you must call the insafter and use the pointer that was returned to place the new node on the list. If the pointer returned is named q, the following diagrams show its location in each of the following cases.
The new value is to be inserted at the beginning of the list.
The new value is to be inserted at the end of the list.
The new value is to be inserted somewhere in the interior part of the list.
Position Of q When 8 Is To Be Inserted
Position Of q When 70 Is To Be Inserted
Position Of q When 35 Is To Be Inserted
In the code for this method, the variable found is used to indicate when the proper place for the element has been located. This variable is initially set to FALSE, but it is changed to TRUE when the position is located. Two pointers, p and q, are used to do the search. p is initialized to point to the beginning of the list, and q is initialized to NULL. If the value to be inserted is less than the first element, q remains NULL, as the first diagram above shows. The main search loop is coded as follows.
while( p != NULL && !found )
.......
The search continues until the proper position of the new value has been found, making the second condition false, or until the end of the list is reached, making the first condition false. The loop itself repeats the following block of code.
if( x <= p->info )
found = TRUE;
else
{
q = p;
p = p->next;
}
If the value of x does not satisfy the condition, both pointers are moved. q first is assigned to point to the same location as p, and then p is moved forward to the next node. Note that, if the situation in the second diagram above occurs, q will stop at the last node when p takes on a NULL value.
The readinfo and printinfo Methods
These methods must be rewritten for each different type of data that is
stored on the list. If the list is to contain struct's of a certain
type, then these methods must read and print, respectively, all elements of the struct
involved.
The readlist Method
This method accepts values from the keyboard and inserts them onto a linked
list in ascending order. Note that, if the list contains a more complex
data item at each node, the comparison statement must be modified to compare the
appropriate part of the data item. This method uses most of the other
methods described above.
The printlist Method
This method accepts a pointer to the beginning of a linked list and displays all values stored on the list. It follows a simple process and is a special example of a list traversal. This method and other list traversals will be discussed in the next set of notes. Note that this method will remain the same regardless of the type of data stored on the list.
The complete program whose methods were discussed above is included below for easy reference.
//
//
// list.cxx
// inserts elements onto a linked list in order
//
//
#include <iostream.h>
// Type Declarations
typedef int LISTTYPE;
struct noderec {
LISTTYPE info;
noderec *next;
};
typedef noderec * PTR;
// Function Prototypes
PTR newnode(),findpos( PTR, LISTTYPE );
void create( PTR &),
printlist( PTR ),
readlist( PTR &),
printinfo( LISTTYPE ),
readinfo( LISTTYPE &);
void push( PTR &, LISTTYPE ),
insafter( PTR, LISTTYPE );
void main(void)
{
PTR l; // l points to the beginning of a linked list
LISTTYPE x; // temporary input variable
create(l); // creates an empty list
readlist(l); // reads values and places them on the list
printlist(l); // prints the values stored on the list
}
PTR newnode() // allocates storage for a new node
{
PTR p;
p = new noderec;
return p;
}
void create( PTR &l) // creates an empty list pointed to by l
{
l=NULL;
}
// Inserts an element with value x at the beginning
void push( PTR &l, LISTTYPE x)
{
PTR p;
p = newnode(); // allocate storage for a new node
p->info = x; // store x at this node
p->next = l; // point to the beginning of original list
l = p;
}
void printlist(PTR l) // prints the values stored on the list
{
PTR p;
p=l;
while( p!=NULL )
{
printinfo( p->info );
cout << endl;
p = p->next;
}
}
void readlist(PTR &l) // reads values and places them on the list
{ // in ascending order
LISTTYPE x;
PTR pos;
readinfo( x ); // Read first value
while( x != 0 )
{
pos = findpos( l, x ); // Find location of value
if(pos == NULL )
push(l, x ); // If list is empty, place at beginning
else
insafter( pos, x ); // Place in proper location
readinfo( x ); // Read next value
}
}
void printinfo( LISTTYPE x ) // Print value for a list element
{ // Modify this when LISTTYPE changes
cout << x;
}
void readinfo( LISTTYPE &x ) // Read value for a list element
{ // May need to be separated into parts
cin >> x; // If LISTTYPE is a struct
}
void insafter( PTR q, LISTTYPE x ) // Insert a new node following the node
{ // To which q points. q is passed from
PTR p; // the calling function.
p = newnode();
p->info = x;
p->next = q->next;
q->next = p;
}
PTR findpos( PTR l, LISTTYPE x ) // Find the position of a given
{ // element on a list if the element
int found = FALSE; // is to appear in order.
PTR p = l, q = NULL;
while( ( p != NULL ) && (!found) ) // Continue until end of list or value
if( x <= p->info ) // is found.
found = TRUE;
else
{
q = p; // Move both pointers
p = p->next;
}
return q;
}