Introduction to Data Structures and Algorithms With Python.

#python #luxacademy #codewithme

Data Structures

Python has four inbuilt basic data structures which are:
Lists, Dictionary, Tuple and Sets.
To start with:
Lists
Lists can be used for any type of object. From numbers to string and also lists.
Lists are defined by brackets - []

numbers = [4,5,6]
print(type(numbers))

output:

<class 'list'>

Lists can also be defined by using the keyword list()

numbers = list()
numbers.append(4)
numbers.append(5)
numbers.append(6)
print(numbers)
[4, 5, 6]

There are set of built-in methods used with lists.

append() - Adds an element at the end of the list
clear() - Removes the elements of a list
copy() - Returns a copy of the list
pop() - Removes the element at the specified position
insert() - Adds an element at the specified position
reverse() - Reverses the order of the list
sort() - Sorts the list
remove - removes the first item with the specified value
count - returns the number of elements with the specified value.

Dictionary
Dictionaries referred to as hashmaps in other languages. It consists of key, value pairs. Key are unique and immutable objects.
Each key and value pair are seperated by a colon.
Dictionaries are defined by curly brackets {}.

Dict = {'name': 'Eric', 'age': 19}

There are also a set of inbuilt python dictionary methods

clear() - Removes all items from a dictionary
copy() - Returns a copy of the dictionary
get() - gets the value of the specified parameter
items() - gets all items of a dictionary in the key value format
popitem() - Removes and returns the last element in the dictionary
update() - updates the dictionary with the key-value pairs
keys() - returns a list containing the dictionary's keys
values() - returns a list of all the values in the dictionary

Tuple
A tuples is ordered and immutable.
Duplicates are allowed in tuples.
Tuples are defined with brackets () and are indexed.

mytuple = ("cat", "mouse", "cow", "chicken")

Tuples can be accessed through indexing

mytuple = ("cat", "mouse", "cow", "chicken")
print(mytuple[1])

# output:

mouse

Sets
Sets are unordered, immutable and unindexed.
Duplicates are not allowed in sets
Sets are defined with curly brackets {}

myset = {"cat", "mouse", "cow", "chicken"}

There are built-in set methods.

add() - Adds an element to the set
clear() - removes all the elements from the set
copy() - returns a copy of the set
discard() - removes the specified item
pop() - removes an element from the set
update() - updates the set with another set
remove() - removes the specified item

Algorithms

Queues
A queue is an abstract data structure that is open on both sides hence use first in first out basis FIFO.
A queue has two ends; front and rear.

The two operations involved with queues are enqueue and dequeue.
Enqueue involves inserting items in a queue while dequeue is the process of removing items.

Methods involved in queues include:
push(item) - used to insert an element to the queue.
pop(item) - used to remove an element from the queue.
get() - used to extract an element from the queue.
empty() - check whether a queue is empty or not.
full() - check whether a queue is full.

Implementation of queues using list in python

q = []
def Enqueue():
    if len(q) == size:
        print('Queue is full')
    else:
        number = input('Enter numbers-:')
        q.append(number)
        print(number,'number added to the queue')

def dequeue():
    if len(queue) == 0:
        print('queue is empty')
    else:
        del = q.pop(0)
        print('Element removed',del)

def display():
    size = input('Enter size of the queue')
    while True:
        print("Select the Operation:1.Add 2.Delete 3. Display 4. Quit")
        choice=int(input())
        if choice==1:
            Enqueue()
        elif choice==2:
            dequeue()
        elif choice==3:
            display()
        elif choice==4:
            break
        else:
            print("Invalid Choice =(")

Stacks

A stack is a linear data structure that stores items in a last-in-First-Out order.

A stack is open on one side hence a new item is added at one end and removed from that end only.

The methods involved with stacks are:
empty() - returns whether stack is empty.
size() - returns size of the stack.
top() - returns a reference to the topmost element of the stack.
push() - inserts items at the top of the stack.
pop() - Deletes the topmost element of the stack.

Implementation using list

stack = []

#append() used to push items into stack
stack.append('a')
stack.append('b')
stack.append('c')

print(stack)

#pop() removes items from stack

print(stack.pop())
print(stack.pop())
print(stack.pop())

#elements after being popped
print(stack)

Linked Lists
A linked list is a sequence of data elements which are connected via links.
Each link contains connection to another link.
Python does not have linked lists in its standard library.

The first node is also known as the HEAD. It is used as a reference to traverse the list.
The last node points to NULL.

Types of Linked Lists

Singly linked list - traversed in forward direction
Doubly linked list - traversed in forward and back directions
Circular singly linked list - the last element contains link to the first element as next
Circular Doubly linked list - the last element contains link to the first element as next and the first element contains link of the last element as previous.


Implementation of nodes using classes

class Node:
  #constructor to create a new node
  def __init__(self, data):
    self.data = data
    self.next = None


class LinkedList:
  #constructor to create an empty LinkedList
  def __init__(self):
    self.head = None

# create an empty LinkedList                 
MyList = LinkedList()

#Add first node.
first = Node(1)
#linking with head node
MyList.head = first

#Add second node.
second = Node(2)
#linking with first node
first.next = second

#Add third node.
third = Node(3)
#linking with second node
second.next = third

Thank you for reading this article. I hope it was of great assistance understanding data structures and algorithms with python.