Linked list or sequential memory?

Question

I'm not really 100% sure how to describe this, but I will try my best. I am currently working on a project where they have a struct (called set) that contains a pointer to a set of structs (called objs). To access these set of structs, on has to iterate through their memory address (like an array). The main struct has the number of structs in its set. This is how I do it

objs = set->objs;

for(n=0; n < set->numObjs; n++)
{
  do_something(objs);
  objs++;
}

My question is, would a linked list be safer, faster, or in any way better? How about an array of structs instead?

Thanks.

Answer 1

This source piece is somewhat incomplete however it appears that objs is a pointer to the same type as in set->objs. What you are doing is iterating over a list or an array of these objs by using pointer arithmetic rather than indexing with array syntax. However the list of objs are stored in sequential memory or the pointer incrementation would not be working to give you the next obj in the sequential list.

The question is really what kinds of operations you are wanting to do so far as maintaining and changing the list. For instance if the list is basically a static list that rarely changes, a sequential list should work fine. If the only major operation is to add something to the list, probably a sequential list would be fine if you know the maximum number and can allocate that much sequential memory.

Where a linked list shines is in the following areas: (1) inserting and/or deleting elements from the list especially elements that are not on the front or back, (2) being able to grow and not having to depend on a specific number of elements to the list.

In order to grow a fixed size sequential list, you would typically have to allocate a new region of memory and copy the list to the new memory area.

Another option is to have a data structure that is basically a set of linked sequential lists. As the sequential list fills up and you need more room, you would just allocate another sequential list area and then link the two. However with this approach you may need to have additional code for managing empty spaces and it will depend on whether you will need to delete items or have them in some kind of sorted order as you insert new items.

Here is a wikipedia article on linked lists.

Answer 2

An array is usually a lot faster to traverse and manipulate element-wise, since all data sits contiguously in memory and will thus use the CPU cache very efficiently. By contrast, a linked list is more or less the worst in terms of cache usage, since every list node may easily end up in an entirely separate part of memory and occupy a whole cache line all by itself.

On the other hand, a linked list is easier to manipulate as a container, since you can insert and remove elements at very little cost, while you cannot really do so with an array at all unless you're willing to move an entire segment of the array around.

Take your pick.

Or better, try both and profile.

Answer 3

A linked list would be slower, since you probably won't be using memory caches as efficiently (The list nodes may be on different memory pages, unlike with an array), however using a linked list is probably both easier and safer. I would recommend you only use arrays if you find that the linked list solution is too slow.