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.

Omid CompSCI
  • 1,861
  • 3
  • 17
  • 29
  • 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. – Tim Biegeleisen Jul 27 '16 at 04: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) – Omid CompSCI Jul 27 '16 at 04:41

1 Answers1

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

Community
  • 1
  • 1
alexscasa
  • 76
  • 3
  • 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. – Omid CompSCI Jul 27 '16 at 05:21
  • 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. – alexscasa Jul 27 '16 at 05:29
  • 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! – Omid CompSCI Jul 27 '16 at 05:34
  • Here is a better answer, since mine isn't a traditional FIFO: http://stackoverflow.com/questions/19039972/linked-list-vs-vector Next time, a simple Google search will yield quicker results. – alexscasa Jul 27 '16 at 05:35
  • Glad I could help! Hope the link provides more clarity. – alexscasa Jul 27 '16 at 05:35
  • wait, queues are fifo based so how come you'd be meddling with data anywhere else? – xyf Oct 16 '22 at 07:25