# Data Structure example

Name a data structure that you could use to implement a queue such that all of the standard queue operations are O(1). If you are thinking of a data structure based on Python's built in list, you need to be more specific then just writing "list".

O(1) is constant time and I know that you can use lists to replace using ADTs but what does the question mean by being more specific? Also I thought that lists are O(n), linear time. How would I return something in constant time?

Note: I am a beginner comp sci student who is learning with Python

• Welcome to CS Stack Exchange! When you copy-paste material from another source, you need to credit the source appropriately. I encourage you to edit the question accordingly. If have doubts about what is meant by a question that was assigned to you, I suggest you ask your instructor or teaching assistant -- they will know what they intended. We can't speak authoritatively about what their intent was.
– D.W.
Commented Apr 18, 2017 at 5:11
• "lists are O(n), linear time" -- that sentence makes little sense. A data structure "is" not a Landau class. Some of it's operations may have certain costs that fall into one. And, believe it or not, for some problems lists are more efficient than arrays! Commented Apr 18, 2017 at 20:23

Have a look at this post here. Data structure with search, insert and delete in amortised time $O(1)$? To summarise, it is not possible to have all operations in constant time. If usage of parallelism is an option for you, have a look at this paper titled "A Parallel Priority Queue with Constant Time Operations", http://dx.doi.org/10.1006/jpdc.1998.1425.