33

I realize a resizable indexed collection that uses an array to store its elements (like List<T> in .NET or ArrayList in Java) has amortized O(1) insertion time at the end of the collection. But then there's always that one pesky insertion at critical junctures where the collection has just reached its capacity and the next insertion requires a full copy of all elements in the internal array to a new one (presumably twice as large).

A common mistake (in my opinion) is to go with a linked list to "fix" this problem; but I believe the overhead of allocating a node for every element can be quite wasteful, and in fact would dwarf the benefit of a guaranteed O(1) insertion in that rare case that the array insertion is costly—when, in fact, every other array insertion is significantly cheaper (and faster).

What I was thinking might make sense is a hybrid approach consisting of a linked list of arrays, where every time the current "head" array reaches its capacity, a new array twice as large is added to the linked list. Then no copy would be necessary since the linked list would still have the original array. Essentially this seems analogous (to me) to the List<T> or ArrayList approach, except that wherever you previously would've incurred the cost of copying all the elements of the internal array, here you only incur the cost of allocating a new array plus a single node insertion.

Of course, this would complicate other features if they were desired (e.g., inserting/removing into/from the middle of the collection); but as I've expressed in the title, I'm really just looking for an add-only (and iterate) collection.

Are there any data structures out there ideally suited to this purpose? Or, can you think of one yourself?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Dan Tao
  • 125,917
  • 54
  • 300
  • 447

4 Answers4

63

There is a beautiful structure called an extendible array that has worst-case O(1) insertion and O(n) memory overhead (that is, it's asymptotically comparable to a dynamic array, but has O(1) worst-case insertion). The trick is to take the approach that the vector uses - doubling and copying - but to make the copying lazy. For example, suppose you have an array of four elements like this one:

[1] [2] [3] [4]

If you want to add a new number, say 5, you begin by allocating an array that's twice as large:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Next, you insert 5 into the new array:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [5] [ ] [ ] [ ]

Finally, pull down the 4 from the old array into the new:

[1] [2] [3] [ ]
[ ] [ ] [ ] [4] [5] [ ] [ ] [ ]

From now on, any time you do an insert, add the element to the new array and pull down one more element from the old array. For example, after adding 6, we'd get

[1] [2] [ ] [ ]
[ ] [ ] [3] [4] [5] [6] [ ] [ ]

After inserting two more values, we end up here:

[ ] [ ] [ ] [ ]
[1] [2] [3] [4] [5] [6] [7] [8]

If we now need to add one more element, we discard the now-empty old array and allocate an array twice as large as the current array (capable of holding 16 elements):

[1] [2] [3] [4] [5] [6] [7] [8]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

And repeat this process. Discounting the cost of a memory allocation (which is usually sublinear in the size of the array), you do at most O(1) work per insertion.

Lookups are still O(1), since you just decide which of the two arrays to look in, while insertions in the middle are O(n) because of the shuffling.

If you're curious, I have a Java implementation of this structure on my personal site. I don't know how useful you'll find it, but you're more than welcome to try it out.

If you want to invest a bit of time reading over a research paper and trying to implement a fairly complex data structure, you can get the same result (worst-case O(1) append) in O(√n) space overhead (which is provably optimal, by the way) using the ideas in this paper. I never got around to actually implementing this, but it's certainly well-worth the read if memory is a super-scarce resource. Interestingly, it uses this above construction as a subroutine!

mkrieger1
  • 19,194
  • 5
  • 54
  • 65
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • 1
    Haha, this is indeed pretty awesome—just the sort of novel idea I was hoping for! Thanks! – Dan Tao Jan 29 '11 at 01:31
  • 1
    @Dan Tao- No problem! I actually came across this while reading a research paper that needed this as a subroutine in a fast priority queue. They mentioned it in a footnote, and I thought it ironic that it was the most important result from the paper! – templatetypedef Jan 29 '11 at 01:32
  • +1. Even with the memory sacrifice (which doesn't seem to be unreasonable), this seems like a very usable pattern and would only incur a slight penalty when expansion was necessary. I'm going to have to hang on to this one! – Adam Robinson Jan 29 '11 at 01:32
  • For small data, the memory sacrifice is smaller than that of a linked list, and best of all you still have `O(1)` random access! +1 for an amazing[ly simple] algorithm. – R.. GitHub STOP HELPING ICE Jan 29 '11 at 07:28
  • By the way, does this data structure have a name? – R.. GitHub STOP HELPING ICE Jan 29 '11 at 07:28
  • @R.. I first heard it described as an "extendible array" in Brodal's paper on an asymptotically optimal worst-case priority queue, but I doubt that's the real name. I can't find a description anywhere, so I've just continued calling it the "extendible array." – templatetypedef Jan 29 '11 at 07:31
  • 2
    You know, a sad thing occurred to me some time after accepting this answer... [I actually don't think that an implementation of this data structure with guaranteed O(1) insertion is possible](http://philosopherdeveloper.wordpress.com/2011/01/29/how-disappointing/) in .NET because array allocation is itself O(n)--all elements are initialized. Do you know if it works that way in Java too? – Dan Tao Feb 05 '11 at 22:02
  • 2
    @Dan Tao- You're correct that it takes O(n) to zero out the memory. What I'm now curious about is whether you can see this in practice, or whether the GC is smart enough to zero out memory it reclaims (since when you're allocating class objects everything defaults to zero). In that case it might actually not cost O(n) to do the allocation because it's already been zeroed in the background. But you're right... I completely didn't think of that. – templatetypedef Feb 05 '11 at 22:20
  • @DanTao: The cost of allocating N bytes should be thought of as O(N), but one can still have an append-only list with a worst-case append and access times that would be reasonable for values of N up to, say, 2^60. As an example, one could have an array of five nodes, the first of which holds a `foo[16]`, the second of which holds a `foo[64][64]`, the third of which holds a `foo[256][256][256]`, the fourth of which holds a `foo[1024][1024][1024][1024]`, and the fifth of which holds `foo[4096][4096][4096][4096][4096]`. If that's too small (yeah right), use an array of six nodes (2^84 items). – supercat Jan 21 '13 at 22:26
  • 1
    @templatetypedef: The amortized cost of allocation is apt to be at least O(N), if nothing else because a there's a finite limit L to how much memory can be allocated before the garbage collector has to run, and so allocating N bytes must have an amortized cost of at least N/L times the minimum cost of a GC cycle. If the cost is at least O(1), the amortized cost must be N/L times that, or O(N). – supercat Jan 21 '13 at 22:33
  • 1
    @supercat- That's true, though in languages like C or C++ where you can get blocks of uninitialized memory from the allocator, it is very reasonable to expect O(1)-time allocations. But yes, you are right. – templatetypedef Jan 21 '13 at 22:34
  • @supercat: That idea [sounds familiar!](https://github.com/dtao/ConcurrentList) ;) – Dan Tao Jan 22 '13 at 01:21
  • Why is this considered O(1) for inserts when two operations are required, the insert in the new list and the copy of one of the elements from the old list. O(2) may seem twice as bad but it is accurate and, more importantly, constant. – Kelly S. French Feb 20 '13 at 18:18
  • 1
    @KellyS.French- O(1) doesn't mean "one operation;" it means "at most a constant number of operations." O(2) means exactly the same thing as O(1) because big-O ignores constant factors, much in the same way that O(n) = O(1000n) = O(10^100 n). – templatetypedef Feb 20 '13 at 20:12
  • I have a question: does new array with double size take time O(n)? https://stackoverflow.com/questions/5640850/java-whats-the-big-o-time-of-declaring-an-array-of-size-n – maplemaple Apr 09 '21 at 01:31
4

When I need a container like that, I use my implementation of the structure described in "Resizeable Arrays in Optimal Time and Space"

AShelly
  • 34,686
  • 15
  • 91
  • 152
1

OK. What you have described is almost exactly what std::deque is in the C++ standard library. The difference is that an array(usually) is used to hold the pointers to the sub arrays instead of using a linked list.

Khaled Alshaya
  • 94,250
  • 39
  • 176
  • 234
  • Thanks; I had heard of a deque before but for some reason had just assumed it was typically implemented as a circular queue (like a `Queue` in .NET—sorry, I'm not too experienced in C++) that exposed both head and tail for push/pop operations. Good to know! – Dan Tao Jan 29 '11 at 01:29
  • @Dan Tao: Just to let you know, C++'s `std::dequeue` supports O(1) random access like an array. – Jerry Coffin Jan 29 '11 at 15:52
0

One idea would be to create a list of few elements, like:

struct item
{
    int data[NUM_ITEMS];
    item *next;
}

In this case insert would take O(1) and if you reached the limit just create a new block and append it to the end of your list

Elalfer
  • 5,312
  • 20
  • 25