### structures when inserting, deleting and searching

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 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

SHARE