Linked List vs Array -- lots of read/writes

[Halsafar]

If I need to keep track of (n) number of items (n > 0 && n < 4096), these items will be tranversed and updated each frame, if an item is flagged to be removed it will. Array removal may be constant time but is it faster than a linked list linear time in these circumstances? Since I know items will be removed quite often is it not better to use a list? I'd like to clear this up.

[Hack]

What language or development platform are you using?

[Shaggy Hiker]

I would be more interested in whether or not you will be adding items into the middle. If you are, then the linked list should definitely be faster. If you are never adding items into the middle, then what will be happening to the size of the total collection?

1) You will be adding things, but only at the end.

2) Your list will start large, then evaporate over time.

The second seems unlikely, the first has many handling options. A list might be easier if you are adding things only to the end, but it won't be faster if you can avoid re-sizing an array. Hard to get faster than referencing an array, the killer comes from re-sizing. If you can avoid the re-sizing, then the array will probably be faster, if you can't avoid re-sizing, then the list will probably be faster.

I have a collection of organisms (a class). The population of organisms certainly isn't fixed, as some will die, and others will be born, and not at a regular pace. While I could have a linked list that changes in size as the total number of organisms changes, I went with an array at the carrying capacity of the population. I could have set empty slots in this array to 0, but instead I added a Dead boolean property to the organism class. Thus, the number of organisms remains fixed, the array never gets re-sized, but some of the members of the array are passed over quickly.

In summary, I seriously doubt that a linked list would be faster than a fixed size array. However, I seriously doubt that an array whoes memory impact is changing often, can compete with a linked list. I guess it all comes down to the design.

[Halsafar]

Demands for the data structure:
- adding is always at the end.
- removal will occur anywhere.
- Must be quick to transverse.
- It will start size 0, max it can ever be is 4096

See wut is happening, sound channels are being but into a data structure, these channels are grouped with units. Each frame the channels will be tranversed to update their position given the position of the unit it is grouped with. If a channel is done playing it must be removed.

I wish to optimize the removal, since it will be the slowest part. This where my question of what structure to use comes in.

[Shaggy Hiker]

In general, I think memory management is the slowest part. With a fixed maximum size, I'd be tempted to use a fixed size array simply to avoid dealing with memory issues. However, removal would be awkward in a fixed size array, and traverses could easily be inefficient, especially for a fragmented array.

Ultimately, I would suggest that you use a custom doubly linked list where all potential objects are created up front, but only the ones in use are linked in. You are kind of between the advantages of each. Arrays are very fast to traverse.....but linked lists are fast, too, and arrays aren't as fast if there are a bunch of slots that could be skipped. Linked lists are fastest to insert and delete, but if that involves memory manipulations (memory acquisition and freeing), you lose the advantage.

The reason I would go with doubly linked rather than single link is simply that a list node could handle updating the one before and after it on its own (by passing the new address to the ones on either side of it). However, I would be thinking of a fixed array of items that are marked as unused when they are not linked in. To add a new item, you would be selecting the next unused object out of the array and telling it to link itself. There are a variety of ways to limit the need to traverse the array looking for the next unused object. I can think of three of them, but I don't know which is fastest.

I may be rambling, there may be a container already built that does this, but I don't know of it.