Time complexity of a Stack ADT implemented using a Linked List

pointers data-structures stack time-complexity abstract-data-type
dvanaria picture dvanaria · Jun 30, 2011 · Viewed 10.7k times · Source

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

Viktor Dahl picture Viktor Dahl · Jun 30, 2011

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]

Pop:

[1]->[2]->[3], returning 5

Related questions

C free and struct

My question is about C free() function for deallocating memory blocks previously allocated with malloc(). If i have a struct data type compose of several pointers, each of them pointing to different memory locations, what would happen to those memory …

Read More
What is satellite information in data structures?

Taken from Introduction to Algorithms by Thomas Cormen: "To keep things simple, we assume, as we have for binary search trees and red-black trees, that any “satellite information” associated with a key is stored in the same node as the …

Read More
What are the differences between a pointer variable and a reference variable in C++?

I know references are syntactic sugar, so code is easier to read and write. But what are the differences?

Read More