Time complexity of a Stack ADT implemented using a Linked List

Question

What is the time complexity of the put(x) and get() functions for a Stack abstract data type that is implemented using a LinkedList?

My first thought was they are both O(1). But if get() has to traverse from the head node to the last element in the list to find the one to remove and return, the get() function will be O(n).

The put(x) function as well has to traverse the entire list to find the last node, where it will install a new node. So this too would be O(n).

If a "specialized" version of a LinkedList were used, one that always kept a pointer to the last node in the list, these would both become constant time operations. Am I correct in understanding that a standard implementation of a LinkedList wouldn't have this available?

Answer 1

You don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they are both O(1).

Stack contains 1,2,3:

[1]->[2]->[3]

Push 5:

[5]->[1]->[2]->[3]  // inserted 5 at the front/top

Pop:

[1]->[2]->[3]  // removed 5 from the front/top

Answer 2

For a doubly linked list the stack operations push and pop should both be O(1).

If you are stuck with a singly linked list, assuming you are ok with the constant overhead of keeping a pointer to the tail as well as the head, you can have O(1) queue operations of enqueue and dequeue. And because with amortized constant overhead you can make a stack out of two queues, in the end, you can achieve O(1) push and pop.