**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:

A. Building an Ordered Linked List | B. Linked-List Algorithms | C. Static vs. Dynamic Data Structures |

**VOCABULARY:**

INTERNAL POINTER | EXTERNAL POINTER |

**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: