I would definitely recommend a quadtree. As you mention yourself, most grids would be empty most of the time. Managing linked lists is a lot of work considering the amount of bullets, that will travel several grids, before getting close to any enemy.
By using an algorithm with low tolerance for enemies in large areas, you should be able to create mostly enemy free regions where the bullets can travel without checking for collision.
That being said, you need a big game before performance should be an issue. Assuming you are using sweep scan with aabb.
As an alternative to a dynamic quadtree you could let several cells share a linked list. i.e. 5x5 cells share one linked list = 3600 in a 300x300 map. And no, a linked list with no elements uses very limited space.