in an assingment, i have to implement a deque ( double ended queue ). the underlying datastructure is allowed to be arrays or linkedlist. only that im not allowed to use any prebuilt java api that does the above. (like the java.util.LinkedList api)
implementing the above using doubly linked list seems straighforward , but i was also looking for how it can be done using arrays. I did a rough sketch on my own, but was facing a bit of hurdle in the resizing methods.
on google-ing for some solution, i came across here where they were saying :
If you "float" both ends of the array, you can have constant-time inserts and deletes, except for when you need to resize the array when it fills up.
i remember that i did learn about "float"-ing an array.. but i cant recollect it, neither did i find anything substantial when i searched for it on the web.
I want to use arrays because i liked the concept of amortized running time , so wanted to try my hand at it...
any help regarding what "float" ing both ends of an array means? also any guide into an efficient way to solve the assingment will be really helpful :)