1

So I know that implementing a stack or queue using vector or an array have these properties:

  • O(n) for searching
  • At least with array implementation (All on the stack rather than heap)
  • O(1) peek top/front or back/bottom

And if array's space constraint is an issue you would implement the stack or queue using a vector, so why would anyone implement one of these data structures using a link list? Any real life examples would be great, and Big O notation of some basic functionality if differ from array/vector implementation.

Improve this question
2
  • A LinkedList is a queue in Java, and you might want to use it over an array if you want the ability to grow dynamically. Commented Jul 27, 2016 at 4:39
  • If you wanted to grow dynamically couldn't you have just implemented the queue or stack using a vector? Sorry I was more geared toward C++ (Making your own stack or queue from scratch) Commented Jul 27, 2016 at 4:41

1 Answer 1

Reset to default
5

For the queue, a linked list would provide faster results when manipulating data in the middle of the queue (add/delete): O(1). If implemented with an array or vector, it would be O(n) because you have to move other elements to create the space for the new element, or fill the space of the deleted element.

As far as the stack, I refer you to this answer: Linked list vs. dynamic array for implementing a stack

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

Thank you, I read the article for stack. However, I don't see the need of inserting in the middle of the queue, hence a queue is supposed to be First-In-First-Out Algorithm, and if anything you can insert in the back or front "Deque". That would be a link list in general, if you start adding other functionality like insertbeforeLast, insertBeforeIndex, etc.
Sorry I didn't include the example of implementation in my response. You would need to manipulate the middle of a queue if it is a priority queue. An element with a high priority will need to be added before other elements with less priority, but after elements of higher priority (in the middle). Also, in the real world, people can drop out of queues so a deletion may be required in the middle of the queue.
Ah, a Priority Queue! Great example, totally makes sense and much easier to implement this using a link list rather than dealing with all the shifting of indexes,etc. Thank you!
Here is a better answer, since mine isn't a traditional FIFO: stackoverflow.com/questions/19039972/linked-list-vs-vector Next time, a simple Google search will yield quicker results.
Glad I could help! Hope the link provides more clarity.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.