linked list vs array

[jesperd]

Hi,

I just wondering the advantages/disadvantages using a linked list and an array.

I have to design a tree-structure with internal nodes and leaves. Normally you would choose linked list in c++ and design a class for the nodes.
But there are some issues you have to take into account. For example the nature of a linked list, that is you have to traverse through the list to get a node and you cannot make a random access to it.

I'm not sure how the vector library in c++ works, but I think it uses linked list.
On Wikipedia.org they mention that you can use memory pool to circumvent the naive memory allocator.
Or is it a problem at all? I'm not sure how the "new" operator works, but it should be obviously that if the nodes lies as string of pearls in memory it would give a better performance.

If you know the size of the data, would you prefer array or a linked list for a tree-structure?

/Jesper

[kbw]

A standard C++ vector class uses an array, not a linked list. If it has to grow, it relocates the array to a new larger array.

The underlying array size can be set larger than the amount actually in use by the vector with the reserve() method. This allows the array to grow (until all the spare elements are used) before relocating the array.

Similarly, removing an element frees up a slot in the array. But that means shuffling elements down. See http://en.wikipedia.org/wiki/Erase-remove_idiom

[jesperd]

Thanks for the link.

I figure out the standard vector class uses array.