3 replies to this topic

[solomon201]

I am writing a term paper on the challenges faced when using Linear Data Structures (Array,List).
I'v read it up and have some of the advantages and disadvantages but I want to hear from other people too.
So i want to know from you guys that use or might have used it or know something about it to kindly give your contributions. Thanks

[fayyazlodhi]

I would first say there are certain challenges (advantages of arrays vs linked lists too) that are unique to each of them.

However, since you have used a term Linear data structures, so i presume being Linear is the focus rather than for e.g. stating array needs size upon creation vs list can have any element added any time.

Linear Data structures have properties such as order, so deletion, search, insertion in the middle etc. are costly operations. If it's a sorted array you need to shift all pending elements to insert one in the middle, if a list you have to traverse through each element to determine the actual place.

The complexity of of any of above operations grow linearly as the size grows i.e. if you put in 50 new elements, you have to scan through them all to find a required one if list, if an array you might be able to use index to locate elements but then deletion will require you to move all remaining elements back by one place.

Hope that helps.

[Alexander]

There must be a guideline somewhere to aid in choosing what you require, efficiency however is the major deciding factor in your choice. With using arrays random access is simple and can be performed in constant time complexity with emphasis on indexing and memory efficiency, compressing or resizing an array as mentioned can only be performed in a linear manner based on the size of the array.

A list on the other hand can perform adding, and removing in constant time if that were so required, including sharing structures and simplifying abstract data types such as a priority queue. Random access will not be constant time on this and an array is better suited if that were so required.

If you are working in C++, you may find the set of STL containers useful for these list types (a guideline could be found here if you know an array is not an option http://www.jamesonwi...lass_choice.png)

[WingedPanther]

I think it's important to realize that an Array does not enforce linear access to its elements, resulting in very different advantages/disadvantages compared to a linked list. I've got some tutorials that discuss memory/speed tradeoffs for them here:
http://forum.codecal...nked-lists.html
http://forum.codecal...rees-101-a.html
http://forum.codecal...ing-arrays.html
http://forum.codecal...sing-lists.html