What is the difference between linkedlist and queue?

Question

I'm new to data structures and it seems like both data structures have more similarities.

In this answer it says that there is a difference in interface. Please explain it.

Answer 1

I had the same question as you! This is what I found:

A Queue is essentially just more restrictive than a LinkedList. For example, in a LinkedList you can use the method .add(int index, Object obj), but if you try doing that with a Queue interface, you’ll get an error, since with a Queue you can only add elements at the tail end. Similarly, in a LinkedList you can use .remove(int index) as well as .remove(Object obj), but attempting to do this with a Queue will result in an error, since you can only remove an object from the head. So, in essence, the Queue just has less options when it comes to methods you can use on it. (There might be more to it than that, but that’s what was most pertinent to me.)

There are some similarities between the two. For example, they both have the .poll() method, and the result is the same: removes the head element from the Object.

Here are some links in which you can compare the methods of the two (scroll to the bottom of each page to see them all, and you’ll see immediately that LinkedList has a lot more):

https://www.geeksforgeeks.org/linked-list-in-java/ (LinkedList) https://www.geeksforgeeks.org/queue-interface-java/ (Queue)

Answer 2

A queue is any data structure that is "FIFO = First-In First-Out." It's a waiting-list. (In Britain, the term is used in ordinary conversation ... you "wait in a queue" not "wait in line.")

A stack is any data structure that is "LIFO = Last-In First-Out." It's a pushdown stack like the stack of dishes in a cafeteria.

Linked lists are a possible implementation of either such structure. It consists of nodes which contain pointers to adjacent nodes in the list.

However, there are many other implementations. "Trees" of various kinds can also be used to implement both queues and stacks. Ordinary arrays can do it, although of course arrays cannot "grow."

Ideally, these days, you simply use an appropriate "container class" in your favorite language and fuhgeddabout how it actually was implemented. "You know that it works, therefore you don't care how." Actual implementation of such things is probably an academic exercise.

Answer 3

In Java (and probably other languages too), a LinkedList implements the Queue interface. So in essence, a LinkedList is a Queue; it has all features that a Queue does and more. Keep in mind, a Queue is not a LinkedList, as a LinkedList is built and expanded upon a Queue.

See this:

Answer 4

A link list is a list of nodes. Each node contain an address field and that address field holding the address of its next node. The reason for this kind of structure is to traverse through the list from its first node till last node. This type of structure is called singly link list. A link list can also be doubly linked, in that structure a node will have two address field where one field will store the address of its previous node and one address will hold the address of its next node. Most important thing of a link list is that its first node address must be stored in an address variable so that we can traverse through the link list at any time.

But Queue can be a link list or an array of nodes. In a list a node can be insert at any place. But in queue a new node must be inserted at the beginning of the list. A queue is working on basis of FIFO i.e. first in first out basis. Hence when you use the pop command on a queue if it is a link list it must remove the last node of the list and return the value of that last node. Hence a queue can be a list as well but with a principle called FIFO based.

You will get more information online. Read properly and try to understand the difference.

Answer 5

List is just a list of things (items, objects whatever). For example a list of courses you are taking in your semester. A list of songs that you are listening. A list of answers of this question on this page. There is no order associate with a list. You can add an item to a list anywhere, you can take an item off the list from anywhere, it doesn't change the definition of a list. Its just a grouping of similar (or not so similar) items.

Now consider a list of people standing in front of ATM machine or a bank teller. This list has to observe a particular order. The first person in the line (list) is the one that will be served first (and will be the first to leave this list). A new person coming in will be standing as a last person in the queue and will be served after everyone in front of him has been served. The people in middle of the list are not supposed to jump the line. This is an example of a Queue. You can also guess what a priority Queue would be (think Airlines with silver and gold members on check-ins).

I hope this explains the difference.