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?

  • 1
    $\begingroup$ I think that while wanting to prove specific algorithms is a nice goal, it's not a good starting point. It's best to pick any algorithms book whatsoever and start at the beginning. $\endgroup$
    – Discrete lizard
    Jan 23 '18 at 21:52
  • $\begingroup$ This question might be better suited for cseducators.stackexchange.com $\endgroup$
    – Discrete lizard
    Jan 23 '18 at 21:53
  • $\begingroup$ Welcome to Computer Science! We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$
    – Raphael
    Jan 23 '18 at 23:49

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.