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