Learning to prove correctness of simple linked-list algorithms

Question

I understand how to use linked lists, and build algorithm using them. But I don't understand how can we prove their correctness, even of simplest algorithm.

I haven't even found a good tutorial reference. Googling suggested that Cormen's book should be a good starting point. His discussion about linked-list (section 10.2) is quite clear, but doesn't demonstrate any correctness proof.

Where can I find a good resource (preferably a book, but can be any resource...) that will teach me that, with good examples?

Answer 1

Linked lists are data structures. They have a set of operations (like the rest of the data structures) and each operation has some properties. For example, the access in a linked list is performed in linear time.

When you are talking about an algorithm that uses a linked list, you assume you have a linked list that works (i.e. the operations are performing as expected) and you show that using those operations, you can achieve the desired goal. Also, in the algorithm analysis, you have to take into account the time complexity of each operation.

This is not very different from the arrays you probably took for granted in your proofs/programs. They too are a data structure, with some operations, each of which take some time. Actually, most of the times the difference between using and array or a linked list stands in the complexity difference obtained by leveraging the properties of each data structure.

Now, to prove that the linked list really works is not a massive problem, since the operations themselves are very straightforward.