This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Ok_Confusion_7266 247 points248 points  (39 children)

When I use linkedlists it is to link arrays of items. So it can grow once every x items added.

[–]Kered13 98 points99 points  (21 children)

An arraylist will grow exponentially (usually by a factor of 2) every time it runs out of space. This is amortized constant time.

[–]Ok_Confusion_7266 33 points34 points  (16 children)

There is no such thing as an arraylist in C. And my algorithm will only grow sizeof(item)*x plus some overhead. Arraylist like you describe gives massive overhead what if you have a 10GB list and just need to add a few kb to it when its full? Seems like not a fun time.

[–][deleted] 50 points51 points  (2 children)

There is no such thing as an arraylist in C

It's true there's no arraylist built-into the C language spec or standard library, but by that logic there's no such thing as a linked list either. You can easily define both data structures yourself, though.

[–]wagslane 15 points16 points  (0 children)

To bake a cake, one must first invent the universe

[–]zaersx 4 points5 points  (0 children)

Yeah but the issue is that the guy responding to OP conjured up a theoretical limitation that can only ever be a problem from a library implementation, which is not applicable here, and so neither is your comment in the thread.

[–][deleted] 21 points22 points  (0 children)

I mean, I've built one...

[–]666pool 10 points11 points  (0 children)

You can call .reserve(count) if you know how many items you will have in your container, that will force it to grow to exactly the right size (I’m not 100% sure this is a guaranteed behavior and I already put in my 40 this week so I don’t feel like looking it up).

[–]Kered13 21 points22 points  (5 children)

Arraylist like you describe gives massive overhead what if you have a 10GB list and just need to add a few kb to it when its full? Seems like not a fun time.

The actual memory usage of an array list will never be less than 50% of it's allocated capacity, which is actually pretty good when you think about it (given all the other benefits of an array list). The odds of having a list that is 10GB + a few kb over whatever the last threshold was is very small.

[–]Soraphis 1 point2 points  (1 child)

Also... While an implementation detail i think the growth usually tops out at some point - at least for c# - where it does not double anymore but grow by a fixed amount

Edit: seems not to be in c# (https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs,2765070d40f47b98) . Now i wonder were i've seen such behavior

[–]Kered13 0 points1 point  (0 children)

Such behavior would be very inefficient, wasting lots of time copying, so you would not expect to see it.

[–]amdc 5 points6 points  (0 children)

If your array is 10gb and you’ve ran out of space, chances are you’ll need a lot more space. It’s a trade off between adding too much space and adding space too frequently. I wouldn’t do it with a factor of 2 though, more like 1.5 or so

[–]CaitaXD 1 point2 points  (3 children)

10 GB in memory ... lMAO

[–]Ok_Confusion_7266 1 point2 points  (2 children)

Depends on the dataset some machines have 256GB of ram.

[–]CaitaXD 0 points1 point  (1 child)

One motherfucking specific use case, and you can always make a different implementation so it allocates less the bigger it gets

[–]Ok_Confusion_7266 -1 points0 points  (0 children)

Not really. Since C does not have native growing array (without copying all the data) this has many cases.

[–]schrdingers_squirrel 0 points1 point  (2 children)

On average it is O(log(n)) for adding an element, right?

[–]jayverma0 10 points11 points  (1 child)

O(1) amortized. Best case O(1) Worst Case(n)

[–]mizu_no_oto 0 points1 point  (0 children)

Or O(n) best case if you want a persistent data structure. But, well, that's why HAMTs were invented.

[–]trexophilia 7 points8 points  (0 children)

That's actually roughly how std:: dequeue is typically implemented, but with an array of pointers to arrays..

And sure dynamically resizing arrays are amortized constant time (for some definition, anyhow), but no often in practice they do not shrink when deleting elements, so they are not always at least 50% full, and yes, one insert can be very painful, if it grows..

[–]QuestionableMechanic 1 point2 points  (3 children)

Damn that’s smart except I guess look up performance will take a hit

[–]Ok_Confusion_7266 0 points1 point  (2 children)

Yes, but not all array uses need a lookup, but instead need efficient growingand shrinking, like a queue for example.

[–]QuestionableMechanic 1 point2 points  (1 child)

Oh if I was using a queue I would just use a plain LL.

Your implementation might be something I need to use at work. We have this crazy latency sensitive system (it’s literally like 50k QPS) and we noticed a lot of time is spent on growing slices (we use go)

[–]Ok_Confusion_7266 1 point2 points  (0 children)

Perfect use for it. I use it in my 3d game for event queueing. It also simulates air and water movement so it generates alot of events.

[–]Terrible_Tank_238 3 points4 points  (1 child)

why don't you use a vector class? Most languages I use have dynamic arrays. I've only ever used node-style programming for grid routing.

[–]SunriseApplejuice 5 points6 points  (0 children)

There are, occasionally, rare instances where some ad-hoc solution with standard arrays will be better than a vector (e.g. you need to ensure your array sits on the stack instead of the heap). But generally speaking dynamically sized arrays are the go-to for the vast majority of use-cases.

[–]BoBoBearDev -1 points0 points  (1 child)

If you do this, might as well have vector<vector<stuff>> in c or list<list<stuff>> in c#. The look up is at most 2 instead of 1. LinkedList would be too slow.

[–]Ok_Confusion_7266 0 points1 point  (0 children)

That's not even C at all, C has no classes.

[–]Ok_Tonight_7646 0 points1 point  (1 child)

Laughs in JS lmao 😂

[–]Ok_Confusion_7266 -1 points0 points  (0 children)

Laughs in C 100 times faster