Page excerpted from Pointers and Linked Lists topic of a second year course in Data Structures

Algorithms that operate on linked lists.

[In this section I will ignore the rule of the null check to keep examples simple.]

Assume variable head is the head link

Find the length of a list.

We will use a pointer variable p to keep track of the position in the list.

We will use an int variable len to count the nodes.

Loop Invariant:

Deleting a list

When we no longer need a list, we should delete all the nodes of a list.

Here is an algorithm to do that.

Variables

Invariant:

Build a list

We will build a list consisting of a sequence of numbers entered by the user.

Variables

Invariant:

Make a reversed copy of a list

Variables

Invariant:

 

Examples Shown in Full