My learning journey of Data Structures and Algorithms in Python (work in progress)
Back before I started programming, I was introduced to a website for programmers to test their skills called LeetCode, which provides coding interview questions for coders to try out. Curious, I went to look at the questions and found myself overwhelmed by how bizzare the questions look. I took a look around the internet to see how people solve LeetCode questions and realised they understood this important programming concept that I haven't touched before - Data Structures and Algorithms.
Hence the birth of this repository, for me to bridge this gap.
(Funnily enough, when I first looked at LeetCode I had no idea how to navigate their website. I saw they had an answer template where you can type in your code answers but it contained many different kinds of programming languages. Obviously I went for the one I knew, Python. But then there was 2 options, Python and Python3. Then I looked at the starting code (at the time I didn't know about Object-Oriented Programming and Classes yet) and I couldn't tell which was the one I was supposed to use. Furthermore, I was literally unable to understand any of the questions and give any relevant answer. So as you can see, this is how disastrous my first LeetCode experience was. (Eventually I found out I was using Python3, which I'm pretty sure is the version everyone using Python is using, after copy-pasting some of the usual codes I've written and asking ChatGPT hahaha...))
Learning and Practices are both organised under each folder for their respective Data Structure/Algorithm.
Most of my sources come from this Youtube playlist by codebasics:
-
-
- Tutorial 1 - What are Data Structures
- Tutorial 2 - Big O Notation
- Tutorial 3 - Concept of Recursion
- Tutorial 4 - Arrays (Data Structure)
- Tutorial 5 - Linked Lists (Data Structure)
- Tutorial 6 - Hash Tables (Data Structure)
- Tutorial 7 - Stacks (Data Structure)
- Tutorial 8 - Queues (Data Structure)
- Tutorial 9 - Trees and General Trees (Data Structure)
- Tutorial 10 - Graphs (Data Structure)
-
On Algorithms (Searching and Sorting Algorithms):
- Tutorial 11 - What are Algorithms
- Tutorial 12 - Binary Search (Searching Algorithm) and Linear Search (Searching Algorithm)
- Tutorial 13 - Bubble Sort (Sorting Algorithm)
- Tutorial 14 - Quick Sort (Sorting Algorithm)
- Tutorial 15 - Insertion Sort (Sorting Algorithm)
- Tutorial 16 - Merge Sort (Sorting Algorithm)
- Tutorial 17 - Selection Sort (Sorting Algorithm)
The 'Introduction_to_Data_Structures_and_Algorithms.txt' file summarises everything that I learnt in this Data Structures and Algorithms learning journey.
What are Data Structures?
Data Structures are a specificied way to organise, manage, and store data in a specific memory layout. Similar to that of a physical container, which you can put and keep stuff in it.
Examples are more finite compared to Algorithms, due to the fundamental concepts of Data Structures being well-defined, and that each of them serve a clear, specific purpose in managing and organizing data efficiently.
Source(s): https://www.youtube.com/watch?v=_t2GVaQasRY&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=1&t=5s (codebasics)
What is the Big O Notation?
The Big O Notation measures the running time (time complexity) or space requirements (space complexity)
for your computer program/algorithm (not very accurate to say it measures running time for your Data
Structure) grow as input grows for the worst case scenario.
Source(s): https://www.youtube.com/watch?v=IR_S8BC8KI0&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=2 (codebasics)
What is the concept of Recursion?
Recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursive function works and are functions that calls itself within the function.
Source(s): https://www.youtube.com/watch?v=9bsK03SlmNM&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=20 (codebasics)
What is an Array?
An Array is a linear data structure that is a collection of similar data elements stored at contiguous memory locations.
Source(s): https://www.youtube.com/watch?v=gDqQf4Ekr2A&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=3 (codebasics)
What is a Linked List?
A Linked List is a linear data structure consisting of nodes where each node contains a data field and a reference(link)/pointer to the next node in the list. Each node consists of 2 components, data of an element in the Data Structure, and a pointer.
What is a Node?
Each node is stored at a random memory space (not continuous to other elements of the Linked List Data Structure, unlike Arrays) and is linked to other nodes via a pointer. (which stores the address of the memory storing the next element)
In this tutorial, we explored 2 types of Linked List Data Structures,
- (Singly) Linked Lists
- Doubly Linked Lists
Source(s): https://www.youtube.com/watch?v=qp8u-frRAnU&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=4 (codebasics)
What is a Hash Table?
A Hash Table is a linear data structure that maps keys to values.
A Hash Table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots in memory, from which the desired value can be found. During lookup, the key (object name/string) is hashed (is put through the hash function) and the resulting hash (result after the key is put through the hash function) indicates where the corresponding value is stored.
Note: You might sometimes come across the term 'Hash Map' which is essentially the same thing as a Hash Table (with some very minor differences)
Source(s): https://www.youtube.com/watch?v=ea8BRGxGmlA&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=5 (codebasics)
What is a Collision in Hash Tables? And what is the Problem of Collisions when making Hash Tables?
A Collision occurs when more than one value (of key-pair values) is hashed by a particular hash function hash to the same slot/produces the same hash (or index in the memory array) in the Hash Table being generated by that hash function.
What is Hash Table Collision Handling?
Collision Handling is when we modify our existing Hash Table Data Structure such that it is able to handle these Collisions and still be able to store every key-value pair being given to it at a unique spot in the Hash Table's memory array such that they are still unique and won't override or affect other key-value pairs in the Hash Table.
In this tutorial, we explored 2 ways of Hash Table Collision Handling,
- Seperate Chaining
- Linear Probing
Source(s): https://www.youtube.com/watch?v=54iv1si4YCM&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=6 (codebasics)
What is a Stack?
A Stack is a linear data structure that only opens at one end, stores items and perform operations using the Last In, First Out (LIFO) method. Whenever a new element is added to a stack, it is added to the top of the stack, and the top element is always removed first from a stack.
Source(s): https://www.youtube.com/watch?v=zwb3GmNAtFk&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=7 (codebasics)
What is a Queue?
A Queue is a linear data structure that opens at both ends, stores items and perform operations using the First In First Out (FIFO) method. Whenever a new element is added, it is added from one end of the queue, and all deletions froma Queue are made from the other end, always first removing the first element added into the queue.
Source(s): https://www.youtube.com/watch?v=rUUrmGKYwHw&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=8 (codebasics)
(Side lesson, for the Queue Data Structure excercise 1)
What is Multithreading?
Lets define what a thread is first: A thread is a seperate flow of code execution.
Each program has one thread by default, but we may need to create new threads to execute tasks concurrently within a single program.
Multithreading is a model of program execution that allows for multiple threads to be created and executed within a process, executing independently but concurrently sharing process resources.
Source(s): https://www.youtube.com/watch?v=PJ4t2U15ACo&list=PLeo1K3hjS3uub3PRhdoCTY8BxMKSW7RjN&index=1 (codebasics)
What is a Tree?
A Tree is a collection of non-linear data structures with a hierarchy-based structure with a set of connected nodes. (like those used in Linked Lists Data Structure)
What is a General Tree?
You can sort of think of General Tree as the foundational Tree Data Structure blueprint for all other Tree Data Structure variations, such that other Tree Data Structure variations are modifications of the General Tree.
A General Tree is a Tree Data Structure where each node may have zero or more children nodes for every node (number of children nodes may vary depending on the Tree Data Structure variation).
Source(s): https://www.youtube.com/watch?v=4r_XR9fUPhQ&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=9 (codebasics)
Tutorial 9.1 - Binary Trees (Tree Data Structure variation) and Binary Search Trees (Binary Tree Data Structure variation)
What is a Binary Tree?
A Binary Tree is a variation of the (General) Tree Data Structure, a non-linear Data Structure with maximum of two children nodes for each node. The difference/modification between a General Tree and a Binary Tree is that each node in a General Tree can have zero to infinity number of children, while each node in a Binary Tree can only have a (zero to) maximum of 2 nodes left and right.
Similar to a General Tree, a Binary Tree does not have its Nodes sorted. Usually, by itself, the Binary Tree is not very applicable/useful as its Nodes are unsorted, hence, it is usually implemented as one of its further variations, more commonly in the form of a Binary Search Tree (BST) (aka ordered/sorted Binary Tree).
What is a Binary Search Tree (BST)?
A Binary Search Tree (BST) is a further variation of the Binary Tree Data Structure, sometimes known as an ordered/sorted Binary Tree. The 2 differences/modifications between a Binary Tree and Binary Search Tree is that a normal Binary Tree is unordered, and allows duplicates, while a Binary Search Tree is ordered (by some manner) that allows easy searching of a particular node, and dosen't allow duplicates (its not like BST don't allow, but we tell our BST to not allow it as duplicate data nodes sort of messes up the BST's ordering/sorting and subsequently the search function. We will be able to understand this once we learn how the BST's ordering/sorting works)
By the way, Binary Search Tree are called as such as due to their ordered/sorted characteristic, it increases the efficiency (Big O Notation) of searching (search operation) in a Binary Tree.
Source(s):
https://www.youtube.com/watch?v=lFq5mYUWEBk&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=10 (Part 1) (codebasics)
https://www.youtube.com/watch?v=JnrbMQyGLiU&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=11 (Part 2) (codebasics)
What is a Graph?
A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the Graph.
A node refers to the individual entity storing data, while an edge refers to the line connecting 2 nodes.
There are 2 types of Graph Data Structures:
- Undirected Graph
- Directed Graph
Also, the edges of Graph Data Structures may or may not be weighted.
In this tutorial, out of the 2 common ways to implement Graph Data Structures, as an Adjacency Matrix or Adjacency List, we only covered implementing Adjacency List Graph Data Structures.
In this tutorial, we explored 4 types of Graphs,
- Adjacency List Directed Graph
- Adjacency List Undirected Graph
- Adjacency List Directed Weighted Graph
- Adjacency List Undirected Weighted Graph
Source(s):
https://www.youtube.com/@AmulsAcademy/videos (Amulya's Academy)(referenced from various videos on Graph Data Structures from this Youtube channel)
https://www.youtube.com/watch?v=j0IYCyBdzfA&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=12 (codebasics)
https://www.simplilearn.com/tutorials/data-structure-tutorial/graphs-in-data-structure (simplilearn)
What are Algorithms?
Algorithms are a list set of instructions of how to solve a computational problem. These Algorithms are executed on Data Structures and together, Data Structures and Algorithms, creates a computer program.
Examples are infinite (possibilities are endless, much wider in variety than Data Structures), but common Algorithms that are first taught to new programmers will always be Searching and Sorting Algorithms.
Source(s): NIL
What is Binary Search?
Binary Search is a searching algorithm used in a sorted array that searches for a value by repeatedly dividing the search interval in half and the correct interval to find is decided based on the searched value and the middle value of the interval.
Note that unlike some other Search Algorithms, Binary Search Algorithm works on the concept of the list to be searched, to be sorted beforehand. (So if the list is unsorted then Binary Search Algorithm dosen't work)
In this tutorial, we implemented the Binary Search Algorithm both iteratively and recursively.
What is Linear Search?
Linear search is a searching algorithm where the list or data set is traversed from one end to the other end to find the desired value.
In this tutorial, we implemented the Linear Search Algorithm iteratively.
Source(s): https://www.youtube.com/watch?v=GnZ9ppr_zaI&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=13 (codebasics)
(Side lesson, for comparing the time complexity of Binary Search Algorithm and Linear Search Algorithm in this file)
What is a Decorator?
Decorators are sort of the 'tags' that allow us to wrap other functions within a function (aka a 'wrapper function') in order to extend the behaviour of the wrapped function, without permanently modifying it. The Decorator 'tag' will be the name of the 'wrapper function', where the 'wrapper function' will be used to wrap other functions (pass other functions through it)
Source(s): https://www.youtube.com/watch?v=IVWZxr0kOyI&t=200s (codebasics)
What is Bubble Sort?
Bubble Sort is a sorting algorithm that sorts a list by examining each set of adjacent elements in the list, from left to right, switching their positions if they are out of order. The Bubble Sort Algorithm then repeats this process until it can run through the entire string and find no two elements that need to be swapped.
In this tutorial, we implemented the Bubble Sort Algorithm iteratively.
Source(s): https://www.youtube.com/watch?v=ppmIOUIz4uI&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=14 (codebasics)
What is Quick Sort?
Quick Sort is a sorting algorithm that sorts a list by using the Divide and Conquer technique that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the array. (In these Algorithm tutorials, the only 2 Algorithms (both Sorting Algorithms) that uses the Divide and Conquer paradigm is Quick Sort Algorithm and Merge Sort Algorithm)
In this tutorial, we implemented the Quick Sort Algorithm recursively.
In this tutorial, we explored 2 schemes of Partitioning,
- Hoare Partition scheme
- Lomuto Partition scheme
Source(s): https://www.youtube.com/watch?v=5iSZ7mh_RAk&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=15 (codebasics)
What is Insertion Sort?
Insertion Sort is a sorting algorithm that sorts a list by iteratively building a sorted subarray within the given unsorted array. The algorithm splits the unsorted array into 2 subarrays, the sorted subarray and unsorted subarray. It starts with the first element as the sorted subarray (since a single element is always considered sorted), and then it repeatedly takes the next element from the unsorted part of the array and inserts it into its correct position in the sorted subarray until the whole array becomes sorted (all the elements in the unsorted subarray is brought to the sorted subarray, and there is no more unsorted subarray, and the initial List now only contains the sorted subarray and is now sorted)
In this tutorial, we implemented the Insertion Sort Algorithm iteratively.
Source(s): https://www.youtube.com/watch?v=K0zTIF3rm9s&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=16 (codebasics)
What is Shell Sort?
Shell Sort is mainly an optimised variation of Insertion Sort.
Shell Sort is a sorting algorithm that sorts a list by dividing the array into smaller subarrays and sort each of these subarrays using Insertion Sort Algorithm. The key difference is that the elements within each subarray are not adjacent, but are separated by a certain gap (Shell Sort Algorithm leverages on the idea of gaps). This gap is initially larger, and after each gap's iteration of sorting via Insertion Sort of these smaller subarrays, the gap is gradually reduced during the sorting process until it reaches 1, at which when the gap is 1, this gap's (1) iteration of sorting transitions into a standard Insertion Sort Algorithm.
In this tutorial, we implemented the Shell Sort Algorithm iteratively.
Source(s):
https://www.youtube.com/watch?v=VxNr9Vudp4Y&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=18 (codebasics) (I didn't like codebasics' video on how he explained the Shell Sort Algorithm, so I sourced from other websites for a better explanation of the Shell Sort Algorithm)
https://www.youtube.com/watch?v=IViqgakt-Eg (Geekific)
https://www.youtube.com/watch?v=SHcPqUe2GZM&t=1s (GeeksforGeeks)
What is Merge Sort?
Merge Sort is a sorting algorithm that sorts a list by using the Divide and Conquer technique that divides an array into smaller subarrays, sorting each subarray recursively (via the same Merge Sort Algorithm), and then merging the sorted subarrays back together to form the final sorted array. (In these Algorithm tutorials, the only 2 Algorithms (both Sorting Algorithms) that uses the Divide and Conquer paradigm is Quick Sort Algorithm and Merge Sort Algorithm)
The way Merge Sort Algorithm does this is by continuously splitting the array in half until it cannot be further divided i.e., the array has only one element left (an array with one element is always sorted). Then the sorted subarrays are merged into one sorted array.
In this tutorial, we implemented the Merge Sort Algorithm recursively.
Source(s): https://www.youtube.com/watch?v=nCNfu_zNhyI&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=17 (codebasics)
What is Selection Sort?
Selection Sort is a sorting algorithm that sorts a list by repeatedly selecting the smallest (or largest) element from the unsorted subarray of the initial unsorted List and moving it to the sorted subarray of the initial unsorted List.
In this tutorial, we implemented the Selection Sort Algorithm iteratively.
Source(s): https://www.youtube.com/watch?v=hhkLdjIimlw&list=PLeo1K3hjS3uu_n_a__MI_KktGTLYopZ12&index=19 (codebasics)
Took me about 2-3 months to finish this learning journey. I can see why Data Structures and Algorithms is now dreaded by many, but is yet so important for every beginner to know due to how abstract these concepts are. However, I feel that learning and understanding Data Structures and Algorithms also pushed me to be able to think more like a programmer when it comes to solving problems, from the various coding tricks that I picked along this learning journey such as the idea of 'pointers', recursion (which I still struggle in), and how to get functions to work within/with other functions to solve a computing problem (one way is via the function's arguments/parameters).
Have a gif:
