Introduction to Data Structures and Algorithms with Python

This is a continuation from the Introduction to Modern Python here which covers

Python Installation and Development environment set up
Indentation, Variables and Comments in Python.

This blog is going to cover basic data structures:

Lists
Sets
Tuples
Dictionaries
Queues
Stack
Linked list

Data structures are a method of organizing and storing data for operations to be easily accessible and run efficiently while algorithms are the order of well defined instructions used in problem solving.

Built-in data structures

These are specified in the language. There are four types of built-in data structures in Python: lists, sets, tuples and dictionaries.

Lists

These are ordered collection of items, created using [ ], separated by commas. A nested list is a list inside a list. The index operator [ ] is used to access an item in a list. In Python, indices start at 0. So a list having 6 elements will have an index from 0 to 5.

Negative indexing is the act of indexing from the end of the list with the index starting at -1. The index of -1 refers to the last item, -2 to the second last item and so on.
List slicing is accessing a range of items in a list by using the slicing operator :

# empty list
emp_list= []

# list with mixed data types
mixed_list = [647, "Abbott Elementary", 98.1]

# nested list
nest_list = [98.1, [2, 4, 3], ['r']]

#list index
index_list = ['l', 'e', 'g', 'i', 'o', 'n']

# first item of list index
print(index_list[0]) #l

# last item of list index
print(index_list[-1]) #n

# fifth last item of list index
print(index_list[-5]) #e

# list slicing elements from index 2 to index 4
print(index_list[2:5]) #['g', 'i', 'o']

List methods

append(): adds an item to the end of a list
extend(): adds several items to a list
insert(): inserts an item at a particular index
remove(): deletes an item from a list
pop(): returns and removes an item at the given index
clear(): removes all items from the list
sort(): sort items in a list in ascending order
count(): returns the count of the number of items passed as an argument
reverse(): reverses the order of items in the list

Sets

These are unordered collection of items which have no duplicates. They are defined using { }, separated by comma, or by using the built-in set() function. A set is mutable: can be modified once created.

# initialize my_set
my_set = {76, "Mango", 5.4}
print(my_set) 
# {5.4, 76, 'Mango'}

# discard an element
my_set.discard(76)
print(my_set) 
# {'Mango', 5.4}

# add an element
my_set.add(2)
print(my_set) 
# {2, 5.4, 'Mango'}

Tuples

They are very similar to lists but are immutable(cannot add or modify items).They are created by inputting items in the ( ) separated using commas.

# accessing tuple elements using indexing
my_tuple = ('h','o','m','e','c','o','m','i','n','g')

print(my_tuple[0])   # h
print(my_tuple[5])   # o
print(my_tuple[-6])  # c

# using a for loop to iterate through a tuple
for name in ('Beyonce', 'Prince'):
    print("Singer", name)
# Singer Beyonce
# Singer Prince

# delete an entire tuple
del my_tuple

Dictionaries

They are unordered data collection of items stored in (key:value) pairs. They retrieve values when the key is known. Defined using { } or using the dict() constructor.

#empty dictionary
my_dict = {}

#dictionary with integer keys
my_dict = {1: 'January', 2: 'February'}

# dictionary with mixed keys
my_dict = {'animal': 'Giraffe', 1: [9, 2, 8]}

# using dict()
my_dict = dict({1:'Dog', 2:'Cat'})

# delete the dictionary itself
del my_dict

# remove all items
my_dict.clear()

User-defined data structures

These are specified data structures by the user. There are three types of user-defined data structures in Python: stacks, queues and linked lists.

Stack

This is a linear data structure in which operations are carried out in LIFO (Last In First Out) sequence where the data entered last is the first to be accessed. There are two main methods used:

push : adds an element to the top of the stack.
pop : removes an element from the top of the stack.

Used in compilers. Implemented in Python as it enables storing and retrieving of data sequentially.

# stack implementation in python
# creating stack
def create_stack():
    stack = []
    return stack

# creating empty stack
def check_empty(stack):
    return len(stack) == 0

# adding items into stack
def push(stack, item):
    stack.append(item)
    print("pushed item: " + item)

# removing item from the stack
def pop(stack):
    if (check_empty(stack)):
        return "Empty stack"

    return stack.pop()

stack = create_stack()
push(stack, str(45))
push(stack, str(46))
push(stack, str(47))
print("popped item: " + pop(stack))
print("stack after popping an element: " + str(stack))

# pushed item: 45
# pushed item: 46
# pushed item: 47
# popped item: 47
# stack after popping an element: ['45', '46']

Queues

This is 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 an array structure and operations can be performed from both ends of the queue: head-tail or front-back.

There are two main methods used:

enqueue: adds an element to the end of the queue.
dequeue: removes the element from the beginning of the queue.

It is applied in CPU scheduling as tasks are handled in the order they arrive.

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

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

Linked Lists

They are a sequence of data connected together by links or pointers. Linked lists contain a chain of nodes in different parts of memory that are linked to each other. Each node contains data (where an item is stored) and next (a memory address that references to the memory location of the next node). Linked lists are applied in blockchains.

There are two main types of linked lists:

Singly Linked Lists
Doubly Linked Lists

Singly linked lists can be traversed in only one direction: left to right while doubly linked lists can be traversed either left to right or right to left. Each node contains its own data value and a memory address that references to the memory location of the next node.

class Node:
   def __init__(self, data=None):
      self.data = data
      self.next = None

# class to create a linked list
class LinkedList:
   def __init__(self):
      self.head = None

   def listprint(self):
      printval = self.head
      while printval is not None:
         print (printval.data)
         printval = printval.next

list1 = LinkedList()
list1.head = Node("Jan")
m2 = Node("Feb")
m3 = Node("Mar")
# link first Node to second node
list1.head.next = m2

# link second Node to third node
m2.next = m3
list1.listprint()

#Jan
#Feb
#Mar

There is much more information in understanding data structures specifically. This gives an overview of the matter. Hope this article helped. Happy learning!

Jane Njoroge's blog