Which data structure is more efficient for backbite algorithm?

Question

Which data structure is more efficient for implementing backbite algorithm for making a hamiltonian path on a 2d lattice?

Simle arrays or linked list or others...?

Answer 1

I'd use an N*M sized array where each entry stores the coordinates for the next and previous vertex in the path.

Linked lists are probably not the best tool for the job since you are choosing vertices at random, and looking up a random vertex is O(n) in a linked list. With arrays it's O(1).

Answer 2

Schindlabua thanks for your answer, I gotta go implement it...