Talk:Search data structure

This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computing This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing ??? This article has not yet received a rating on the project's importance scale.

I don't see how a sorted linked list has an insertion efficiency of O(1). Don't you have to find where to insert it? I think it's O(n).

As a corollary, deletion would also be O(n). Must traverse the list to find the item. Trigger hurt (talk) —Preceding undated comment added 20:24, 16 October 2009 (UTC).Reply

I modified the table to reflect this. 143.44.78.159 (talk) 04:55, 24 May 2010 (UTC)Reply

The timing listed for search is O(1) while Hash table says O(n). Which is it? --ben_b (talk) 18:10, 16 April 2012 (UTC)Reply

I strongly disagree with O(1) for linked-list insert/delete worst case timing. "If you know the target's location..." is not "the worst-case", it is the "best" case scenario considering the nature of the operation! How could this table survive this long without any objections or at least a simple discussion?! What would be the worst-case scenario in the mind of the author, I wonder ! 128.97.84.109 (talk) 21:46, 11 February 2014 (UTC)Reply

BTW, I will wait for a few days if no one objects to my comment I will change all of the linked-list "worst-case" insert/delete times to O(n) ... worst case = insert at the very end, delete from the very end, AND not having a MAGICAL reference to the insertion/deletion location (honestly, where does this magical pointer come from? Having these types of magical powers, one can solve many unsolvable problems in CS... don't you think?!). 128.97.84.109 (talk) 21:51, 11 February 2014 (UTC)Reply

There no "Search data structure" in TOC of Introduction_to_Algorithms#Table_of_Contents, but there "III Data Structures".

Please merge content & delete Search data structure. Ushkin N (talk) 04:54, 24 May 2016 (UTC)Reply