|
If you need to represent a sequence of values, you can use either a linked list or an array. Each has its advantages and disadvantages.
Indexing (getting the i-th member) is efficient for an array, taking only a constant amount of time, but is much slower for a linked list. It takes time proportional to i to find the i-th member of a linked list by skipping over the first i−1 cells.
An array takes less memory for a given number of values than a linked list, since a linked list needs to store the 'next' pointers, which an array does not have. But if you have a lot of extra unused slots in the array, it can take more space than a linked list.
Linked lists allow memory sharing, which arrays to not.
It is very fast to add a new value to the beginning of a linked list. To add a new value to the beginning of an array requires you to make a copy of the entire array.
You can rearrange the structure of a linked list by altering pointers. For example, you can insert a value by adding a new cell. Arrays have a rigid structure.
As you can see, whether a linked list or an array is preferred depends on what you want to do with it.
|