Implement Stack with Linked List
Implementation of stack using singly linked list.

Question

Implement Stack with Linked List

Implementation of stack using singly linked list.

Accepted Answer

I simply implemented pop and push operations of stack using insert and delete from front operations of linked list and wrote its fully functional code with comments.

Accepted Answer

Best Approach

Maintain a linked list. Keep track of its head, and size at all times, and update them accordingly whenever a new operation is performed.
Following is the way we can implement all functions of the stack using linked list:
1. First, initialize a head node, and the size of the list as NULL and 0 respectively.
2. Then for push function, insert new elements at the head of the list, i.e. the new element will become the new head of the list and the previous head will become the next of new head. Also, increase the size by 1.
3. For pop, just move the head to its next and delete the original head(if required). Also, decrease the size by 1. If the head was null or None (i,e, the list is empty), do nothing.
4. For getTop, simply return the head’s data or -1 if the list is empty.
5. For getSize, simply return the size of the list
6. For isEmpty, return true if the size is 0, otherwise, return false

Space Complexity: O(n)Explanation:

O(N) where N is the number of elements pushed in the stack.

Time Complexity: O(1)Explanation:

O(1) for all operations. Since we are inserting and deleting elements from the head of the list itself, constant time is spent on pop and push functions. The other functions are also simply returning a value so they also take constant time.

Top Cadence Design Systems Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Cadence Design Systems Software Developer