Python Data Structures and Algorithms

Data Structures and Algorithms (DSA) is one of the most important topics in computer science that every CS student must be proficient in and even non-CS students must have basic understanding of it. It is said that DSA is like bread and butter, necessity of CS. This repository is made for those students (like me 😎) who are eager to learn and want to implement data structures and algorithms.

Instructions

1. To get started make sure that you have python v3+ installed on your computer.
2. Once python is installed on your machine, just clone or download this repository.
3. Now cd <folder-name> into downloaded repo.
4. Now run pytest . to run all tests or pytest <folder-name> to run specific tests.

Example

Let's assume that you want to run tests for stack, then the syntax to run it would be:

cd python-data-structures-algorithms
pytest stack

Data Structures

Name	Time Complexity	Space Complexity	Description
Graphs
Directed Unweighted	-
Directed Weighted	-	-	-
Undirected Unweighted	-	-	-
Undirected Weighted	-	-	-
Heaps
Max Binary Heap	insert, delete: O(log(n))	O(n)	n: # of elements
Min Binary Heap	insert, delete: O(log(n))	O(n)	n: # of elements
Linked Lists
Circular Doubly LL	push, pop, shift, unshift: O(1) insertMiddle, deleteMiddle: O(k)	O(n)	n: # of elements k: pos of node to act on
Circular LL	push, pop, shift, unshift: O(1) insertMiddle, deleteMiddle: O(k)	O(n)	n: # of elements k: pos of node to act on
Doubly LL	push, pop, shift, unshift: O(1) insertMiddle, deleteMiddle: O(k)	O(n)	n: # of elements k: pos of node to act on
Singly LL with preserve order	pop, shift: O(1) insert: O(n) delete: O(k)	O(n)	n: # of elements k: pos of node to act on
Singly LL	push, pop, shift, unshift: O(1) insertMiddle, deleteMiddle: O(k)	O(n)	n: # of elements k: pos of node to act on
Queues
Circular Double Ended Q	insert, delete: O(1)	O(n)	n: # of elements
Circular Q	insert, delete: O(1)	O(n)	n: # of elements
Double Ended Q	insert, delete: O(1)	O(n)	n: # of elements
Priority Q	insert, delete: O(log(n))	O(n)	n: # of elements
Simple Q	insert, delete: O(1)	O(n)	n: # of elements
Stack
Stack	push, pop: O(1)	O(n)	n: # of elements
Trees
AVL Trees	Insert: O(h) BFS, DFS(In, Pre, or Post): O(n)	Insert: O(h) BFS, DFS(In, Pre or Post): O(n)	h: height of the tree n: # of nodes
Binary Search Tree	Insert: O(n) BFS, DFS(In, Pre, or Post): O(n)	Insert: O(h) BFS, DFS(In, Pre or Post): O(n)	h: height of the tree n: # of nodes
Simple Binary Tree	Insert: O(n) BFS, DFS(In, Pre, or Post): O(n)	Insert: O(n) BFS, DFS(In, Pre, or Post): O(n)	h: height of the tree n: # of nodes

Algorithms

Name	Time Complexity	Space Complexity	Description
Searching
Binary Search	O(log(n))	O(1)	n: # of elements
Interpolation Search	Avg Case: O(log2(log2(n))) O(n) when items are distributed exponentially	O(1)	n: # of elements
Linear Search	O(n)	O(1)	n: # of elements
Ternary Search	O(log3(n))	O(1)	n: # of elements
Sorting
Binary Insertion Sort	O(n2)	O(n)	-
Bubble Sort	O(n2)	O(1)	-
Bucket Sort	O(n2)	O(1)	-
Counting Sort	O(n + k)	O(k)	-
Heap Sort	O(nLog(n))	O(1)	-
Insertion Sort	O(n2)	O(1)	-
Merge Sort	O(nLog(n))	O(n)	-
Quick Sort	O(n2)	O(log(n))	-
Radix Sort	O(nk)	O(n+k)	-
Selection Sort	O(n2)	O(1)	-
Shell Sort	O(n2)	O(1)	-

Contribution

This repository is for learning how to implement data structures and algorithms, and since contributions of others won't really teach me how to implement it by myself, I won't be accepting any pull requests. However, feel free to fork this repo and modify the code to play around various data structures and algorithms. Moreover, while playing around the code, if you find anything unusual or wrong in the implemetation, I would highly appreciate if you create an issue on the same.

License

This repository is released under the MIT license. In short, this means you are free to use this software in any personal, open-source or commercial projects. Attribution is optional but appreciated.

HAPPY CODING 💻
HAPPY LEARNING 📚