implement linked list using array - advantages & disadvantages
data-structures, linked-list
Solution
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:
- You'll have dead space in the array (entries which aren't currently used for items) taking up memory
- You'll have to keep track of the free entries - after a few insertions and deletions, these free entries could be anywhere.
- Using an array will impose an upper limit on the size of the linked list.
I suppose some advantages are:
- 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)
- 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.
- You could make some guarantees about elements in the array being close to each other in memory.
Problem
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.