We will look at each function of our Stack Adapter individually. As we know, it is also given in the question that Stack adds and removes elements in LIFO manner, i.e. Last In First Out.

Which means, the end at which element will be added lastly will be the first to get accessed. Element is removed and added from one end only.

To make a linked list work like a stack, we need to make use of functions, such that addition and removal occurs at one end only.

We have two options to achieve this: we can perform these operations like addition and removal either at the beginning or at the end.

If we use the linkedlist which is in java then it does not matter which way we choose to do it because addition and removal at end as well as beginning are O(1) i.e. take constant time to perform their action.

But if you use the linked list which we implemented then we chose to operate the starting of the linked list.

**Why?**

We do so because the functions; addFirst, getFirst and removeFirst are of O(1) i.e. take constant time to perform their action.

Whereas the function removeLast which we implemented takes O(n) time, therefore we discard the idea of operating at the end of the linked list.

Let's look at what needs to be done in each function of Stack using the functions addFirst, removeFirst and getFirst.

Push

**Time Complexity: O(1)**

**Space Complexity: O(1)**

Whenever an element is pushed inside the stack it means an element is getting added in the list. So we simply call the addFirst function of list and further pass the val as an argument which will be passed in push .

Pop

**Time Complexity: O(1)**

**Space Complexity: O(1)**

Whenever an element is pupped it means an element is removed in the list.

So we simply call the removeFirst function inside this function.

Top

**Time Complexity: O(1)**

**Space Complexity: O(1)**

Whenever the function top is called it means that we need to return the value of top most (which is the first) element of stack. For this we will call getFirst() function, which will return us the value of top of stack.

Size

**Time Complexity: O(1)**

**Space Complexity: O(1)**

Whenever the function size is called it means that we need to return the size of the stack. For this, it is quite obvious that we call the size() function of the list, which will return us the size of the stack.