Introduction to Data Structures and Algorithms With Python

Data structure

Data structure is a specialized means of organizing and storing data in computers in such a way that we can perform operations on the stored data more efficiently

Algorithm

is a step-by-step procedure for solving a problem in a finite amount of time with finite amount of effort(resources).
What is an efficient algorithm :One whose function's values are small, or grow slowly compared to a growth in the size of the input.

Types of Data structure

Python has implicit support for Data Structures which enable you to store and access data. These structures are called list , Dictionary , sets and tuples
Python also allows its users to create their own Data Structures enabling them to have full control over their functionality . The most prominent Data Structures are
Stack,Queue, Tree, Linked List , graph **and **hash tables .

1. List

To represent a sequence of items indexed by their integer position, one data structure you can use is a list. Lists contain zero or more elements and can contain elements of different types. List is a mutable ordered sequence of element mutable meaning that you can add, delete, or change elements in a flexible manner
Access list items:
List elements are accessed by the assigned index.Starting index of the list is 0 and the ending index is n-1 where n is the number of elements.
students[0] _gets the first element in a list
_students[0] = ‘Amina' changes a list item by offset.
students[0:2] _slices to extract items by offset. This example returns the first 2 elements of students.
Add list items:
_append() _adds an item to the end of a list.
_extend() or += merges one list into another.
insert() adds an item before any offset.
Remove list items:
remove() removes an item value from a list.
pop() removes the last (or specified) element while also returning the value.
del removes an item by its position in the list. del is a Python statement, not a list method.
join() returns a string of combined list items. The argument for join() is a string or any iterable sequence of strings.
_len() _returns the number of items/length in the list.
_count() _returns the number of occurrences of a specified value.

#defining  a list 
students = ['sam', 'pam', 'rocky', 'austin', 'steve', 'banner']
#acessing element in a list 
print(students[0])
print(students[-3])
print(students[1:3])

#adding element in a list 
students.append("amina")
print(students)

#deleting element in a list
students.pop(0)
print(students)

#printing the len of the list 
print(len(students))

#join string in a list
name = "-".join(["Jack", "O", "Lantern"])
print(name)

output:
sam
austin
['pam', 'rocky']
['sam', 'pam', 'rocky', 'austin', 'steve', 'banner', 'amina']
['pam', 'rocky', 'austin', 'steve', 'banner', 'amina']
6
Jack-O-Lantern

2 Dictionaries

Instead of using an offset, dictionaries use keys to associate with each value. This means that order is not tracked and should not matter if you plan to use a dictionary. Dictionary keys are immutable and unique, however, dictionaries are mutable; the key-value elements can be added, deleted, or changed
Create dictionaries using {}. Typecast using dict()

Access value in dictionary
book[‘key’] gets an item by its key

*Updating value in a dictionary *
book['key'] = ‘value' _uses a key to add (or change if it already exists) a value.
_update() merges the keys and values of one dictionary into another.

*Removing value in a dictionary *
del deletes an item by the provided key. del is a Python statement, not a dictionary method.
keys() returns all the dictionary keys. values() returns all the values in the dictionary. items() returns all the dictionary key-value pairs.

# dictionaries help us store complicated data, which is not single valued like a number or a string
book = {
    'title': "How to be awesome",
    'author': "john doe",
    'isbn': "1234-23-15-12-3",
    'date_published': "23-21-2010",
    'year': 2010}
# access value in a dict
book_title = book['title']
print(book_title)
# update value in a dict
book['title'] = "2020 what went wrong"
print(book["title"])
# get all the keys in this dictionary
keys = book.keys()
print(keys)

#deleting item from dictionary 
del book['isbn']
print (book)

#adding item to dictonary 
book['page']=450
print(book)

#Checking if a Key exists
if "year" in book:
  print("Yes, the keyword exists in the dictionary")
else:
  print('No, the keyword does not exist in the dictionary')

output
How to be awesome
2020 what went wrong
dict_keys(['title', 'author', 'isbn', 'date_published', 'year'])
{'title': '2020 what went wrong', 'author': 'john doe', 'date_published': '23-21-2010', 'year': 2010}
{'title': '2020 what went wrong', 'author': 'john doe', 'date_published': '23-21-2010', 'year': 2010, 'page': 450}
Yes, the keyword exists in the dictionary

3 Tuples

Tuples are also a sequenced data structure, just like lists. However, tuples are immutable; you cannot add, delete, or change items after a tuple is created. Tuples differ from lists by having many fewer functions because they can’t be modified after being defined. Tuples contain zero or more elements and can contain elements of different, immutable types
Create tuples using () or a comma-separated list of elements with no surrounding brackets or braces. Typecast using tuple().

Accessing element in a tuples
Accessing items in a tuple is similar to a list, we can access elements in a tuple using indexes. We can specify the index value and it will return the item stored at that particular index value.

Concatenating two tuples

vector = (4, 5, 9)
#acessing element in  a tuple
print("x-coordinate:", vector[0])
print("y-coordinate:", vector[1])
print("z-coordinate:", vector[2])

location = 108.7774, 92.5556
latitude, longtitude = location
print("The coordinates are {} x {}".format(latitude, longtitude))

output:
x-coordinate: 4
y-coordinate: 5
z-coordinate: 9
The coordinates are 108.7774 x 92.5556

4.Sets

A set is like a dictionary with only the keys, not the values. This means that sets are unique and not sequential. Sets are also mutable. Sets contain zero or more elements and can contain elements of different, immutable types .Create sets using set(). Typecast using set().
Operation that can be done in a list
add() adds an item to the set if it doesn’t already exist
remove() removes specified items from the set
intersect() returns an intersection of two sets
union() returns a union of two sets

set ={1,2,5, "amina"}
print(set)
#acessing item in a set
for x in set:
  print(x)
#add item in a set
set.add("sandra")
print(set)

#deleting element in set 
set.remove("amina")
print(set)

output:
{1, 2, 5, 'amina'}
1
2
5
amina
{1, 2, 5, 'sandra', 'amina'}
{1, 2, 5, 'sandra'}

5. Stack

Stack are linear Data Structures which are based on the principle of Last-In-First-Out (LIFO) where data which is entered last will be the first to be accessed. It is built using the array structure and has operations namely, pushing (adding) elements, popping (deleting) elements and accessing elements only from one point in the stack called the TOP. This TOP is the pointer to the current position of the stack.example :5 is added in to the stack ontop of 4 and while removing you have to start with the top most element which 5 is removed first followed by 4 thus the term Last-In-First-Out .

Operation done in stack
empty()– Returns whether the stack is empty.
size() – Returns the size of the stack.
top()– Returns a reference to the topmost element of the stack.
push()– Inserts the element ‘a’ at the top of the stack.
pop() – Deletes the topmost element of the stack.

# implementing stack using List :
myStack = []
#adding item to the stack 
myStack.append(10)
myStack.append(100)
myStack.append(1000)
myStack.append(10000)
print("Initial stack is:",myStack)
#removing utem form the list
print(myStack.pop())
print(myStack.pop())
print(myStack.pop())
print("After Removing elements:",myStack)

output:
Initial stack is: [10, 100, 1000, 10000]
10000
1000
100
After Removing elements: [10]

6. Queues

A queue is also a linear data structure which is based on the principle of First-In-First-Out (FIFO) where the data entered first will be accessed first. It is built using the array structure and has operations which can be performed from both ends of the Queue, that is, head-tail or front-back. Operations such as adding and deleting elements are called En-Queue and Dequeue and accessing the elements can be performed.

Operation performed in queues
enqueue(): Adds an element to the back of queue Q..
dequeue(): Removes and returns the first element from queue Q. Error occurs if empty.
empty(): Returns True if no elements found in queue Q, else returns False
size(): Returns the number of elements in queue Q.

# implementing Queue using List :
queue=[]
queue.append(10)
queue.append(100)
queue.append(1000)
queue.append(10000)
print("Initial Queue is:",queue)
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print("After Removing elements:",queue)

output
Initial Queue is: [10, 100, 1000, 10000]
10
100
1000
After Removing elements: [10000]

7.Linked list

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers.

Operation performed in linked list
Traversal: To traverse all the nodes one after another.
Insertion: To add a node at the given position.
Deletion: To delete a node.
Searching: To search an element(s) by value.

# A single node of a singly linked list
class Node:
  # constructor
  def __init__(self, data = None, next=None): 
    self.data = data
    self.next = next
# A Linked List class with a single head node
class LinkedList:
  def __init__(self):  
    self.head = None 
  # insertion method for the linked list
  def insert(self, data):
    newNode = Node(data)
    if(self.head):
      current = self.head
      while(current.next):
        current = current.next
      current.next = newNode
    else:
      self.head = newNode
  # print method for the linked list
  def printLL(self):
    current = self.head
    while(current):
      print(current.data)
      current = current.next
# Singly Linked List with insertion and print methods
LL = LinkedList()
LL.insert("Lux ")
LL.insert("Tech")
LL.insert("Academy")
LL.printLL()

output:
Lux 
Tech
Academy