Yep ... thanks for the correction ... so using either an array based list or a linked list would result in these time complexities:
(ordered - array-based list)
depositData: O(lg n + n) since we must use binary search to find proper insert location and then call the insert operation which over time amortizes to O(n)
(described in API) getStoredData: O(1) if we don't have to make a copy of our data
(ordered - linked list)
depositData: O(n + 1) since we may have to search the entire list for the proper insertion point, but insertion takes a constant amount of time for a linked list
getStoredData: O(1) if we don't have to make a copy of our data
Although not quite as good as I led you to believe in my previous post, the ordered linked list implementation is still more efficient than the ordered array list or any unordered list structure.
Note that the implication of insert operatin having O(n) instead of O(lg n) means that the orrdered linked list is a viable option only if you really are going to call the "get" method about as frequently as you call the "insert" method. Insert of O(n) is a tough price to pay for very large collections. If it turns out that you will be calling "insert" much more frequently than you call "get,"
you should consider using a heap as I originally mentioned.
[ January 06, 2007: Message edited by: Dave Wingate ]
[ January 06, 2007: Message edited by: Dave Wingate ]