• Linear
  • Basically Array/Linked List with limitations
  • Elements are First In Last Out (FILO) and Last In First Out (LIFO)

Time Complexity

  • O(1) to Insert push()
  • O(1) to Delete pop()
  • O(1) to See the value on top of the stack peek()
  • O(n) to search for a value


Implementation with Array

  • Visual
  • push(), pop() & peek() from the back
  • Can use Dynamic Array, then the expansion is handled automatically

Implementation with Linked List

2 implementation comparison

Both support Stack Operations without much difference

Time Efficiency

  • Array has Cache Locality to take advantage of CPU Cache for extreme fast access. However, array has fixed size. If there isn’t any space left in the array, new insertion needs to create a new array and transfer all elements to that new array, and the time complexity will be O(n)
  • Linked List has to use extra time to perform pointer operation
  • Conclusion: Array has slightly better time efficiency, since expansion is a low frequency operation, while pointer operation occurs whenever there is an insertion operation. However, Linked List has more stable performance

Space Efficiency

  • Array get a pre-defined Main Memory size, and each expansion is usually double the original size which may exceed the actual demand
  • Linked List needs actual Main Memory to store the Memory Address of the next node
  • Conclusion, we cant determine which uses more Main Memory, it depends on the use case. If we already know the total elements to store, Array is better, else Linked List may be maybe