As one of my beginner C projects I'm making a simulation of a few animals...

So they're living in a 2D array or something? And they do a random walk to find food and die if they don't find it quick enough?
Anyway you can probably just use an array of pointer to animal structs, and then null the ones that die (and maybe even free that struct memory). Then you just traverse the array, skipping all nulls. Probably also keep a counter too, so you don't end up in an endless loop if they all die.

Linked list vs array only really matters when order is relevant. Based on your description you have an unordered set of animals, so you can do constant time removals/insertion in both linked lists and arrays. In that case, array is usually preferable, for speed and simplicity purposes. The main problem with arrays is the fear of a realloc if you run out of space.

If you aren't working in parallel and don't care for order you can just do nigger[i] = nigger[--niggercount]

GTFO.

Xir's being sarcastic user.

Actually spilled my coffee, I was not expecting that.

STOP
Linked list is never the right choice.

ITT: C niggers show again why C programmers are superior to other programmers.

Fuck off Corey

I am planning to add the ability for the animals to split into two if they've eaten an extra amount of food, meaning the simulation could run for 1000s and 1000s of cycles.

Wouldn't I end up with a lot of redudant space in the array after cycling life/death for a while using an array?

Attached: bnU9690.jpg (720x540, 44.05K)

You will learn a lot more writing test cases, than arguing on Zig Forums.

Hey I'm not arguing at all. Like I said I've only been writing this stuff for 2 weeks, so in no way do I think my solution is right. It wasn't a rhetorical question, I am genuinely curious.

Re-organizing arrays and/or having redundant space in it is a lot faster than having to loop through a linked list.

For a test case it's not a big deal, but for future's sake it's better to practice using arrays.

Linked list are almost always for university intellectuals who can't understand the cost of pointer dereferencing and lack of data locality or just ignore it because "muh CY hardware".

keep your animals in an array shaped like the physical space that they're in
bonus: you don't have to care about population
malus: you'll skip a lot of empty space when handling a few animals
if animals can't coexist with food or terrain features, you can put them all in the same array.

Even better, use quadtrees to store your animals and other things. This way you can easily calculate potential collisions between animals. It also gives you logarithmic insertions AND indexing - way better than either linked lists or arrays. To avoid pointer dereferencing/locality (>>974329), store your trees in a single flat array, and calculate the offsets like in a binary tree.

in what sense? an insertion into an array is just a write to memory at a particular index, constant time.
*tilts head and looks quizzically at you*

Maybe he should just write it in 6502 asm on a VIC-20, just to be sure.

The only time that there is a cost to dereferencing a pointer is when you compare it to memory in cache or in register. That's not an accurate statement because most of the time memory is not stored in cache or in register, so most of the time there is no cost to dereference a pointer.

Arrays are linear insertion. Linked lists are linear indexing. Trees are logarithmic insertion and indexing. You will never have an n so large that logarithmic time hurts you, but you will very frequently feel the slowdown from linear time. That's why trees are always the best choice.

he's not going to ever say "I need to find a free space in this array to put this animal" though. He's going to say "this animal at this location wants to divide--is one of these four/eight positions free?"

the b8 worked, look how many autist your triggered. HAHAHAHAHA

If(this->hunger >= TooHungryToLive) RemoveFromList();else Draw();

...

I looked into quadtrees and they sound good for what I will be going, thanks

No bait in just new at trying to program like a white person

(checked)
What a shame that a retard got those quints.
Read that again and then retroactively abort yourself.

If you know how many animals will there be at maximum (and you should), use an array to store all animals. Iterate over it to update it. If an animal dies, swap it with the last member of the array, and reduce its count. Then, iterate again and render.

You can do this because you don't need to keep the animals ordered to be updated, so swapping their orders is cheap. It is even cheaper than mallocing and freeing every time you update the population, and chances are that, if the user can already hold an array as big as the MAX_POPULATION, you won't need to free it any time soon. You can always make a resizable array if you want to, and it will be easier on memory, cache and CPU than a linked list. It is also better than making a 2D grid (seriously user, what the fuck), since it will consume less memory, will iterate over no empty tiles to update, and you couple less entity data and spatial information, which will make your engine more flexible in the long run.

Also, don't use quadtrees to store the actual entity data. While it could be a good idea to build a quadtree from the entity data in order to check for collisions, it should be a "second class game engine structure", and not an actual data storage for all your game entities. Iterating over an entire array, which is what you will do in EVERY logic frame, is still cheaper than iterating over every node of any tree you can imagine.

Don't do this. I know coupling logic and rendering in the same loop over the entity array looks like the logical thing to do, since you only iterate the array once, but it will fuck you over later on. You want to keep them separate to be able to update and/OR render (say, you want to pause the game, but still move around, like a camera mode). Iterate twice if it's needed, and you will maybe even benefit morr from code cache.

What about iterating over a binary tree?

Attached: ClipboardImage.png (300x75, 8.23K)

While complexity wise is probably about the same, some implementations may be less efficient in moderately big data sizes due to jumping back and forth. Unless you implement the binary tree as an array and iterate over the underlying array or use an overcomplicated scheme to more or less iterate it linearly, but why use a binary tree if you are looking at an unordered set and not an ordered collection?

Also, if the binary tree is ordered, you will have to reorder it on reinsertions. Unless you habe a good reason to use a tree, use an array.

Rethinking it, you may want to have a binary tree at some point if you want to implement scripting or direct interactions.You will have to refer to specific objects at some point in time if you want to write scripts, so ordering according to some criteria (UID?) may serve as a primitive database if sorts to search for specific objects without using a linear search.

That is, again, if you want to write a more complex engine. Whatever you do, you want to be able to iterate over items linearly and contiguously (look up Entity-Component-System) so a binary tree could do, BUT you will have worse insertion/removal times if you want to keep it ordered. Probably not an issue and hardly noticeable, but whatever. You could also build a "metadata tree" with pointers to the actual entities later on in another place, separated from the main array, specifically for searches, but you don't achieve anything other than not including the pointer to the next member in the main array if you go that route.

Why don't you explain it to me since you insist on arguing.

Thank you user. I'll take all this onboard.

Hmm. What should it feed on. Random files and processes?