Tout simplement un tableau à 2 dimensions, ça n'irait pas ?
Avec un tableau, tu n'as pas besoin de pointeur pour trouver les voisins, un simple calcul sur les coordonnées devrait suffire.

Pour ce qui est ensuite de trouver le chemin le plus court, on verra quand ton labyrinthe sera modélisé. Il peut y avoir plusieurs approches