Introduction to data structures and algorithms in Python
Tags: python, algorithms, beginners, programming
Published: 2022-02-20 21:39:10

In this article we will explore the most fundamental concept in Python and programming. 

A good grasp of data structures and algorithms and the ways to implement them will assist you solve challenges using code and create robust solutions to real world problems. 

Data structures and algorithms can be a bit of a headache but by the end of this article you'll have the pain relief for that headache.

##Data Structures
A data structure is a special format in which data you can organize, process, retrieve and store data.
There are various types each used for particular purposes. 
Data structures are important in assisting users organize data for easier use.

![chart showing data structures](https://res.cloudinary.com/practicaldev/image/fetch/s--XzxY2Bkw--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_880/https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c67h1v1f1r5jsazd8xrg.png)

**Built-in**
I have covered this type in detail in the previous article [PYTHON 101: ULTIMATE GUIDE TO PYTHON](https://dev.to/andisiambuku/python-101-ultimate-guide-to-python-542g)

- List 
A list is a collection of data which is ordered and modifiable. It can have duplicate values.

- Tuple 
A tuple is a collection of data which is ordered and unmodifiable. It can have duplicate values.

- Set 
A set is a collection of data which is unordered, unmodifiable and un-indexed. It cannot have duplicate values.

- Dictionary 
A dictionary is a collection of data which is unordered and modifiable and indexed. It cannot have duplicate values.

**User-defined**
User defined data structures allow users to control the functionality of the data structures and create them too.

- Stack - 
A stack is a linear data structure that stores data in a FILO(First In Last Out) format. A new element is added at one end and removed at only that end.
Deleting an item is called *pop* while adding an item is called *push*.
Illustration
![stack](https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2013/03/stack.png)
 
 
Implementation using a list

```
stack = []
stack.append("Andisi")
stack.append("Ambuku")
stack.append(2022)
print(f"Initial stack : {stack}")
Initial stack : ['Andisi', 'Ambuku', 2022]
stack.pop()
2022
stack.pop()
'Ambuku'
stack.pop()
'Andisi'
print(f"Stack after elements are removed : {stack}")
Stack after elements are removed : [] 
```

- Queue - 
A queue is a linear data structure that stores items in FIFO(First In First Out) format. The last item to be added is the first to be removed.

Illustration
![queue](https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2014/02/Queue.png)
```
queue = []
queue.append("Andisi")
queue.append("Ambuku")
queue.append(2022)
print(f"Initial Queue is {queue}")
Initial Queue is ['Andisi', 'Ambuku', 2022]
queue.pop(0)
'Andisi'
queue.pop(0)
'Ambuku'
queue.pop(0)
2022
print(f"Queue after removing element: {queue}")
Queue after removing element: []


```

- Linked list - 
A linked list is a linear data structure where elements are not stored at adjoining memory locations. The elements are linked using pointers.
Illustration
![linked list](https://media.geeksforgeeks.org/wp-content/cdn-uploads/gq/2013/03/Linkedlist.png)

- Tree - 
A tree is a hierarchical data structure that looks like this
   
Illustration 
![tree](https://www.bing.com/th?id=OIP.5TR6ld9jT87LkRA8kHmiWgHaGL&w=130&h=108&c=8&rs=1&qlt=90&o=6&pid=3.1&rm=2)

the top part is called the *root* and the successive parts below it are called *nodes*. The noes without successors or *children* are called *leaf nodes*

- Graph - 
A graph is a nonlinear data structure that has *edges* and nodes (vertices). The edges connect two nodes.

Illustration
![graph](https://www.geeksforgeeks.org/wp-content/uploads/undirectedgraph.png)

- Hash map - 
A hash map is an indexed data structure. It uses a *hash function*() to get the index with a corresponding key into an array of slots. The key is unique and cannot be changed.

Illustration
![hash map](https://upload.wikimedia.org/wikipedia/commons/thumb/d/d0/Hash_table_5_0_1_1_1_1_1_LL.svg/450px-Hash_table_5_0_1_1_1_1_1_LL.svg.png)

- Heap - 
A heap is a data structure that is used to show a priority queue. This data structure gives the smallest element when an element(at random) is *popped*. When items are *popped* or *pushed* the structure of the heap is maintained.

Illustration
![heap](https://www.geeksforgeeks.org/wp-content/uploads/MinHeapAndMaxHeap.png)

##Algorithms
An algorithm is a set of rules that are followed to solve a problem. Input is given then the algorithm is executed and an output which is the solution results from the process.

**Sorting algorithms**
A sorting algorithm is a set of instructions accepts lists or arrays as input and arrange the items in a specific order.
Sorting algorithms are useful in organizing data in a particular order. They make disorganized data more organized and easier to use.

Examples of sorting algorithms include:

- Bubble sort 
- Insertion sort
- Merge sort
- Shell sort
- Selection sort

**Searching algorithms**
Searching algorithms are sets of instructions used to search for an item in the data structure where it is contained. They are categorized into:

- Sequential search - 
This type of search algorithms are used on lists or arrays where they traverse every element sequentially and each element is checked until the solution is found then the process stops.
An example is Linear Search

Illustration from [Geeks for Geeks](https://www.geeksforgeeks.org/searching-algorithms/)
![linear search](https://media.geeksforgeeks.org/wp-content/cdn-uploads/Linear-Search.png)

- Interval Search - 
This type of search algorithms are used on sorted data structures for example, a sorted array. They divide the search space in two and keep doing so until the solution is found then the process stops.
An example is Binary Search.

Illustration from[Geeks for Geeks](https://www.geeksforgeeks.org/searching-algorithms/)
![binary search](https://www.geeksforgeeks.org/wp-content/uploads/Binary-Search.png)

**Graph algorithms**
A graph algorithm is a set of instructions that travel through (traverse) the nodes of a graph. It is used to find a particular path between nodes or a particular node.

Graph algorithms have many uses one real world use is in taxi cab applications. The algorithm is implemented on the map feature to find the cheapest or the shortest path for a vehicle using a specified route.

- Depth-first traversal - 
A depth-first search traverses the graph by checking the current node and then continuing to to one of its successors and repeating the same process. 
In case the current has no successor the algorithm goes back to its predecessor and then checks for successors and if the solution is found the search stops.


Illustration from [Freecodecamp](https://www.freecodecamp.org/news/graph-algorithms-explained/)
![depth-first-algorithm](https://upload.wikimedia.org/wikipedia/commons/7/7f/Depth-First-Search.gif)

- Breadth-first traversal - 
The breadth-first search traverses the graph by checking the current node first and then enlarges it by including its successors to the consecutive level. 
This goes on all nodes it the current level then it continues to the next level until the solution is found the the search ends.
Illustration from [Simplilearn](https://www.simplilearn.com/tutorials/data-structure-tutorial/bfs-algorithm#:~:text=Breadth-First%20Search%20Algorithm%20or%20BFS%20is%20the%20most,must%20move%20on%20to%20the%20next-level%20neighbor%20nodes.)
![breadth-first-algorithm](https://www.simplilearn.com/ice9/free_resources_article_thumb/BFS-Algorithm-Soni/bredth-first-search-in-graph-data-structure.png)

###Properties of algorithms
- Finite
An algorithm must end after a defined number of steps for any input entered.

- Output specified
An algorithm has to give an output as a result of the input it was given by a user. The output is the solution of the process.

- Effective
An algorithm's steps should be done accurately and within a finite amount of time.

- Input specified
An algorithm has to be given input values to perform the process needed to generate a solution to a problem. 

- Definite
An algorithm must have specified steps that it follows in generating the solution to a given problem. 


Until next time, may the code be with you!