1

I was wondering if there is a data structure that supports the conditions mentioned in the title. The memory requirement should be in O(n) for n the number of elements.

D.M.28
  • 11
  • 1
  • An array with geometric growth gives you O(1) access and amortized O(1) append. See [Understanding Amortized Time and why array inserts are O(1)](https://stackoverflow.com/questions/45972160/understanding-amortized-time-and-why-array-inserts-are-o1) – Raymond Chen Jun 02 '22 at 03:05
  • Lets say it should always be O(1), so not only amortized. Is there a way to find such a data structure? – D.M.28 Jun 02 '22 at 05:10
  • Does this answer your question? [A data structure supporting O(1) random access and worst-case O(1) append?](https://stackoverflow.com/questions/4834490/a-data-structure-supporting-o1-random-access-and-worst-case-o1-append) – Raymond Chen Jun 02 '22 at 09:27

1 Answers1

0

Perhaps you may want to take a look at linked lists. If implemented as a doubly linked list, this data structure provides constant time append/prepend and it is also easy to implement constant lookup at either end of the list. If you want to do read/write operations in the middle of the list though, well that takes linear time. Maybe be more specific about this in your post.

You may also like this cheat sheet of data structures provided on https://www.bigocheatsheet.com/

Hash tables could fit your description, but I think you wouldn't have used the word "appending" in that case (?) because you usually "append" elements to a linear data structure.

Easy
  • 41
  • 2
  • 5
  • Hey Easy thank you for your answer. I did'nt quite get it how constant lookup could be implemented in doubly linked list. – D.M.28 Jun 01 '22 at 21:50
  • Is there something like an array that supports the operations in the given time? – D.M.28 Jun 01 '22 at 22:04
  • @D.M.28 The answer said that you get constant-time access to the ends of the list (first element or last element). You don't get constant-time access to arbitrary list elements. It was unclear what the requirements were. (All you said was "reading elements". If your intention is to read the elements in order, then that can be done in O(1). If you want random access, then linked lists don't offer that.) – Raymond Chen Jun 01 '22 at 22:10
  • The requirement is that any element in the data structure can be read in time O(1). Sorry for being imprecise. – D.M.28 Jun 01 '22 at 22:35