# Connection between 2D array and list vector?

• 08-31-2008
glo
Connection between 2D array and list vector?
Hi there,

For a maze generator I coded, I used a 2d array of struct Cell.
One of the generation algorithms required to create a list, that would eventually hold pointers to those Cells.
Then it was needed to choose one of the Cell pointers within the list, and work upon it. This one is easy, since I just need to reference to the pointer's location.
Thing is when I needed to do it vice versa - finding a list element based on the array index, (such as finding the list element that points to array[4][7] in the list, and removing it from the list), is where it gets nasty.
I solved it by iterating from list.begin() to list.end(), and comparing x and y values I added to Cell, but I'm not sure it's as fast a solution as can be.
Can I both-way link a list and an array?

Thanks!
• 08-31-2008
matsp
Sure, just make an array [MAXY][MAXX], and then generate the linked list from those elements rather than from allocations.

--
Mats
• 08-31-2008
glo
Thanks for the quick reply Mats

It's what I do really, the list is actually a vector <struct Cell*>
The link works one-way, so I can know where the sixth element points to with *(list[5])
My problem starts when I want it the opposite way, finding which element of the list points to the array index at [4][6] etc.
• 08-31-2008
tabstop
Searching through a linked list by definition involves starting at the front and going element by element through the list until you find what you're looking for. If you want something faster, then you want something other than a list. (Edit: And then of course, you may not be able to insert as fast, etc.)
• 08-31-2008
glo
Thank you,
This pretty much answers my question, will look into alternatives and see if anything is more appropriate to my particular case
• 08-31-2008
matsp
You could of course store the "points to this" as you build your 2D array, so when you produce the maze, you put links to all other cells that refer to [4][6] in the cell [4][6] itself.

--
Mats