Wednesday, July 01, 2009
Javascript Deque
Doubly ended queue code is just a whole lot cleaner if you go with dummy head and tail nodes to avoid special cases. I put together this Javascript example:
A Javascript array has the methods available (push(), pop(), shift(), unshift()) to be used as a deque but of course being an array you shouldn't be adding and removing from anywhere but the tail end if you need top performance. The following provides for a comparison between my deque and a regular Javascript array for adding and removing items from the head or tail of the data structure.
Subscribe to:
Post Comments (Atom)
What are you using this for?
ReplyDeleteNothing! I was looking at some code in a book and the authors proceeded to show a doubly ended queue example which, because they didn't use dummy head and tail pointers had all this special case code. You know, add the node this way, unless the dequeue is empty in which case you do this... This reminded me of a dequeue implementation I wrote in college using C that used the dummy nodes to avoid special case code. To exercise my Javascript skills a bit I decided to see what it might look like in Javascript and how it would compare on performance to a Javascript array because it provides shift and unshift for working with the head...
ReplyDeletehey david - i actually have a use for this. can I use this under an MIT license or do i have to reimplement?
ReplyDeleteJust use it.
ReplyDelete