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!