Stack Implementation and complexity
Stacks are linear collections of elements and are classified as an abstract data type. New elements pile up on prior elements so the top of the stack is always the last element added. The operation that adds an object to the top of stack is called push. Can we remove an element in the middle of the stack immediately? No we cannot. We can only remove an element from the top of the stack. To remove and return an object at the top of the stack, we use the pop operation. There is one more operation to view the object on the top called peek. The last element that is added to the stack is the first element to be removed from it. We call the order of this stack LIFO (Last In, First Out).
We can implement stacks by using more concrete data types called Array Lists and/or Linked Lists. They are linear data structures. The difference between them has to do with memory allocation. Array Lists reserve contiguous memory blocks, which generally means much more data is reserved than is needed. For example, if we save 5 numbers in an array list, array list occupy 10 bytes memory instead of 5 bytes one and each memory is neighbor. Linked list do not need contiguous blocks of memory and they need the same amount of memory as amount of data we save. So, they need 5 bytes to save 5 number, but the location of each byte is scattered.
ArrayStack
Let’s implement stack with Array Lists. We have 2 options to push item. We append item (add item at the next to the last index) or prepend item (insert item at the first index).
‘push’ with appending an item
First, we are going to append an item to our Array Lists Stack. The running time is O(1)*. * means average. Why is it important to say that the runtime is “constant on average” rather than simply constant? That’s because it takes a long time to create new contiguous blocks (usually copy the length of the block) and add item if the block is full already, otherwise the running time is O(1) to add item to the next to the last index.
Next, we perform the ‘peek’ operation. We know the length of the array list, and the last item we add is the item at the last index of the array list because we can simply append the item. Therefore, the item on the top of the stack is the item in index (the length of the array list)-1. This running time is O(1).
How about pop? We can use the built-in function ‘pop’, which returns and removes the last item. This running time is O(1)*.
‘push’ with prepending an item
When we append item to push, the running time for each operation is constant. We have one more option to push item. How long is the running time for each operation, when we insert item to the first index?
Let’s add new item at index 0. Wait… There is an item at index 0 already. How can we insert the new item at index 0? The answer is to create a new array list with the new item at the first index, pushing all other values up the list.Thus, we need another block of memory and have to copy the items. The running time is O(n) for n items in the last array list.
We implement peek next. We returns the item at index 0 because the last item we push on the top is the first item in the array list. This running time is O(1).
Finally, we perform the ‘pop’ operation. We are going to remove and return the first item of the arraylist. We need another contiguous block of memory to duplicate the items except the first item. Therefore, it takes O(n) for n items in the arraylist.
Let’s summarize running times of each implementations.
LinkedStack
We are going to implement stack with linked list. We have two starting ways of pushing an item to our Linked Stack. We append a new node after the tail (the last node) or prepend new node before the head.
‘push’ with appending an item
Let’s implement the ‘append’ operation first. We know where the tail node is. So, we point the original tail of our list to the new node and identify our new node as the list’s new tail. This running time is O(1).
Next operation is peek. We know the node at the “top” of the stack: it’s the tail! We can get the item with running time O(1). The item is tail.data.
Oh, easy so far huh? It seems we may be able to do the ‘pop’ operation with running time O(1). Let’s implement it together! We want to get the item in the tail and delete the tail.
Steps for ‘pop’ is below.
- Get a item in the tail node.
The first implementation is simple. We can get a item with tail.data. This running time is O(1).
2. Before deleting the original tail, we need to update tail pointer.
We point the node before the original tail as tail. We know the tail node, but we do not know where the node before the tail is because each node points its next node not the node before it. Therefore, we need to loop through this linked list from the head to the node before the tail and check whether node.next is the tail or not. If so, we point the node before the original tail as tail. This running time is O(n) for n items in the linked list.
3. Delete the original tail node.
The last step that is deleting the original tail node is simple. The new tail node that is the node before the original tail still point the original tail, but tail node should not point any node because it is the last node in the linked list. So, we make tail.next point None; we no longer know where the original node is.
Hurray! It’s done! The total running time is O(n) because we ignore constant time when we have linear running time.
‘push’ with prepending an item
We prepend new item at the head to ‘push’. Let’s analyze this running time. We need to create new node that has new item; O(1). Next, we make the new node.next point the original head to connect new node and the linked list; O(1). Finally, we change head pointer from the original head to new node; O(1). Therefore, the running time of ‘push’ operation with prepending is O(1).
How do we implement ‘peek?’ This is a simple implementation. We know the head and the head item is the last item that come to the LinkedStack. We can get this item with head.data. This is O(1).
We implement ‘pop’ operation with the opposite way to ‘push’. First, we get the item in the head with head.data; O(1). We need point the head as current node and the node next to the original head as head; O(1). Then, we remove the current node (the original head) from the linked list by making the node point None; O(1).
Summarized graph is below;
Summary
Time complexity for Stack operation is different even though we use the same data structure. We want to use less time complexity because it’s time efficient and cost effective. When we use Array Lists to implement Stack, we should append new item to ‘push’. On the other hand, we should prepend new item to ‘push’ when we use Linked Lists. We should take into account the running time of more than one implementation if we are to find the best one.
