PathNodes: array or list
You are talking about pathfinding, right ? In this case you often need only to find a handful of nodes to start your pathfinding (eg A*). Once it has started you can traverse the graph by using a adjacent list, so once your pathfinding is running , you can access each node of interest in O(1).
For the general node structure I would sugguest a tree (quad/oct tree). Most trees suited for this task guarantee an access time of O(log n).
Assuming you are talking about A*, you will use more than one container for the pathfinding, you will need one to represent your scenario, one for the open list and one for the closed list.
The simplest solution is to use a grid to store your nodes and represent your scenario (assuming all your nodes have the same area size), where node of position x, y can be directly translated to the grid x, y index. A grid has two problems, the first one is that it will use a lot of memory, the second is that you will have a lot of nodes.
The best container to keep an open list a heap, since it will always recover the node you need in O(1), inserting an element in a heap is a O(log n) operation. Just keep in mind that you will need a modified heap, as you need to update the node cost (you can also update the values and call the heapify operation, if your implementation allows it).
For the closed list I like to use a list and a flag in the node, once I add it to the closed list I mark the flag and add it to the closed list. This approach is good because the only information you need for the closed list is if the node is in it. In the end of the pathfinding I go through all the elements of the list, reseting the flag.
Just keep in mind that you will need a modified heap, as you need to update the node cost (you can also update the values and call the heapify operation, if your implementation allows it).
The problem with trying to update the node cost in the heap is that you need another structure to keep track of where things are in the heap, or you need to keep the costs in a separate structure... An easier solution is to allow a node to be inserted multiple times in the heap. When you take a node out of the heap, you check if it is in the closed list, and in that case you skip it.
If you repeatedly do pathfindings over the same terrain then keeping an array (with the inbuilt relation between nodes) can be less costly -- particularly if you have to interpret/process the actual (raw) terrain to generate the 'symbolic' map - simplified down to what the pathfinding needs to know -- eliminating re-doing THAT every pathfinding can be a significant saving (interpretations like edge costs/impassibility in different directions for slopes, content of the nodes for difficulty of movement, etc... )
Of course now you may need a array grid for the entire map (versus a subset around where the pathfinding is done if you rebuild that data each time)
I use a specialized priority Queue for my Open list, and a dictionary for my visited nodes. I know that another way to do it, for grid implementations, is to have a bitfield for the visited nodes. Then it's trivially easy to clear all the bits. And now that I wrote that, I think I'll looking into seeing how I'd do that for C# and see if I get any performance gains.
EDIT: It would be slightly trickier in my case, since i'm doing directional and minimum turn radius.
I have an interesting dilemna for the experts. It is about CPU use vs. cache misses. I have a max of 63x63 tiles on a map, each of which breaks down into 20x20 collider tiles and pathnodes. No unit can be smaller than a collider tile, and so it has only room for 4 unit ID's to be partly occupying it at the same time. It takes a ushort to store a unit ID but a bitfield might also be used because they only go up to 4098. 63x63x20x20x12 bit bitfield = 2,381,400 bytes = 2,325.58594 kB = 2.271 MB. Most of the A* pathnode checks will return no collision and require no precise collision check. However if we use a map tile size for the collider tile, and keep a list for any units in the tile, we fragment the memory but we also reduce memory use significantly. But we also have to check for collisions with all units on that map tile for each pathnode we check.
