### Efficiency of stacks, queues, linked lists, doubly linked lists, and more data

### structures when inserting, deleting and searching

Big O notation *is defined by Wikipedia* as a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann,[1] Edmund Landau,[2] and others, collectively called Bachmann–Landau notation or asymptotic notation.

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.[3] In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem.

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

When you are studying Data Structures and Algorithms is one of the things that you learn and you *should* not forget.

When I learnt them was useful to have them in an ordered table written in my notebook. So here it comes; a quick cheatsheet to check whenever you might need it.

In the following table you have the name of the Data Structure, and the classification for

search, insert, and delete in the Average and the Worst Case.

Data Structure | Search AC | Insert AC | Delete AC | Search WC | Insert WC | Delete WC |
---|---|---|---|---|---|---|

Stack | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |

Queue | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |

Sorted Array | O(log n) | O(n) | O(n) | O(log n) | O(n) | O(n) |

Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |

Doubly Linked List | O(n) | O(1) | O(1) | O(n) | O(1) | O(1) |

Binary Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |

Binary Search Tree | O(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |

AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |

Hash table | O(1) | O(1) | O(1) | O(n) | O(n) | O(n) |

Here some basic implementations in Python.

```
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from namedlist import namedlist
class Stack():
__slots__ = ["_values"]
def __init__(self, iterable=None):
self._values = []
if iterable is not None:
for value in iterable:
self.push(value)
def __len__(self):
return len(self._values)
def empty(self):
return len(self._values) == 0
@property
def top(self):
assert not self.empty(), 'No elements'
return self._values[-1]
def push(self, value):
self._values.append(value)
def pop(self):
assert not self.empty(), 'No elements'
return self._values.pop()
def clear(self):
self._values.clear()
def copy(self):
new_stack = Stack()
new_stack._values = self._values.copy()
return new_stack
def __eq__(self, other):
return self._values == other._values
def __repr__(self):
return ('Stack([' + ', '.join(repr(x) for x in self._values) + '])' )
```

```
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from namedlist import namedlist
class Queue():
_Node = namedlist('Node', 'value next')
__slots__ = ['_front', '_back']
def __init__(self, iterable=None):
self._front = self._back = None
if iterable is not None:
for value in iterable:
self.enqueue(value)
def is_empty(self):
return self._front is None
@property
def front(self):
#assert not self.is_empty(), 'Empty queue'
return self._front.value
@property
def back(self):
assert not self.is_empty(), 'Empty queue'
return self._back.value
def clear(self):
self._front = self._back = None
def enqueue(self, value):
new_node = Queue._Node(value, None)
if self.is_empty():
self._front = self._back = new_node
else:
self._back.next = self._back = new_node
def dequeue(self):
assert not self.is_empty(), 'Empty queue'
value, self._front = self._front
if self._front is None:
self._back = None
return value
def copy(self):
new_queue = Queue()
if not self.is_empty():
node = self._front
new_queue._front = back = Queue._Node(node.value, None)
while node.next is not None:
node = node.next
back.next = back = Queue._Node(node.value, None)
new_queue._back = back
return new_queue
def __len__(self):
n = 0
node = self._front
while node is not None:
node = node.next
n += 1
return n
def __eq__(self, other):
x = self._front
y = other._front
while x.next is not None and y.next is not None:
if x is None and y is None:
return True
x = x.next
y = y.next
def __repr__(self):
values = []
node = self._front
while node is not None:
values.append(node.value)
node = node.next
return 'Queue([' + ', '.join(repr(x) for x in values) + '])'
```

(*) Some implementations are based or taken from a Data Structures Course,

that were originally written and published in :

https://github.com/gosella/DS/tree/master/Python