Ask coding questions

← Back to all posts
Why the heck is LinkedList the default implementation of Queue in Java?
h
SixBeeps

Okay so,

I was working on a Java coding challenge that called for the use of a queue. Neat, I like queues. But when I learned queues in my data structures course, we never used the standard implementations, queues included. So when I heard that Java's LinkedList class was the recommended subclass for Queue, I was a bit shocked.

I mean yeah, they do have similar methods and things like that, but I would have thought an array-based implementation would have been a whole lot faster and memory-efficient. Does anybody happen to know why there isn't one?

Voters
SixBeeps
Comments
hotnewtop
theangryepicbanana

I would think that a linked list would be more efficient for a queue because they require fast (and efficient) insertion and deletion. Linked lists are obviously good at this (being O(1) for insertion and deletion, particularly if you also keep track of the end of the links), which is much better than arrays, where you would have to re-allocate an entire array for every addition/removal

SixBeeps

@theangryepicbanana I guess that makes sense, but if the queue size is fixed (seems like a reasonable restriction in a lot of cases) then reallocation is unnecessary. Then, you can keep track of the head/tail indices, making pushing and popping O(1). Add on the fact that objects like linked list nodes (which wrap around the queued item) inherently take up more memory at runtime compared to just an array entry (nothing wraps around the queued item) and arrays look better. Why is there no array implementation then? Is there something wrong in my assumptions?

theangryepicbanana

@SixBeeps A fixed-size queue doesn't seem that helpful ngl. If you really need one, you should probably use a Vector instead lol

SixBeeps

@theangryepicbanana There has to be some practical usage of a fixed-size queue...

But right now I can't think of any. Also, by "vector", are you talking about C++'s dynamic sized array structure?

theangryepicbanana

@SixBeeps nope, Vectors in java are like arraylists that you resize manually

SixBeeps

@theangryepicbanana Why would you use a resizable structure if you know the size is never going to change? Now I'm just confused.