Python Data Structure Guide (Side by Side Comparison with C++)
AMAN VARYANI
8223
PythonCareer

Python Data Structure Guide

image

About Me:
I am a Software Developer having almost 2 years of experience in python and on coding platforms i use C++.

Why this post

  1. I am shifting to python as in some of my interview the language is restricted to python only. So I face difficulty when trying to implement simple thing like sorting, priority queue etc.

  2. Easier to debug code (we can print the whole dict, list, etc with print)

  3. Will be helpful for those who started coding in python, or shifting to python.

  4. Not finding any good resource on internet for detail explaination of DSA in python.

Not Covered in this post

  • Basic data structure topic: list, string, set etc you can find plenty of resources on internet.
  • How to create object, class etc.
  • Slicing for list and string

LETS GET START

1. Replace Character in a string :

  • Strings are immutable in python so the following operation will not work.

    str1 = “test”

    str1[idx] = ‘c’

2. SortedDict

  • In C++ we have map which stores the key in sorted order likewise we have sorted dict in python ( python dict will be same as unordered map)

3. Custom Comparator

  • Custom Comparator is used to sort the list, priority_queue etc, which can be used in the complex data

    • When providing a custom comparator, it should generally return an integer/float value that follows the following pattern (as with most other programming languages and frameworks):

    • return a negative value (< 0) when the left item should be sorted before the right item

    • return a positive value (> 0) when the left item should be sorted after the right item

    • return 0 when both the left and the right item have the same weight and should be ordered "equally" without precedence

4. INT_MAX and INT_MIN in Python

	print(float('inf'))
	print(float('-inf'))

5. Priority Queue

heapq is the module which is used to implement priority queue.

Initialize : priority_queue = []

1. Create O(n) https://stackoverflow.com/a/18295327
heapq.heapify(priority_queue)

2. Push O(logn)
Push the element in the list heapq.heappush(priority_queue, element)

3.Top Element O(1)
priority_queue[0]

4. Pop Element O(logn)
heapq.heappop(priority_queue)

Below is the example using code.

6. Binary search functions

from bisect import bisect_left, bisect_right
arr = [1,2,2,3,3,4,5,6]

# Syntax : bisect.bisect_left(array, key)
print(arr)
print(f"Lower bound : {bisect_left(arr, 2)}") # idx of first number greater than or equal to key.
print(f"Upper Bound : {bisect_right(arr,2)}") # idx of first number greater than key.

"""
Output: 
[1, 2, 2, 3, 3, 4, 5, 6]
Lower bound : 1
Upper Bound : 3
"""

**

7. Initialize 2D array(useful for dp)

m = 4 # row 
n = 5 # column

dp = [[-1 for _ in range(n)] for _ in range(m)]
print(dp)

Fact:
res = [[0]*n]*m
Never Initialize 2D array like this.

if you do res[i][j] = 0 in loop it will update the value for whole rows.

This makes every element in the array reference the same value. Use a list comprehension to initialize the list instead, which will copy all the elements. This is the pythonic way to initialize lists.

eg: https://stackoverflow.com/questions/72747802/updating-matrix-values-updates-entire-row

8. Stack

Stack can be implemented using simple list
stack = []
# push operation O(1)
stack.append(1)
stack.append(2)

# pop operation O(1) 
stack.pop()

print(stack)

"""
output
[1]
"""

9. Queue

For implementing queue there are 3 methods:

  • list
  • collections.deque
  • queue.Queue

List is not recommended because time complexity of pop is O(n)
Below is the implementation using deque.

# deque is double ended queue which can be used both as stack and queue
from collections import deque

queue = deque([])
queue.append(1)
queue.append(2)

queue.popleft() # O(1) https://stackoverflow.com/a/32543863

print(queue)

"""
Output:
deque([2])
"""

Some Bonus Section

  • How do I round a floating point number up to a certain decimal place?

    import math
v = 2.35776796976

print(int(v*102)/102)  # 2.35

print(math.ceil(v*102)/102)  # -> 2.36

print(math.floor(v*1000)/1000)  # -> 2.35

  • Maths Operation

    import math
# floor
a = 5.67

print(f"Floor of {a}: {math.floor(a)}")
print(f"Ceil of {a} : {math.ceil(a)}")

# gcp of two number (math.gcd(a,b))
a = 2
b = 6

print(f"\nGCD of ({a},{b}) is {math.gcd(a,b)}")

# bin used to represent number in binary
b = 6
print(f"Binary representation of {b}: {bin(b)}")

"""
Output:
Floor of 5.67: 5
Ceil of 5.67 : 6

GCD of (2,6) is 2
Binary representation of 6: 0b110
"""

  • Taking Input in python

    # single input 
a = input()
print(a)

# more than one input

x, y = input("Enter Two numbers: ").split()
print(f"Entered numbers are {x} {y}")

# taking multiple inputs at a time with type casting
input_list = [int(a) for a in input("Enter multiple values: ").split()]
print("list is: ", input_list)

In case you want to add anything important which i missed please add it in comment.

( If you find this post helpful plz upvote 👍)

Google Colab Notebook Link
Please leave a 🌟on repo if you like this post Github.

Lets connect for any discussion here

Comments (13)