Computer Science C++  Lesson 33:  Linked-List Algorithms

INTRODUCTION:   

The linked list in this lesson will have the following special characteristic: 

the random order of the incoming data will be stored in ordered fashion based on a key field. 

After creating the linked list, a variety of algorithms will be discussed and solved.

The key topics for this lesson are:

VOCABULARY:                        

DISCUSSION:                      

A.  Building an Ordered Linked List

1.   If data is supplied in unordered fashion, building an ordered linked list becomes a harder problem.  Consider the following cases for inserting a new value into the linked list:

a.   Insert the new value into an empty list.

b.   Insert the new value at the front of the list.

c.   Insert the new value at the tail of the list.

d.   Insert the new value between two nodes.

2.   Suppose the data was supplied in this order:

            42    6    95    12    <eof> 

The resulting ordered linked list looks like this:

3.   Three of the cases are easy to identify and solve:  the empty list case, placing the new value at the front of the list, or adding the value to the end of the list.

4.   To assist us in our discussion of linked list algorithms, some definitions will be helpful.  An internal pointer is one which exists inside a node.  An internal pointer joins one node to the next in the linked list.  An external pointer is one which points to a node from outside the list.  Every linked data structure must have at least one external pointer which allows access to the data structure.  Our linked list in the student outline has two external pointers, first and last.

5.   Suppose a fifth value, 61,  is to be inserted into the list.  We can see in the diagram that it will go between the 42 and 95.  To help the computer  “see” this, we are going to use some helping external pointers, also called auxiliary pointers.

6.   It is possible to find the attachment point using just one auxiliary pointer, but we will use two called temp and back.  Using two external pointers makes the hookup easier.  Finding the attachment point involves something like this:

while we haven't found the attachment point

{

back = temp;                         {move back up to temp}

temp = temp->next;             {advance temp one node ahead}

}

      For attaching the value 61, back and temp will end up pointing to these locations: