Time complexity of a Stack ADT implemented using a Linked List

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?

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

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.

The basic functionality of stack is that both push and pop operations are performed from the top of the stack i.e. at the head of the linked list. A head pointer is maintained which points to the first element in the list when a linked list is implemented and hence put(x) and get() operations used for adding/removing an element from stack will always be O(1).