Python

Data Structures in Python

Python language has features to support different data structures. In this tutorial, we will see how to develop python data structures in detail with examples.

 

1. Introduction

This is an article about data structures in Python. A data structure is the organization of data to cut down the storage space used and to bring the complexity down while performing different tasks. Data structures are used to handle and perform operations with large amounts of data in various fields, such as database management and internet indexing services.

2. Data Structures in Python

2.1 Prerequisites

Python 3.6.8 is required on windows or any operating system. Pycharm is needed for python programming.

2.2 Download

Python 3.6.8 can be downloaded from the website. Pycharm is available at this link.

2.3 Setup

2.3.1 Python Setup

To install python, the download package or executable needs to be executed.

2.4 IDE

2.4.1 Pycharm Setup

Pycharm package or installable needs to be executed to install Pycharm.

2.5 Launching IDE

2.5.1 Pycharm

Launch the Pycharm and start creating a pure python project named HelloWorld. The screen shows the project creation.

python data structures - Pycharm Create project
Pycharm Create project

The project settings are set in the next screen as shown below.

python data structures - Pycharm Project Settings
Pycharm Project Settings

Pycharm welcome screen comes up shows the progress as indicated below.

python data structures - project view
Pycharm Project View

You can create a Hello.py and execute the python file by selecting the Run menu.

python data structures - hello world
Pycharm Hello World

The output message “Hello World” is printed when the python file is Run.

Pycharm Python Execution

2.6 Data Structures

First, we will look at the definition of abstract datatypes, classifying data
structures into the following types :

  • Linear
  • Non Linear
  • Homogeneous
  • Heterogeneous
  • Dynamic

Lists, Sets, Tuples, and Stacks are linear data structures discussed in this article. Many applications, such as Facebook, Twitter, and Google, use lists and linear data structures. These data structures allow us to organize big data in a sequential and organized manner. They help in cutting downtime and effort.

The tree is the nonlinear data structure presented here. Non-linear data structures are used in cryptography and other areas. A non-linear data structure is a structure in which an element is connected to different elements. They use memory quickly and efficiently. Free contiguous memory is not required for appending new elements. The length of the data structures is not important before appending new elements. A non-linear data structure has different levels and a linear one has one level. The values of the elements are disorganized in a non-linear data structure. The data elements in a non-linear data structure cannot be iterated in one step. The implementation of these data structures is complex in nature.

2.7 Data Structures in Python

List,Set,Dictionary,Tuple,Stack,queue,Tree,Graph,LinkedList, and Hashmap examples are discussed below.

2.7.1 List

A list is a collection of ordered elements that are used to persist a list of items. Unlike array lists, these can expand and compress dynamically. You can use Lists as a base for other data structures, such as stack and queue. You can also use them to store lists of users, car parts, ingredients, to-do items, and various other such elements. Lists are the common linear data structures used by the developers. They were first introduced in the lisp programming language.

List

Example_List = []
print("Initial blank Example_List: ")
print(Example_List)


Example_List.append(1)
Example_List.append(2)
Example_List.append(7)
print("\nExample_List after Addition of Three elements: ")
print(Example_List)


for i in range(1, 4):
	Example_List.append(i)
print("\nExample_List after Addition of elements from 1-3: ")
print(Example_List)


Example_List.append((4, 5))
print("\nExample_List after Addition of a Tuple: ")
print(Example_List)


Example_List2 = ['For', 'JavaCodeGeeks']
Example_List.append(Example_List2)
print("\nExample_List after Addition of a Example_List: ")
print(Example_List)

You can compile the code by using the command below:

Compilation Command

python3 ExampleList.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_List.py 
Initial blank Example_List: 
[]

Example_List after Addition of Three elements: 
[1, 2, 7]

Example_List after Addition of elements from 1-3: 
[1, 2, 7, 1, 2, 3]

Example_List after Addition of a Tuple: 
[1, 2, 7, 1, 2, 3, (4, 5)]

Example_List after Addition of a Example_List: 
[1, 2, 7, 1, 2, 3, (4, 5), ['For', 'JavaCodeGeeks']]

2.7.2 Set

A Set is a linear data structure that has a collection of values that are unique. A set can
store unique values without any order. In the real world, sets can be used to collect all tags for blog articles and chat conversations. The data can be of Boolean, integer, float, characters, and other data types. Static sets allow only query methods, which means operations related to querying the set. Dynamic and mutable sets allow
the addition and deletion of elements in the set. Algebraic operations such as union, intersection, difference, and subset can be defined as methods on the sets.

Set

Example_Set = set()
print("Initial empty Set: ")
print(Example_Set)


Example_Set.add(1)
Example_Set.add(2)
Example_Set.add((3,4))
print("\nSet has these elements after Addition of Three elements: ")
print(Example_Set)


for i in range(1, 7):
	Example_Set.add(i)
print("\nSet has these elements after Addition of elements from 1-6: ")
print(Example_Set)

You can compile the code by using the command below:

Compilation Command

python3 Example_Set.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_Set.py
Initial empty Set: 
set()

Set has these elements after Addition of Three elements: 
{1, 2, (3, 4)}

Set has these elements after Addition of elements from 1-6: 
{1, 2, 3, 4, (3, 4), 5, 6}
apples-MacBook-Air:python_data_structures bhagvan.kommadi$

2.7.3 Dictionary

A dictionary is a collection of unique key and value pairs. You can use this data structure for storing a set of data items. It has a key, and each key has one item associated with it. When given a key, the dictionary will restore the item related to that key. These keys can be of any data type: strings, integers, or objects. Where we need to sort a list, an element value can be found using its key. Add, remove, modify, and lookup operations are possible on this collection. A dictionary is similar to other data structures, such as hash function and hashmap. The key/value store is used in distributed caching and in-memory databases. Dictionary data structures are used in the following streams like Phone directories, Router tables in networking, Pagetables in operating systems, Symbol tables in compilers, and Genome maps in biology.

Dictionary

Example_Dict = {}
print("Empty Example_Dictionary: ")
print(Example_Dict)

Example_Dict[0] = 'JavaCodeGeeks'
Example_Dict[2] = 'Like'
Example_Dict[3] = 2
print("\nExample_Dictionary will be like below after adding 3 elements: ")
print(Example_Dict)

Example_Dict['Value_set'] = 4, 5, 7
print("\nExample_Dictionary will be like below after adding 3 elements: ")
print(Example_Dict)

Example_Dict[2] = 'Hello'
print("\nUpdated key value for second element: ")
print(Example_Dict)

Example_Dict[5] = {'Nested_Dict' :{'1' : 'Jack', '2' : 'King'}}
print("\nAdding a Nested Key dictionary will be: ")
print(Example_Dict)

You can compile the code by using the command below:

Compilation Command

python3 Example_Dict.py 

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_Dict.py 
Empty Example_Dictionary: 
{}

Example_Dictionary will be like below after adding 3 elements: 
{0: 'JavaCodeGeeks', 2: 'Like', 3: 2}

Example_Dictionary will be like below after adding 3 elements: 
{0: 'JavaCodeGeeks', 2: 'Like', 3: 2, 'Value_set': (4, 5, 7)}

Updated key value for second element: 
{0: 'JavaCodeGeeks', 2: 'Hello', 3: 2, 'Value_set': (4, 5, 7)}

Adding a Nested Key dictionary will be: 
{0: 'JavaCodeGeeks', 2: 'Hello', 3: 2, 'Value_set': (4, 5, 7), 5: {'Nested_Dict': {'1': 'Jack', '2': 'King'}}}

2.7.4 Tuple

Tuples are finite ordered sequences of elements that are objects. They have a combination of other data
types and are used to group related data into a data structure. In an RDBMS, a tuple is a row of a table. Tuples have a fixed size compared to lists and perform better. A finite set of tuples in the relational database is called as a relation instance. A tuple can be assigned in a single statement. You can use tuples for swapping values. Lists usually have values of the same data type, while tuples can have different data.

Tuple

Example_Tuple1 = (3, 'Hello', 4, 'Java Code Geeks')
print("\nTuple with combination of different Datatypes: ")
print(Example_Tuple1)

Example_Tuple1 = (2, 1, 4, 7)
Example_Tuple2 = ('java', 'java code geek')
Example_Tuple3 = (Example_Tuple1, Example_Tuple2)
print("\nTuple which is nested tuples: ")
print(Example_Tuple3)

Example_Tuple1 = ('Java Code Geeks',) * 4
print("\nTuple after 4 repetitions: ")
print(Example_Tuple1)

Example_Tuple1 = ('Java Code Geeks')
n = 7
print("\nTuple consisting of elements in a loop")
for i in range(int(n)):
	Example_Tuple1 = (Example_Tuple1,)
	print(Example_Tuple1)

You can compile the code by using the command below:

Compilation Command

python3 Example_Tuples.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_Tuples.py 

Tuple with combination of different Datatypes: 
(3, 'Hello', 4, 'Java Code Geeks')

Tuple which is nested tuples: 
((2, 1, 4, 7), ('java', 'java code geek'))

Tuple after 4 repetitions: 
('Java Code Geeks', 'Java Code Geeks', 'Java Code Geeks', 'Java Code Geeks')

Tuple consisting of elements in a loop
('Java Code Geeks',)
(('Java Code Geeks',),)
((('Java Code Geeks',),),)
(((('Java Code Geeks',),),),)
((((('Java Code Geeks',),),),),)
(((((('Java Code Geeks',),),),),),)
((((((('Java Code Geeks',),),),),),),)

2.7.5 Stack

A stack is a last-in, first-out, data structure. You can add items from the top. Stacks are used in parsers and maze puzzles. Push, pop, top, and get size are the methods allowed on stack data structures. You can use stacks in the use cases such as Syntax parsing, backtracking, compiling, and memory management.

Stack

class ExampleStack:
   def __init__(self):
      self.stack = []

   def addElement(self, dataval):
      if dataval not in self.stack:
         self.stack.append(dataval)
         return True
      else:
         return False
        
   def removeElement(self):
      if len(self.stack) <= 0:
         return ("No element is there in the Stack")
      else:
         return self.stack.pop()

Stack = ExampleStack()
Stack.addElement("Jan")
Stack.addElement("Feb")
Stack.addElement("Mar")
Stack.addElement("Apr")
Stack.addElement("May")
print(Stack.removeElement())
print(Stack.removeElement())

You can compile the code by using the command below:

Compilation Command

python3 Example_Stack.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_Stack.py 
May
Apr

2.7.6 Queue

A queue has elements to be processed in a specific order or based on priority. Methods such as enqueue, dequeue, and peek can be executed on Queue. A Queue is a linear data structure and a sequential collection. Elements are appended to the end and are removed from the start of the queue. You can use Queues for storing tasks that need to be done, or incoming HTTP requests to be processed by the webserver. You can use queues for handling interruptions in real-time systems, call handling, and CPU task scheduling.

Queue

class ExampleQueue:
   def __init__(self):
      self.queue = list()

   def addtoqueue(self,dataval):
      if dataval not in self.queue:
       self.queue.insert(0,dataval)
       return True
      return False

   def removefromqueue(self):
      if len(self.queue)>0:
         return self.queue.pop()
      return ("No elements are there in Queue!")

Queue = ExampleQueue()
Queue.addtoqueue("Jack")
Queue.addtoqueue("George")
Queue.addtoqueue("John")
Queue.addtoqueue("Kate")
print(Queue.removefromqueue())
print(Queue.removefromqueue())

You can compile the code by using the command below:

Compilation Command

python3 Example_Queue.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_Queue.py
Jack
George

2.7.7 Tree

A tree is a nonlinear data structure. You can use Trees for search and other scenarios. A binary search tree has nodes that have a maximum of two descendants. A binary search tree consists of nodes where the property values of the left node are less than the property values of the right node.

Tree

class ExampleNode:
   def __init__(self, data):
      self.left = None
      self.right = None
      self.data = data

   def insertNode(self, data):
      if self.data:
         if data  self.data:
               if self.right is None:
                  self.right = ExampleNode(data)
               else:
                  self.right.insertNode(data)
         else:
              self.data = data
   def findbyvalue(self, lkpval):
      if lkpval  self.data:
            if self.right is None:
               return str(lkpval)+"element Not Found"
            return self.right.findbyvalue(lkpval)
      else:
            print(str(self.data) + ' is found here')

   def PrintExampleTree(self):
      if self.left:
         self.left.PrintExampleTree()
      print( self.data),
      if self.right:
         self.right.PrintExampleTree()
rootNode = ExampleNode(2)
rootNode.insertNode(7)
rootNode.insertNode(15)
rootNode.insertNode(4)
print(rootNode.findbyvalue(5))
print(rootNode.findbyvalue(15))

You can compile the code by using the command below:

Compilation Command

python3 Example_Tree.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_Tree.py
5element Not Found
15 is found here
None
apples-MacBook-Air:python_data_structures bhagvan.kommadi$

2.7.8 Graph

A graph is a group of objects that are connected by links. The links connect vertices/points. The basic methods on a graph are the appending and deletion of links and vertices. These are some different types of graphs such as Directed graph,Non-directed graph, Connected graph, Non-connected graph, Simple graph, and Multi-graph.

Graph

class ExampleGraph:
   def __init__(self,graphdict=None):
      if graphdict is None:
         graphdict = {}
      self.graphdict = graphdict
   def getPoints(self):
      return list(self.graphdict.keys())
      
   def addPoint(self, point):
      if point not in self.graphdict:
         self.graphdict[point] = []

egraph_elements = { 
   "a" : ["b","c"],
   "b" : ["a", "d"],
   "c" : ["a", "d"],
   "d" : ["e"],
   "e" : ["d"],
   "f" : ["e"]
}
graph = ExampleGraph(egraph_elements)
graph.addPoint("g")
print(graph.getPoints())

You can compile the code by using the command below:

Compilation Command

python3 Example_Graph.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_Graph.py
['a', 'b', 'c', 'd', 'e', 'f', 'g']

2.7.9 LinkedList

LinkedList is a sequence of node elements that have properties and a reference to the next node element in the order. It is a linear data structure that is used to persist data in the memory . The data structure permits the appending and removal of components from any node next to another node. They are not persisted contiguously in memory, which makes them different arrays.

Linked List

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

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

   def printList(self):
      printval = self.headval
      while printval is not None:
         print (printval.dataval)
         printval = printval.nextval
   def AddAtStart(self,newdata):
      NewNode = ExampleNode(newdata)
      NewNode.nextval = self.headval
      self.headval = NewNode

list = ExampleLinkedList()
list.headval = ExampleNode("Jan")
enode2 = ExampleNode("Feb")
enode3 = ExampleNode("Mar")

list.headval.nextval = enode2
enode2.nextval = enode3

list.AddAtStart("Dec")
list.printList()

You can compile the code by using the command below:

Compilation Command

python3 Example_LinkedList.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_LinkedList.py
Dec
Jan
Feb
Mar

2.7.10 Hashmap

Hash maps are indexed data structures. A hash map uses a hash function to calculate an index with a key into an array of buckets or slots. Its value is mapped to the bucket with the respective index. The key is unique and immutable. A hash map is like a cabinet having drawers with labels for the things stored in them. For example, storing user information- you can use email as the key, and you can map values corresponding to that user such as the first name, last name, etc to a bucket.  

A hash function is the core of implementing a hash map. It takes in the key and decodes it to the index of a bucket in the bucket list. Ideal hashing should produce a different index for each key. Sometimes, collisions can occur. When hashing gives an existing index, you can use a bucket for multiple values by appending a list or by rehashing.

Hashmap

class ExampleHashMap:


	def __init__(self, size):
		self.size = size
		self.hash_table = self.create_buckets()

	def create_buckets(self):
		return [[] for _ in range(self.size)]


	def set_value(self, key, val):
		

		hashed_key = hash(key) % self.size
		

		bucket = self.hash_table[hashed_key]

		found_key = False
		for index, record in enumerate(bucket):
			record_key, record_val = record
			
			if record_key == key:
				found_key = True
				break

		if found_key:
			bucket[index] = (key, val)
		else:
			bucket.append((key, val))


	def get_value(self, key):
		

		hashed_key = hash(key) % self.size
		
		bucket = self.hash_table[hashed_key]

		found_key = False
		for index, record in enumerate(bucket):
			record_key, record_val = record
			
			if record_key == key:
				found_key = True
				break


		if found_key:
			return record_val
		else:
			return "No record is found"


	def delete_value(self, key):
		

		hashed_key = hash(key) % self.size
		

		bucket = self.hash_table[hashed_key]

		found_key = False
		for index, record in enumerate(bucket):
			record_key, record_val = record
			
			if record_key == key:
				found_key = True
				break
		if found_key:
			bucket.pop(index)
		return


	def __str__(self):
		return "".join(str(item) for item in self.hash_table)


hash_map = ExampleHashMap(30)

hash_map.set_value('george@gmail.com', 'x1')
print(hash_map)
print()

hash_map.set_value('jack@gmail.com', 'y1')
print(hash_map)
print()

print(hash_map.get_value('jack@gmail.com'))
print()

hash_map.delete_value('jack@gmail.com')
print(hash_map)

You can compile the code by using the command below:

Compilation Command

python3 Example_Hashmap.py

The output of the code executed is attached below:

Execution Output

apples-MacBook-Air:python_data_structures bhagvan.kommadi$ python3 Example_Hashmap.py
[][][][][][][][][][][][][][][][][][][][][][][][][][('george@gmail.com', 'x1')][][][][]

[][][][('jack@gmail.com', 'y1')][][][][][][][][][][][][][][][][][][][][][][('george@gmail.com', 'x1')][][][][]

y1

[][][][][][][][][][][][][][][][][][][][][][][][][][('george@gmail.com', 'x1')][][][][]
apples-MacBook-Air:python_data_structures bhagvan.kommadi$ 

3. Download the Source Code

Download
You can download the full source code of this example here: Data Structures in Python

Bhagvan Kommadi

Bhagvan Kommadi is the Founder of Architect Corner & has around 20 years’ experience in the industry, ranging from large scale enterprise development to helping incubate software product start-ups. He has done Masters in Industrial Systems Engineering at Georgia Institute of Technology (1997) and Bachelors in Aerospace Engineering from Indian Institute of Technology, Madras (1993). He is member of IFX forum,Oracle JCP and participant in Java Community Process. He founded Quantica Computacao, the first quantum computing startup in India. Markets and Markets have positioned Quantica Computacao in ‘Emerging Companies’ section of Quantum Computing quadrants. Bhagvan has engineered and developed simulators and tools in the area of quantum technology using IBM Q, Microsoft Q# and Google QScript. He has reviewed the Manning book titled : "Machine Learning with TensorFlow”. He is also the author of Packt Publishing book - "Hands-On Data Structures and Algorithms with Go".He is member of IFX forum,Oracle JCP and participant in Java Community Process. He is member of the MIT Technology Review Global Panel.
Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments
Back to top button