CareerCup

First you need a "Piece" class to represent one piece of a puzzle.
Each piece has four sides, each one with a unique outline which will
only connect to one other piece. Edge sides have an "edge" outline.
Each side also has a piece id attribute called "adjacent" to store the
value of the piece it connects to. Piece provides a "rotate" method
which turns the piece 90, 180, or 270 degrees.
The "Jigsaw" class has a number of pieces in the puzzle and a
container of pieces. The "Solve" method uses a map to store the
association of edges to pieces. It iterates through the pieces and for
each edge, looks to see if its compliment is in the map. If so, it
rotates the new piece to the correct orientation and sets the adjacent
fields in the two edges to point at each other. If not, it adds the
edge to the map. With one pass through the pieces, it should have all
the pieces in the correct orientation and connected to all of the
adjacent pieces.

what is jigsaw puzzle?

A jigsaw puzzle:

Think of a big painting. Now cut the painting into 2 thousand small pieces. Now mix the pieces up and put them in a box. The puzzle is to reconstruct the pieces back into the picture.

I think a 2D array will suffice as a data structure.
Where each slot in the matrix knows and remembers who all are his neighbors.