data structures - implement linked list using array - advantages & disadvantages

Question

I know how to implement linked list using array. For example we define a struct as follow:

struct Node{
    int data;
    int link;
}

"data" stores the info and "link" stores the index in the array of next node.

Can anybody tell me what is the advantage and disadvantage of implementing a linked list using array compared to "ordinary" linked list? Any suggestion will be appreciated.

Answer 1

If you back a linked list with an array, you'll end up with the disadvantages of both. Consequently, this is probably not a very good way to implement it.

Some immediate disadvantages:

1. You'll have dead space in the array (entries which aren't currently used for items) taking up memory
2. You'll have to keep track of the free entries - after a few insertions and deletions, these free entries could be anywhere.
3. Using an array will impose an upper limit on the size of the linked list.

I suppose some advantages are:

1. If you're on a 64 bit system, your "pointers" will take up less space (though the extra space required by free entries probably outweighs this advantage)
2. You could serialise the array to disk and read it back in with an mmap() call easily. Though, you'd be better off using some sort of protocol buffer for portability.
3. You could make some guarantees about elements in the array being close to each other in memory.