Modern Data Structures and Algorithms With Python.
Tags: python, datastructures, algorithms, programming
Published: 2023-04-05 18:14:49

This is a piece that is a continuation of my second article [python-101-a-step-by-step-python-tutorial-guide-for-beginners](https://dev.to/sleekscreatess/python-101-a-step-by-step-python-tutorial-guide-for-beginners-4jm7) If you're not so sure or wondering, click the above link so that you can see the article and learn Python programming language the right way.
In this article, We will go all the way in talking about data structures which are very crucial in organizing the storage on your computer, allowing you the ability to access and change your data very easily. Consequently we will also discuss the many types of Data Structures used in Python, for example Lists, Tuples, Dictionaries, Sets, Stacks, Queues, Linked list and so on.

#Introduction To Data Structures and Algorithms Using Python.

### What is a Data Structure?
Is a set of procedure that allows you to define, store, access and manipulate data.
A Data structure is an organized collection of data in your computer or a logical model or mathematical model that of a particular organization of data.
Data structure is important since it defines the relationship between the elements of the data stored in memory.
A data structure is a data composed of a set of functions and a set of statements.

### An Algorithm in Python?
**An Algorithm** is a finite sequence of rules or instructions, each carrying a clear meaning that one must perform to solve a well-formulated problem. 
*Python Algorithm* is important because they have a detailed set of instructions that facilitates the processing of data for a specific purpose.

## Types of Data Structures in Python.
There are two types, namely:
- **Built-in Data Structures**
- **User-Defined Data Structures**

### Built-in Data Structures
They comprise the following; *Lists*, *Tuples*, *Dictionaries* and *Sets*.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uyg8c0sw4m9uvdzca730.png)

### User-Defined Data Structure
These data structures include Stack, Queues, Graphs, Lists, Trees and HashMap

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2xyveg52mo7ym1n6bn3g.png)


- Additionally, In Python, Data Structure can be categorized into two different groups this is **Linear** and **Non-Linear** Data Structures where in the **Linear data structure** the data items or elements are arranged or stored in a linear sequence for example *Lists*, *Stack*, *Queues* etc whereas in **Non-linear Data Structure** the data item or node is linked to multiple numbers of items or elements say 'n' for instance *Tree* and *Graphs*. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eq0vv5yhre25bpjqxlbd.png)
## Lists

A list is a simple way to give one name to a collection of values. These values or elements can have different data types i.e int, float, complex numbers, strings etc and even other lists.
Lists allow you to use several elements at once with all the information stored in that list and is created by placing elements inside *square brackets* **[]**, separated by commas.
  ```python
Python 3.10.2 (main, April 4, 09:03:01) [GCC 12.2.0] on linux
Type "help", "copyright", "credits" or "license" for
>>> mylist = [Ruby, Vue, NodeJs, Flask, Perl]
>>> my_list = [1, "Hello World", 3.14]
>>> my_nested_list = ["Jatelo", [9, 10, 11], ['x']]
>>> print(mylist)
>>> print(my_list)
>>> print(my_nested_list)
```
#### Output: 
```python
[Ruby, Vue, NodeJs, Flask, Perl]
[1, "Hello World", 3.14]
["Jatelo", [9, 10, 11], ['x']]
```
List items are ordered, changeable or mutable, and allow for the values to be duplicated.
A list indices start at 0, and lists can be sliced, concatenated and so on.
An indexed list can be accessed by referring them using an index number and it is important to note that a list having 3 elements will have an index from 0 to 2.
  ```python
months = ["January", "February", "March"]
print(months[0])  
print(months[1])  
print(months[2]) 
```
#### Output:
```python
January
February
March
```
In Python, negative indexing means start from the end
-1 refers to the last item, -2 refers to the second last item and -3 refers to the third last item etc.
```python
colors = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"]
print(colors[-1])
print(colors[-3])
print(colors[-5])
```
#### Output:
```python
violet
blue
yellow
```

To remove an item in a list, you can use either use the del statement if you know exactly which item(s) you are deleting or the remove() method which removes the specified item.
```python
days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]
del days[2]
print(days)
days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]
del days[1:3]
print(days)
days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]
del days
print(days) 

days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]
days.remove("Wednesday")
print(days)
days = ["Monday", "Tuesday", "Wednesday", "Thursday", "Friday"]
days.pop(1)
print(days)
```
#### Output:
```python
['Monday', 'Tuesday', 'Thursday', 'Friday']
['Monday', 'Thursday', 'Friday']
Traceback (most recent call last):
  File "/tmp/sessions/20b16bb7e7902bfb/lis.py", line 11, in <module>
    print(days) 
NameError: name 'days' is not defined
['Monday', 'Tuesday', 'Thursday', 'Friday']
['Monday', 'Wednesday', 'Thursday', 'Friday']
```
In a List, for you to slice a range of items  you must use the slicing operator [:].
```python  
cars = ["Ford", "Tesla", "Toyota", "Mustang", "BMW", "Volvo"]
print(cars[3:4])
print(cars[5:])
print(cars[:])
```
#### Output:
```python
["Mustang"]
["Volvo"]
["Ford", "Tesla", "Toyota", "Mustang", "BMW", "Volvo"]
```
To add a single item to a list, you will have to use the **append()** method or add multiple items using the **extend()** method.
```python
odd = [1, 3, 5]
odd.append(7)
print(odd)
odd.extend([9, 11, 13])
print(odd)
```
#### Output:
```python
[1, 3, 5, 7]
[1, 3, 5, 7, 9, 11, 13]
```
## Tuples
Similar to a List, A tuple is used to store multiple items in a single variable.
The main difference between tuples and lists is that you cannot change or modify the elements of a tuple hence tuples are **Immutable** once it is assigned whereas you can change the elements of a list making them have **mutable functionality**.
A tuple is created by placing all the elements inside parentheses (), separated by commas. Although, the use of parentheses in tuples is optional.
A tuple can have any number of items and they may be of different types such as integer, float, list and string.
```python
Python 3.10.2 (main, April 4, 09:13:00) [GCC 12.2.0] on linux
Type "help", "copyright", "credits" or "license" for
>>> tuple_1 = (0, 1, 2, 3, 4, 5)
>>> tuple_2 = ("Zawadi Zoe", 4.5, [a, b, c] )
>>> tuple_3 = ([4, 2, 3],"Marvelous Day!", ['z'])
>>> print(tuple_1)
>>> print(tuple_2)
>>> print(tuple_3)
```
#### Output:
```python
(1, 2, 3, 4, 5, 6, 7)
("Zawadi Zoe", 4.5, ["a", "b", "c"])
([4, 2, 3],"Marvelous Day!", ["z"])
```
   
An example of a tuple created without using parentheses:
```python
mytuple= True, False, True
print(mytuple)

my_tuple = "a", "b", "c"
print("a")
print("b")
print("c")
```
#### Output:
```python
(True, False, True)
a
b
c
```
Tuple items are ordered, unchangeable, and allow duplicate values.
```python
my_tuple = ("hi",)
print(type(my_tuple))

my_tuple = ("hi")
print(type(my_tuple))
```
#### Output:
```python
<class 'tuple'>
<class 'str'>
```
- In the above example, you will need to use a comma to tell Python that you are creating a tuple with a single item, otherwise, Python will not recognize it as a tuple.

To access an items in a tuple always use the index operator [], where the index starts from 0.
   
```python
mytuple = ("Batman", "Superman", "Ironman", "Fishman", "Mudraman")    
print(mytuple[4])
```
#### Output:
```python
Mudraman
```   
Negative indexing in Python tuples is similar to that one on lists.
The index of -1 refers to the last element, -2 to the second last element etc, Confirm the shared example on List which is similar to a Tuple.

Once the tuple is created, you cannot change its values as a result of its unchangeable/immutable functionality, however, you can convert the tuple into a list, change the list, and convert the list back into a tuple.
```python
mytuple = ("Manganese", "Lead", "Copper", "Iron", "Gold")
b = list(mytuple)
b[1] = "Silver"
mytuple= tuple(b)
print(mytuple)
```
#### Output:
```python
("Manganese", "Silver", "Copper", "Iron", "Gold")
```
To access a range of elements in a tuple by using the slicing operator colon [:].
```python
mytuple = ("Manganese", "Lead", "Copper", "Iron", "Gold", "Bronze")
print(mytuple[1:4])
print(mytuple[:-4])
print(mytuple[4:])
print(mytuple[:])
```
#### Output:
```python
('"Lead", "Copper", "Iron")
("Manganese", "Lead")
("Gold", "Bronze")
("Manganese", "Lead", "Copper", "Iron", "Gold", "Bronze")
```
For concatenation or combining two tuples then you can use the + operator.
```python
tuple1 = ("x", "y" , "z")
tuple2 = (1, 2, 3)
tuple3 = tuple1 + tuple2
print(tuple3)
```
#### Output:
```python
("x", "y" , "z", 1 , 2 , 3)
```
In Python, to repeat elements in a tuple for a given number of times then use the * operator.

Both + and * operations result in a new tuple.
```python
color = ("red", "orange", "yellow")
tuple4 = color * 2
print(tuple4)
```
#### Output:
```python
("red", "orange", "yellow", "red", "orange", "yellow")
```
Since you cannot change the elements in a tuple. This means that you cannot delete or remove elements from a tuple.
To delete the entire tuple use the keyword del.
```python
thistuple = ("Lemon", "Onion", "Cadamon",)
del thistuple
print(thistuple) 

thistuple = ("Mango", "Grapes", "Banana", "Avocado")
b = list(thistuple)
b.remove("Banana")
thistuple = tuple(b)
print(thistuple)
```
#### Output:
```python
Traceback (most recent call last):
  File "/tmp/sessions/09e0f94d526221f8/thistup.py", line 3, in <module>
    print(thistuple) 
NameError: name 'thistuple' is not defined
("Mango", "Grapes", "Avocado")
```
## Dictionaries
A Dictionary is a collection of items where each item of a dictionary has a key/value pair that stores data values in those key/value pairs.
Keys are unique within a dictionary while values may not be. The values of a dictionary can be of different types, but the keys must be of an immutable data type such as strings, numbers, or tuples.
A dictionary is like an associative array where each key stores a specific value and cannot be indexed by a sequence of numbers but indexed based on keys.
To create a dictionary just place items inside curly brackets {} and separate them with commas.
```python
Python 3.10.2 (main, April 4, 10:11:01) [GCC 12.2.0] on linux
Type "help", "copyright", "credits" or "license" for
>>> pop = [1.4, 332, 1.42]
>>> countries = ["India", "USA", "China"]
>>> world = {"India":1.4, "Usa":332, "China":1.42}
>>> print(world)
>>> dict = {"brand": "Audi", "model": "Q5", "year": 2023}
>>> print(dict)
>>> mydict = {"name": "Utumishi Tech", 1: ["a", "b", "c"]}
>>> print(mydict)
>>> my_dict1 = dict({1:"Gold", 2:"Silver"})
>>> print(my_dict1)
>>> my_dict2 = dict([(1,"Gold"), (2,"Silver")])
>>> print(my_dict2)
```
#### Output:
```python
{"India":1.4, "Usa":332, "China":1.42}
{"brand": "Audi", "model": "Q5", "year": 2023}
{"name": "Utumishi Tech", 1: ["a", "b", "c"]}
{1:"Gold", 2:"Silver"}
{1:"Gold", 2:"Silver"}
```
Dictionaries cannot have two items with the same key and thereby when items are duplicated on a key it overwrites the existing value.
```python
dict = {"brand": "BWM", "model": "M2 G87", "year": 2022, "year": 2023}
print(dict)
```
#### Output:
```python
{"brand": "BWM", "model": "M2 G87", "year": 2023}
```
As a result of dictionaries being **mutable** then you can be able to add a new item or change the value of existing items using an assignment operator. In any case, if the key is already present, then the existing value gets updated and if not a new (key: value) pair is added to the dictionary.
```python
mydict = {"name": "Zawadi", "age": 18}
mydict["age"] = 19
print(mydict)
mydict["address"] = "Harlem, New york"
print(mydict)

dict = {"brand": "BMW", "model": "G5", "year": 2023}
dict["color"] = "blue"
print(dict)
```
#### Output:
```python
{"name": "Zawadi", "age": 19}
{"name": "Zawadi", "age": 19, "address": "Harlem, New york"}
{"brand": "BMW", "model": "G5", "year": 2023, color: blue}
```
You can either remove individual dictionary elements or clear the entire contents of a dictionary. Also, you can delete the entire dictionary with a single operation.

A **pop()** method which removes the item with the specified key name:
```python 
dict = {"name": "Zawadi", "age": 18, "DOB": 2003, "country": "Ghana"}
dict.pop("DOB")
print(dict)
```
#### Output:
```python
{"name": "Zawadi", "age": 18, "country": "Ghana"}
```
The **clear()** method empties the dictionary:
```python
dict = {"name": "Zawadi", "age": 18, "DOB": 2003, "country": "Ghana"}
dict.clear()
print(dict)
```
#### Output:
```python
{}
```
The **pop item()** method removes an arbitrary item and returns (key, value)
```python
dict = {"name": "Zawadi", "age": 18, "DOB": 2003, "country": "Ghana"}
dict.popitem()
print(dict)
```
#### Output:
```python
{"name": "Zawadi", "age": 18, "DOB": 2003}
```
The **del** keyword removes the item with the specified key name and can also delete the entire dictionary completely:
```python
dict = {"name": "Zawadi", "age": 18, "DOB": 2003, "country": "Ghana"}
del dict["age"]
print(dict)
```
#### Output:
```python
{"name": "Zawadi", "DOB": 2003, "country": "Ghana"}
```
```python
dict = {"name": "Zawadi", "age": 18, "DOB": 2003, "country": "Ghana"}
del dict
print(dict)
``` 

## Sets
In a set, a single variable is used to store several items.
In comparison to lists and tuples, sets cannot have multiple occurrences of the same element(duplicates or repeating items) and can store unordered values.
Sets can also be used to perform mathematical set operations like union, intersection, symmetric difference, etc.
Set elements are unchangeable, but you can remove elements and add new elements.
A set is created by using the built-in set() function or placing all the elements inside curly brackets {}, separated by a comma.
Sets can have any number of items including different types like integer, float, tuple and string.
```python 
Python 3.10.2 (main, April 4, 10:31:00) [GCC 12.2.0] on linux
Type "help", "copyright", "credits" or "license" for  
>>> thisset = {"COVID-19", "typhoid", "malaria", "Pneumonia"}
>>> print(thisset)
>>> myset = {4.3, "Hi", ("x", "y", "z")}
>>> print(myset)
>>> set1 = {"Zawadi", "Mark", 4, 16, 36, True, True, True}
>>> print(set1)
```
#### Output:
```python
{"malaria", "COVID-19", "Pneumonia", "typhoid"}
{'Hi", 4.3, ("x", "y", "z")}
{16, True, 4, 36, "Mark", "Zawadi"}
```
To make a set without any elements, we use the set() function without any argument.
```python
myset = set(("Ghana", "Mali", "Cameroon"))  
print(myset)
myset1 = {"Ghana", "Mali", "Cameroon"}
print(type(myset1))
```
#### Output:
```python
{"Mali", "Cameroon", "Ghana"}
<class 'set'>
```
To remove an item in a set, use the **remove()**, or the **discard()** method. If the item to remove does not exist, **remove()** will raise an error therefore use **discard()** that will not raise an error.
```python
set1 = {"COVID-19", "typhoid", "malaria", "Pneumonia"}
set1.discard("COVID-19")
print(set1)
```
#### Output:
```python
{"Pneumonia", "typhoid", "malaria"}
```
In Python, to remove the last item in a set use the **pop()** method:
```python
disease = {"COVID-19", "typhoid", "malaria", "Pneumonia"}
a = disease.pop()
print(disease)
```
#### Output:
```python
{"COVID-19", "typhoid", "malaria", "Pneumonia"}
```
To delete the whole set then you use the **clear()** method which empties the set:
```python   
myset = {"pnemunomia", "typhoid", "malaria", "COVID-19"}
myset.clear()
print(myset)
```
#### Output:
```python
set()
```
Once a set is created, you cannot change its elements, but you can add new items by using the **add()** method.
```python
even = {2, 4, 6, 8}
even.add(10)
print(even)
even.update([12, 14, 16])
print(even)
even.update([18, 20], {22, 22, 24})
print(even)
```
#### Output:
```python
{2, 4, 6, 8, 10}
{2, 4, 6, 8, 10, 12, 14, 16}
{2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24}
```
## STACK
A **Stack** is a linear list in which insertion and deletion operations are performed at only one end or side of the list/stack.
The principle used in a stack is **Last-in First-Out** *(LIFO)*.
A stack is a linear data structure in which elements are added and removed from one end, called *the top of the stack*.
In a Stack, an item is added on top of other items for instance **5** is added on top of **4, 3, 2 and 1** which were already in the stack and when you are removing the elements you have to start with the topmost element for example *5* is removed first then followed by *4*. 

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/43twqakhs4uh372joby2.png)

In Python, stacks the insert operation is known as **push** and the delete operation is known as **pop**. 

### Basic Operations on Stack 
- *empty()*: checks and returns if the stack is empty.

- *size()*: checks and return the size of the stack

- *push(x)*: adds or inserts the element 'x' at the top of the stack.

- *pop()*: removes or deletes the topmost element found in the stack.

- *top()* reports the reference to the topmost element of the stack.   

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ruj1l9p93jkdfkdearjy.png)

## Creating a Slack using List. 
```python
stack = ["North", "South", "West", "East"]
stack.append("North West")
stack.append("North East")
stack.append(1)
print(f" Initial stack : {stack}")
```
#### Output
```python
Initial stack : ["North", "South", "West", "East", "North West", "North East", 1]
```
```python
stack = ["North", "South", "West", "East"]
stack.pop()
stack.pop()
stack.pop()
stack.pop()
print(f" stack after items are removed : {stack}")
```
#### Output
```python
stack after items are removed : []
```
### Real-Life Application of Stack
- **Arrangement of plates on a dining table in the Cafeteria**
- **Cards are arranged on top of the table while people are playing**

## QUEUES
A **Queue** is a linear data structure in which insertion takes place from one end called the **Back end or Rear** and deletion takes place from the other end called the **Front end**.
Insertion and Deletion takes place from different places.
The principle used in Queue is **First-in First-Out** *(FIFO)* where the element that is inserted first is deleted first.
In a Queue there are two variables one is the *Back/Rear* and the other is the *Front*. 
Elements must be added at the *Back/Rear end* and removed or deleted at the *Front end*.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ooosvxg2ut1l70vh76pa.png)

### Basic Operations on Queue
- *Enqueue:* Inserts or adds an element to the queue.
- *Dequeue:* Removes or deletes an element from the queue.
- *Size:* Checks whether the queue is empty.
- *Rear:* Checks on the last item from the queue.
- *Front:* Checks on the front item from the queue.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bmt2t3e1hfqdwkq9whsn.png)

### Creating  Queue using List
```python
queue = ["North", "South", "West", "East"]
queue.append("North West")
queue.append("North East")
queue.append(1)
print(f" Initial queue : {queue}")
```
#### Output
```python
Initial queue : ["North", "South", "West", "East", "North West", "North East", 1]
```
```python
queue = ["North", "South", "West", "East"]
queue.pop()
queue.pop()
queue.pop()
queue.pop()
print(f" queue after items are removed : {queue}")
```
#### Output
```python
queue after items are removed : []
```
### Real-Life Application of Queue
- *A queue or waiting list of people in a Bank waiting to be served*.
- *A queue or waiting list of people in the Airport waiting to book a flight.*
- *A queue or waiting list of cars in a parking booth.*
- *In Call Center, phone systems use Queues to hold people who are calling in order in an orderly manner.*

## LINKED LIST
The Linked List is a sequence of nodes having similar data types, each node containing one data object and a pointer to the next node.
A **Linked List** is implemented by each item having a link to the next item.
In Python Linked List, an item or an element is called a **node**.The *Head* points to the first node while the *Last* node points to the *NULL* which indicates the end of the chain.

### Types of Linked Lists
- *Singly-linked lists*
- *Doubly linked lists*
- *Circular linked lists*
- *Circular doubly linked lists*

## Creation of a Linked List
```python
# creating linked list
class LinkedListNode :
      def __init__(self,value, nextNode = None):
        self.value = value
        self.nextNode = nextNode
# creating nodes with their values
Node1 = LinkedListNode("North")
Node2 = LinkedListNode("South")
Node3 = LinkedListNode("West")
Node4 = LinkedListNode("East")
Node5 = LinkedListNode(10)
#directing the nodes to the next data
Node1.nextNode = Node2
Node2.nextNode = Node3
Node3.nextNode = Node4
Node4.nextNode = Node5
#linking the nodes
currentNode = Node1
while True:
  print(currentNode.value, "~>" , end ="")
if currentNode.nextNode is None:
    print(None)
    break
currentNode = currentNode.nextNode
```
### Applications of Linked List 
- Dynamic memory allocation.
- Implemented in stack and queue.
- Hash tables, Graphs.
- In undo functionality of the software.