title: Time complexity of a Stack ADT implemented using a Linked List
body: <p>What is the time complexity of the put(x) and get() functions for a Stack abstract data type that is implemented using a LinkedList?</p>
  
  <p>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).</p>
  
  <p>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).</p>
  
  <p>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?</p>