11-04-2005, 04:47 AM
Linked lists have a few advantages over an array, and also a few disadvantages.
Arrays:
Arrays are (in most implementations) contiguous areas of memory. That means all of the elements of the array from the first to the last are stored in memory sequentially, side-by-side, one after the other. This is how you can have O(1) random access to any element, iow, it doesn't matter how many elements are in the array, the time it takes to retrieve one of those elements will be the same (because we can simply do some pointer arithmetic).
This contiguous storage brings up a problem when we need to insert or remove an element in the array, because all of the elements after it will have to be moved accordingly - that is, when inserting, the elements following the insertion point must be moved further in memory (to the right) to make space for the new element. Similarly, when deleting, the elements following the deletion point must be moved earlier in memory (to the left) to fill in the space caused by the deleted element.
As you can imagine, the larger the array is, the more time it will take to perform these operations. An alternative is to use a linked list, which itself has an O(1) insertion/deletion complexity, but suffers from its own drawbacks as we'll see in a moment.
Linked Lists:
Linked Lists are containers similar to arrays, in the fact that they contain elements. Linked lists implement this storage differently than arrays, however.
A linked list is composed of one or more nodes. These nodes are objects which contain an element, and a pointer to another node. In a singly-linked list, these nodes point to the next node in the list, thus, one can only iterate forward in such a list. In a doubly-linked list, each node points to the next and previous node, making forward and reverse iteration possible.
You may be able to guess how we can have constant insertion/deletion into a linked list - and the answer is with pointers. Since each node (or element) merely points another node, these nodes don't have to be contiguous, ie. they can be stored in memory wherever the compiler sees fit to put them. This means that it's not necessary to move elements when inserting or deleting. All we do is change the pointer!
Although linked lists can be efficient if you need to add and remove alot of elements from the middle of a container, they are incredibly inefficient when it comes to random-access. Since elements are stored at arbitrary locations in memory, the only way to access an element via an index is to start from the beginning of the list and make your way forward (via the nodes pointers). As you can see, this is the same problem with insertion/deletion for arrays, where on the average, half the elements must be dealt with.
Summary:
Arrays are good when you need efficient random access (like a screen buffer) and when you only need to insert/remove elements from the ends of the array.
Linked lists are very efficient in insertion/removal from the middle of the list (like a task list for a kernel), but horribly slow with random access.
Conclusion
For basic object storage, prefer arrays, and use linked lists when you specifically need to take advantage of its features, and are not concerned with its downfalls. For any programmer not using C++, making your own linked list can be fun, and it is a good way to get introduced to working with pointers (C++ has a built-in linked list, as well as numerous other container types).
Arrays:
Arrays are (in most implementations) contiguous areas of memory. That means all of the elements of the array from the first to the last are stored in memory sequentially, side-by-side, one after the other. This is how you can have O(1) random access to any element, iow, it doesn't matter how many elements are in the array, the time it takes to retrieve one of those elements will be the same (because we can simply do some pointer arithmetic).
This contiguous storage brings up a problem when we need to insert or remove an element in the array, because all of the elements after it will have to be moved accordingly - that is, when inserting, the elements following the insertion point must be moved further in memory (to the right) to make space for the new element. Similarly, when deleting, the elements following the deletion point must be moved earlier in memory (to the left) to fill in the space caused by the deleted element.
As you can imagine, the larger the array is, the more time it will take to perform these operations. An alternative is to use a linked list, which itself has an O(1) insertion/deletion complexity, but suffers from its own drawbacks as we'll see in a moment.
Linked Lists:
Linked Lists are containers similar to arrays, in the fact that they contain elements. Linked lists implement this storage differently than arrays, however.
A linked list is composed of one or more nodes. These nodes are objects which contain an element, and a pointer to another node. In a singly-linked list, these nodes point to the next node in the list, thus, one can only iterate forward in such a list. In a doubly-linked list, each node points to the next and previous node, making forward and reverse iteration possible.
You may be able to guess how we can have constant insertion/deletion into a linked list - and the answer is with pointers. Since each node (or element) merely points another node, these nodes don't have to be contiguous, ie. they can be stored in memory wherever the compiler sees fit to put them. This means that it's not necessary to move elements when inserting or deleting. All we do is change the pointer!
Although linked lists can be efficient if you need to add and remove alot of elements from the middle of a container, they are incredibly inefficient when it comes to random-access. Since elements are stored at arbitrary locations in memory, the only way to access an element via an index is to start from the beginning of the list and make your way forward (via the nodes pointers). As you can see, this is the same problem with insertion/deletion for arrays, where on the average, half the elements must be dealt with.
Summary:
Arrays are good when you need efficient random access (like a screen buffer) and when you only need to insert/remove elements from the ends of the array.
Linked lists are very efficient in insertion/removal from the middle of the list (like a task list for a kernel), but horribly slow with random access.
Conclusion
For basic object storage, prefer arrays, and use linked lists when you specifically need to take advantage of its features, and are not concerned with its downfalls. For any programmer not using C++, making your own linked list can be fun, and it is a good way to get introduced to working with pointers (C++ has a built-in linked list, as well as numerous other container types).
stylin: