![]() There's nothing in the language itself that prevents this - since, as far as the compiler is concerned, implementing Deque just requires that you define a bunch of methods - there's no enforcement of what these methods are supposed to do. Now for an important albeit somewhat confusing note - LinkedList can, for example, implement Deque and have an addFirst that doesn't do what it's supposed to - it can just, for example, print some random text. Based on the docs, the addFirst function needs to add to the front of the Deque, and indeed, with a LinkedList, it will add to the front of the LinkedList (while the front of the LinkedList doesn't need to be the front of the Deque, by looking at the Deque methods implemented in LinkedList, we see that the front of the Deque is the front of the LinkedList, and all the methods add to / remove from one of the sides, do so from the correct side). Queue doesn't actually need to be FIFO (see the docs) (if it needed to be, a LinkedList would also need to be), so LinkedList would have quite a bit of freedom in this regard, so let's continue this explanation using Deque - it has methods to support addition and removal from either the front or the back.īecause LinkedList implements Deque, it needs to implement the addFirst function. The whole piece of paper is still there - you could simply remove the covering, which would be synonymous to casting it back to a LinkedList, which would then allow you to call any LinkedList method on it again.īy the way a LinkedList "normally would" do things I mentioned above, I mean a LinkedList is always a linked-list, even if you assign it to a Queue - it doesn't suddenly start using an array as the underlying implementation, as an ArrayDeque would (which also implements Queue), or something else. Given that most of it is covered, you can't see it's a LinkedList, all you can see is that it's a Queue, so you can only call the Queue methods on it. If you call a Queue method on it, it will still do things like a LinkedList normally would, since that that's what the piece of paper is. Think of the assignment to a Queue as covering all but a little part of this piece of paper which reveals that it's a Queue. Let us define our class template for the Queue implementation.įront and rear instance variable are the linked list node that holds the data and a reference to the next node.To explain with a (perhaps somewhat flawed) metaphor - think of a LinkedList as a piece of paper. ![]() once we remove the tail then there is no way to point to the element that was before a tail in a singly linked list unless we have an extra pointer. Removal of an element happens from the front of the Q and if the linked list tail is the front of a queue then how we going to remove the front element of a Q(the tail of linked list) as the linked list does not allow to remove the tail of it at a constant time O(1). The front of Q is the head and rear of the Q is tail due to the remove operation. You can visit my previous article for custom implementation of linked list in Java. While using linked list for the queue implementation, EnQueue operation is implemented by inserting element at the end of the list and DeQueue operation is implemented by deleting an element from the beginning of the list.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |