Well, it seems like that different people have lots of different ideas on the way that this project should go. It seems like that double linked list is must for my project. ( Personally my opinion too is that it is better to construct the most used structures rather than trying to code data structures that are rarely used by few people).
Just an addition to the things you have been discussing about, how about a Dequeue?
