Search data structure: Difference between revisions

Revision as of 13:43, 25 September 2010

Revision as of 00:06, 11 October 2010

Line 92:

| O(''n'')

|}<small>&nbsp;† The deletion cost is O(log ''n'') for the minimum or maximum, O(''n'') for an arbitrary element.</small>

<small>&nbsp;* The cost to add or delete an element into a known ___location in the list (i.e. if you have an iterator to the ___location) is O(1),. butIf onlyyou afterdon't know the list___location, hasthen beenyou traversedneed to traverse the list to the ___location of deletion/insertion, which takes O(''n'') time.</small>

This table is only an approximate summary; for each data structure there are special situations and variants that may lead to different costs. Also two or more data structures can be combined to obtain lower costs.