Introduction to Data Structures and Algorithms
Tags: beginners, python, programming
Published: 2022-02-21 08:15:36

This article is written to this end, that you have a generic view of what data structures and algorithms is in python. Data structures can be classified in two categories;

- Built-in data structures

- User-built data structures

**Built-in data structures**
This are structures built-in the function that allows us to store, manage and organize data. In this article we'll focus on four; list, tuple, set, and dictionary.

_LIST_
Lists are used to store multiple items in a single variable. The list can contain strings or integers. The contents of a list are written inside square brackets, []. The list is mutable and ordered.

```
my_list = [1,2,3,4,5]
```
After assigning values to a list variable, we can access values by their indexes. Example in the list above, 

```
my_list[0] 
#this will access the first item in the list.
```

_TUPLE_
Tuples are very similar to lists but they are unmuttable. You cannot add or remove elements from a tuple. Tuples are ordered and are written inside ()

```
my_tupple = (1,2,3,4,5,6)
```
Tuple items can also be accessed by index.

```
my_tuple[3]
# This will access the fourth item which is 4
```
_SET_
A set contains unique items. Set items cannot be accessed by index since they are unordered.
Let's create a list and pass it into a set for unique values

```
my_list = [1,2,3,1,1,1,6,5,5,7,6,3,4]

my_set = set(my_list)

print(my_list)

#The output will be:
#(1,2,3,4,5,6,7)

```
_DICTIONARY_
Dictionaries are unordered collection of items. it allows storing a pair items, keys and values.

To access an item value in a dictionary, you use its key.

```
'''
this example shows the rating in number of stars of famous games.
to use the rating of NFS for example, we call the index at NFS.
'''
my_dict = {'GTA':4, 'NFS':5, 'PUBG':4}


```
**User-built data structures**
Here we'll focus on queues, stacks and linked lists.

_QUEUES_
Queue is a linear data structure that stores items in First In First Out (FIFO) manner. 
With a queue the least recently added item is removed first. A good example of queue 
is any queue of consumers for a resource where the consumer that came first is served first.
 
Characteristics of queues

Two ends:
front → points to starting element
rear → points to the last element

There are two operations:
enqueue → inserting an element into the queue. It will be done at the rear.
dequeue → deleting an element from the queue. It will be done at the front.

There are two conditions:
overflow → insertion into a queue that is full
underflow → deletion from the empty queue

```
class my_queue:
    
    def __init__(self):
        self.data = []
        
    def length(self):
        return len(self.data)
    
    def enque(self, element): # put the element in the queue
        if len(self.data) < 5:
            return self.data.append(element)
        else:
            return "overflow"
        
    def deque(self): # remove the first element that we have put in queue
        if len(self.data) == 0:
             return "underflow"
        else:
            self.data.pop(0)
            
b = myqueue()
b.enque(2) # put the element into the queue
b.enque(3)
b.enque(4)
b.enque(5)
print(b.data)
b.deque()# # remove the first element that we have put in the queue
print(b.data)

#OUTOUT
'''
[2, 3, 4, 5]
[3, 4, 5]
'''
```

**STACK**
A stack is a linear data structure that stores items in a Last-In/First-Out (LIFO) or First-In/Last-Out (FILO) manner. 
In stack, a new element is added at one end and an element is removed from that end only. 
The insert and delete operations are often called push and pop.

The operations of stack are:

Push → inserting an element into the stack
Pop → deleting an element from the stack

The conditions to check:

overflow condition → this condition occurs when we try to put one more element into a stack that is already having maximum elements.

underflow condition →this condition occurs when we try to delete an element from an empty stack.
```
class my_stack:
    
    def __init__(self):
        self.data =[]
        
    def length(self): #length of the list
        return len(self.data)
    
    def is_full(self): #check if the list is full or not
        if len(self.data) == 5:
            return True
        else:
            return False
        
    def push(self, element):# insert a new element
        if len(self.data) < 5:
            self.data.append(element)
        else:
            return "overflow"
        
    def pop(self): # # remove the last element from a list
        if len(self.data) == 0:
            return "underflow"
        else:
            return self.data.pop()

a = mystack() # I create my object
a.push(10) # insert the  element
a.push(23)
a.push(25)
a.push(27)
a.push(11)
print(a.length())
print(a.is_full())
print(a.data)
print(a.push(31)) # we try to insert one more element in the list - the output will be overflow
print(a.pop())
print(a.pop())
print(a.pop())
print(a.pop())
print(a.pop())
print(a.pop()) # try to delete an element in a list without elements - the output will be underflow

#OUTPUT
#5
#True
#[10, 23, 25, 27, 11]
#overflow
#11
#27
#25
#23
#10
#underflow
 
```
**LINKED LIST**
A linked list is a sequence of data elements, which are connected together via links. 
Each data element contains a connection to another data element in form of a pointer. 
Python does not have linked lists in its standard library. We use the concept of nodes to implement linked lists

```
class Node:
   def __init__(self, dataval=None):
      self.dataval = dataval
      self.nextval = None

class SLinkedList:
   def __init__(self):
      self.headval = None

list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2

# Link second Node to third node
e2.nextval = e3
```