The sorted list might be workable, since the list will stay sorted so long as you insert particles in the correct positions, but finding the insertion points would be the tough part.
I'm thinking you could solve this by keeping an array of when your particles were going to die. To do this, you'd need to set an upper limit to a particle's time-to-live. A "cyclical" array of pointers to particles would index them by their time of death. Then, when you need to insert a particle, it's O(1) to find the correct place to put it:
insertion_point.particle = next_particle_to_die_after((current_frame + this_particle\ttl) MOD max_ttl)
Null would mean that no particle will be dying after that time and that any new particles should simply be added to the end of the list. Every frame, you'd need to clean the leading edge of the array by setting next_particle_to_die_after((current_frame + max_ttl) MOD max_ttl) = Null (yes, i know that math's redundant, but i think it better shows the intent.) Also, when you insert a particle, you'll need to update the relevant pointers in the next_particle_to_die_after array.
Ugh. I hope this makes sense. I'll see if I can code up a simple example later, as I have to run out the door now.
A totally different approach would be to replace the oldest particle in each effect in turn. This would even out where the particles came from. This method would likely involve each effect having its own linked list of particles. Effects could have "priority" values so that you might remove particles from less important effects either more often than (or in place of) particles in more important effects. You might also decide to favour removing particles from effects which use more particles than other effects. This method assumes that each effect creates particles with the same time-to-live.
I'm thinking you could solve this by keeping an array of when your particles were going to die. To do this, you'd need to set an upper limit to a particle's time-to-live. A "cyclical" array of pointers to particles would index them by their time of death. Then, when you need to insert a particle, it's O(1) to find the correct place to put it:
insertion_point.particle = next_particle_to_die_after((current_frame + this_particle\ttl) MOD max_ttl)
Null would mean that no particle will be dying after that time and that any new particles should simply be added to the end of the list. Every frame, you'd need to clean the leading edge of the array by setting next_particle_to_die_after((current_frame + max_ttl) MOD max_ttl) = Null (yes, i know that math's redundant, but i think it better shows the intent.) Also, when you insert a particle, you'll need to update the relevant pointers in the next_particle_to_die_after array.
Ugh. I hope this makes sense. I'll see if I can code up a simple example later, as I have to run out the door now.
A totally different approach would be to replace the oldest particle in each effect in turn. This would even out where the particles came from. This method would likely involve each effect having its own linked list of particles. Effects could have "priority" values so that you might remove particles from less important effects either more often than (or in place of) particles in more important effects. You might also decide to favour removing particles from effects which use more particles than other effects. This method assumes that each effect creates particles with the same time-to-live.