Question about linked list
I'm reading a C++ book and will like to get a better understanding of the difference between an array-based implementation of a list and the pointer-based version in terms of complexity for the add/get/remove functions.
An array based implementation of a list may seem appealing at first due to one's early comfort with arrays when learning c++, however once you actually get stuck into the code and try to make it robust you soon realise that to cater for the limitations associated with an array based list actually makes it more work - like when you want to grow the array and need to take the performance knock of reallocating a very large array - typically also, if you are reaching near limits with memory usage within overall system, you would likely suffer very degrading consequences as large chunks of physical ram will be far less available than a large number of smaller chunks (memory within a very busy system do get fragmented).
This is not to say array based lists don't have a place - if the requirement is for a relatively small list where very high speed access is required then an array based list will give the better performance.
Link lists on the other hand are simpler in the sense that they allow for easy growth and shriking by storing chains of nodes. Each node stores a pointer to its next node and in a double link list each node also stores a pointer to it's previous node.
Templates make creating these types of containers in a very intuitive fashion - you may declare a template node something like this:
You then need to create an associated template list list class that utilizes this node template structure to store an head and a tail pointer (tail not required in classical linklist but is very useful and at a very small cost of 1 extra pointer). Your list list class should then have methods for adding an item (to head and one method to add to tail) and also such methods for removing from head and removing from tail + all the other methods that would be useful to a link list adt.
To make such a link list useful you should also consider creating an iterator class. Basically this will just take the head and tail pointers of your link list and iterate from start to end passing you a pointer to the item - this allows you to reference item for reading or for updating.
Basically link list does not suffer the same fix size limitations of the array based list which makes it superior to the array based list for storing large volumes of items, but items within the link list can not be referenced as fast as items within an array based list if by index.
This is not to say array based lists don't have a place - if the requirement is for a relatively small list where very high speed access is required then an array based list will give the better performance.
Link lists on the other hand are simpler in the sense that they allow for easy growth and shriking by storing chains of nodes. Each node stores a pointer to its next node and in a double link list each node also stores a pointer to it's previous node.
Templates make creating these types of containers in a very intuitive fashion - you may declare a template node something like this:
|
|
You then need to create an associated template list list class that utilizes this node template structure to store an head and a tail pointer (tail not required in classical linklist but is very useful and at a very small cost of 1 extra pointer). Your list list class should then have methods for adding an item (to head and one method to add to tail) and also such methods for removing from head and removing from tail + all the other methods that would be useful to a link list adt.
To make such a link list useful you should also consider creating an iterator class. Basically this will just take the head and tail pointers of your link list and iterate from start to end passing you a pointer to the item - this allows you to reference item for reading or for updating.
Basically link list does not suffer the same fix size limitations of the array based list which makes it superior to the array based list for storing large volumes of items, but items within the link list can not be referenced as fast as items within an array based list if by index.
I also forgot to mention the added overhead associated with delete operations on an array based pointer list - if delete operations do not occur at ends of array, then one needs to consider management of open cells or compress array. Thus array based implementation will also require that it not be used where it will change too frequently in size.
Topic archived. No new replies allowed.