- Python

Python Data Structures

Data Structures are a way of organizing so that is can be accessed more efficiently depending upon the situation. Data Structures are fundamentals of any programming language around which a program is built. Python helps o learn the fundamental of these data structures in a simpler way as compared to other programming languages. In this article, we will discuss the Data Structures in the Python Programming Language and how they are related to some specific Python Data Types. We will discuss all the in-built data structures like list tuples, dictionaries, etc. as well as some advanced data structures like trees, graphs, etc.ListsPython Lists are just like the arrays, declared in other languages which is an ordered collection of data. It is very flexible as the items in a list do not need to be of the same type.The implementation of Python List is similar to Vectors in C++ or ArrayList in JAVA. The costly operation is inserting or deleting the element from the beginning of the List as all the elements are needed to be shifted. Insertion and deletion at the end of the list can also become costly in the case where the preallocated memory becomes full.We can create a list in python as shown below.Example: Creating Python ListPython3List = [1, 2,  3, “GFG”, 2.3]print(List)Output[1, 2, 3, ‘GFG’, 2.3]List elements can be accessed by the assigned index. In python starting index of the list, sequence is 0 and the ending index is (if N elements are there) N-1. Example: Python List OperationsPython3List = [“Geeks”, “For”, “Geeks”]print(“nList containing multiple values: “)print(List)List2 = [[‘Geeks’, ‘For’], [‘Geeks’]]print(“nMulti-Dimensional List: “)print(List2)print(“Accessing element from the list”)print(List[0]) print(List[2])print(“Accessing element using negative indexing”)     print(List[-1])     print(List[-3])OutputList containing multiple values:
[‘Geeks’, ‘For’, ‘Geeks’]

Multi-Dimensional List:
[[‘Geeks’, ‘For’], [‘Geeks’]]
Accessing element from the list
Accessing element using negative indexing
GeeksDictionaryPython dictionary is like hash tables in any other language with the time complexity of O(1). It is an unordered collection of data values, used to store data values like a map, which, unlike other Data Types that hold only a single value as an element, Dictionary holds the key:value pair. Key-value is provided in the dictionary to make it more optimized. Indexing of Python Dictionary is done with the help of keys. These are of any hashable type i.e. an object whose can never change like strings, numbers, tuples, etc. We can create a dictionary by using curly braces ({}) or dictionary comprehension.Example: Python Dictionary OperationsPython3Dict = {‘Name’: ‘Geeks’, 1: [1, 2, 3, 4]}print(“Creating Dictionary: “)print(Dict)print(“Accessing a element using key:”)print(Dict[‘Name’])print(“Accessing a element using get:”)print(Dict.get(1))myDict = {x: x**2 for x in [1,2,3,4,5]}print(myDict)OutputCreating Dictionary:
{‘Name’: ‘Geeks’, 1: [1, 2, 3, 4]}
Accessing a element using key:
Accessing a element using get:
[1, 2, 3, 4]
{1: 1, 2: 4, 3: 9, 4: 16, 5: 25}TuplePython Tuple is a collection of Python objects much like a list but Tuples are immutable in nature i.e. the elements in the tuple cannot be added or removed once created. Just like a List, a Tuple can also contain elements of various types.In Python, tuples are created by placing a sequence of values separated by ‘comma’ with or without the use of parentheses for grouping of the data sequence.Note: Tuples can also be created with a single element, but it is a bit tricky. Having one element in the parentheses is not sufficient, there must be a trailing ‘comma’ to make it a tuple.Example: Python Tuple OperationsPython3Tuple = (‘Geeks’, ‘For’)print(“nTuple with the use of String: “)print(Tuple)     list1 = [1, 2, 4, 5, 6]print(“nTuple using List: “)Tuple = tuple(list1)print(“First element of tuple”)print(Tuple[0])print(“nLast element of tuple”)print(Tuple[-1])   print(“nThird last element of tuple”)print(Tuple[-3])OutputTuple with the use of String:
(‘Geeks’, ‘For’)

Tuple using List:
First element of tuple

Last element of tuple

Third last element of tuple
4SetPython Set is an ordered collection of data that is mutable and does not allow any duplicate element. Sets are basically used to include membership testing and eliminating duplicate entries. The data structure used in this is Hashing, a popular technique to perform insertion, deletion, and traversal in O(1) on average. If Multiple values are present at the same index position, then the value is appended to that index position, to form a Linked List. In, CPython Sets are implemented using a dictionary with dummy variables, where key beings the members set with greater optimizations to the time complexity.Set Implementation: Sets with Numerous operations on a single HashTable: Example: Python Set OperationsPython3Set = set([1, 2, ‘Geeks’, 4, ‘For’, 6, ‘Geeks’])print(“nSet with the use of Mixed Values”)print(Set)print(“nElements of set: “)for i in Set:    print(i, end =” “)print()print(“Geeks” in Set)OutputSet with the use of Mixed Values
{1, 2, ‘Geeks’, 4, 6, ‘For’}

Elements of set:
1 2 Geeks 4 6 For
TrueFrozen SetsFrozen sets in Python are immutable objects that only support methods and operators that produce a result without affecting the frozen set or sets to which they are applied. While elements of a set can be modified at any time, elements of the frozen set remain the same after creation.If no parameters are passed, it returns an empty frozenset.Python3normal_set = set([“a”, “b”,”c”])print(“Normal Set”)print(normal_set)frozen_set = frozenset([“e”, “f”, “g”])print(“nFrozen Set”)print(frozen_set)OutputNormal Set
{‘a’, ‘c’, ‘b’}

Frozen Set
frozenset({‘g’, ‘e’, ‘f’})StringPython Strings are arrays of bytes representing Unicode characters. In simpler terms, a string is an immutable array of characters. Python does not have a character data type, a single character is simply a string with a length of 1.Note: As strings are immutable, modifying a string will result in creating a new copy. Example: Python Strings OperationsPython3String = “Welcome to GeeksForGeeks”print(“Creating String: “)print(String)     print(“nFirst character of String is: “)print(String[0])     print(“nLast character of String is: “)print(String[-1])OutputCreating String:
Welcome to GeeksForGeeks

First character of String is:

Last character of String is:
sBytearrayPython Bytearray gives a mutable sequence of integers in the range 0 self.queue[max]:                    max = i            item = self.queue[max]            del self.queue[max]            return item        except IndexError:            print()            exit()if __name__ == ‘__main__’:    myQueue = PriorityQueue()    myQueue.insert(12)    myQueue.insert(1)    myQueue.insert(14)    myQueue.insert(7)    print(myQueue)               while not myQueue.isEmpty():        print(myQueue.delete())Output12 1 14 7
1Heap queue (or heapq)heapq module in Python provides the heap data structure that is mainly used to represent a priority queue. The property of this data structure in Python is that each time the smallest heap element is popped(min-heap). Whenever elements are pushed or popped, heap structure is maintained. The heap[0] element also returns the smallest element each time. It supports the extraction and insertion of the smallest element in the O(log n) times.Python3import heapqli = [5, 7, 9, 1, 3]heapq.heapify(li)print (“The created heap is : “,end=””)print (list(li))heapq.heappush(li,4)print (“The modified heap after push is : “,end=””)print (list(li))print (“The popped and smallest element is : “,end=””)print (heapq.heappop(li))OutputThe created heap is : [1, 3, 9, 7, 5]
The modified heap after push is : [1, 3, 4, 7, 5, 9]
The popped and smallest element is : 1Binary TreeA tree is a  hierarchical data structure that looks like the below figure –  tree
j 4 -> 3 -> 2 -> 0

Adjacency list of vertex 2
head -> 3 -> 1

Adjacency list of vertex 3
head -> 4 -> 2 -> 1

Adjacency list of vertex 4
head -> 3 -> 1 -> 0 Graph TraversalBreadth-First Search or BFSBreadth-First Traversal for a graph is similar to Breadth-First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. For simplicity, it is assumed that all vertices are reachable from the starting vertex.For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Breadth-First Traversal of the following graph is 2, 0, 3, 1. Python3from collections import defaultdictclass Graph:        def __init__(self):                self.graph = defaultdict(list)        def addEdge(self,u,v):        self.graph[u].append(v)        def BFS(self, s):                visited = [False] * (max(self.graph) + 1)                queue = []                        queue.append(s)        visited[s] = True        while queue:                                    s = queue.pop(0)            print (s, end = ” “)                                                            for i in self.graph[s]:                if visited[i] == False:                    queue.append(i)                    visited[i] = Trueg = Graph()g.addEdge(0, 1)g.addEdge(0, 2)g.addEdge(1, 2)g.addEdge(2, 0)g.addEdge(2, 3)g.addEdge(3, 3)print (“Following is Breadth First Traversal”                ” (starting from vertex 2)”)g.BFS(2)OutputFollowing is Breadth First Traversal (starting from vertex 2)
2 0 3 1 Time Complexity: O(V+E) where V is the number of vertices in the graph and E is the number of edges in the graph.Depth First Search or DFSDepth First Traversal for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, a node may be visited twice. To avoid processing a node more than once, use a boolean visited array.Algorithm:Create a recursive function that takes the index of the node and a visited array.Mark the current node as visited and print the node.Traverse all the adjacent and unmarked nodes and call the recursive function with the index of the adjacent node.Python3from collections import defaultdictclass Graph:        def __init__(self):                self.graph = defaultdict(list)        def addEdge(self, u, v):        self.graph[u].append(v)        def DFSUtil(self, v, visited):                        visited.add(v)        print(v, end=’ ‘)                        for neighbour in self.graph[v]:            if neighbour not in visited:                self.DFSUtil(neighbour, visited)            def DFS(self, v):                visited = set()                        self.DFSUtil(v, visited)g = Graph()g.addEdge(0, 1)g.addEdge(0, 2)g.addEdge(1, 2)g.addEdge(2, 0)g.addEdge(2, 3)g.addEdge(3, 3)print(“Following is DFS from (starting from vertex 2)”)g.DFS(2)OutputFollowing is DFS from (starting from vertex 2)
2 0 1 3 Time complexity: O(V + E), where V is the number of vertices and E is the number of edges in the graph. Attention geek! Strengthen your foundations with the Python Programming Foundation Course and learn the basics.  To begin with, your interview preparations Enhance your Data Structures concepts with the Python DS Course. And to begin with your Machine Learning Journey, join the Machine Learning – Basic Level Course