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:

- p has the same value as one of the links of the list.
- len equals the number of links between head and p.

#### 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

- head: the head link of the list

Invariant:

- All nodes between the original and the current value of head have been deleted

#### Build a list

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

Variables

- newHead: the head link of the new list

Invariant:

- newHead is the head of a list that contains all the values read so far from input , but in reverse order.

#### Make a reversed copy of a list

Variables

- head: the head link of the original list
- newHead: the head link of the new list
- p: a cursor into the original list

Invariant:

- p has the same value as one of the links of the list headed by head.
- newHead is the head of a list that contains copies of all the nodes between head and p, but in reverse order.

## Examples Shown in Full