Why not use queues? Sounds more like a queue when you say remove the first and if its valid add to then end. Pop, update, if alive, add to the end of the queue. You may not be able to get a specific object that is in the middle of the queue but most of the time I never want to do that.
Also, from my experience, running through arrays/collections that are about 1-5k in size is really not that expensive. Its the updating that will slow you down. Heck I really don’t think 25-50k is that massive. Now if you have many arrays that are all large and all need to be updated, sure it can get cumbersome but still. Anyways sorry for getting off topic.
The easiest way would be to use an object that has say an x and y value for the location and updating and a sprite/image that you will draw on the screen.
You can store it in an arraylist as its really easy to use. Then when its suppose to die just do remove(); Not most efficient but worry about making things faster when you have something to make faster.
You may also want some sort of collision method to see if its hitting a bad guy or if its off the screen. Maybe if your getting more complex give it some sort of life that you subtract from every update and when it reaches 0 remove it. This way you wont worry about it going off screen as much and maybe you can make bullets not go on forever but what fun would that be.