DSA in Python: A Practical Guide with Code Examples

Introduction to DSA with Python

Data Structures and Algorithms (DSA) are fundamental building blocks of computer science. Mastering DSA is crucial for writing efficient, scalable, and optimized software. Python, with its clear syntax and extensive libraries, is an excellent language for learning and implementing DSA concepts. If you are serious about your career, consider visiting SWE180 DSA guide.

Arrays and Lists

Arrays and lists are fundamental data structures. Python's built-in list type is a dynamic array.

Array Operations

• Accessing element: arr[i] - O(1)
• Insertion at the end: arr.append(x) - O(1) amortized
• Insertion at the beginning: arr.insert(0, x) - O(n)
• Deletion at the end: arr.pop() - O(1)
• Deletion at the beginning: arr.pop(0) - O(n)

arr = [1, 2, 3, 4, 5]
print(arr[0])  # Output: 1
arr.append(6)
print(arr)  # Output: [1, 2, 3, 4, 5, 6]
arr.insert(0, 0)
print(arr)  # Output: [0, 1, 2, 3, 4, 5, 6]
arr.pop()
print(arr)  # Output: [0, 1, 2, 3, 4, 5]
arr.pop(0)
print(arr)  # Output: [1, 2, 3, 4, 5]

For beginners, check out our DSA Beginner Sheet.

Linked Lists

Linked Lists are linear data structures where elements are stored in nodes, and each node contains a value and a pointer to the next node.

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

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

• Insertion at the head: O(1)
• Insertion at the tail: O(n) (if you need to traverse to the end)
• Deletion at the head: O(1)
• Deletion at the tail: O(n) (if need to traverse for finding the previous node)
• Searching for an Element: O(n)

Stacks and Queues

Stacks operate on the LIFO (Last-In, First-Out) principle, while Queues follow the FIFO (First-In, First-Out) principle. Python lists can be cleverly used to implement these. Consider practicing Core subjects to build strong foundations.

Stack Implementation

stack = []
# Push (add) elements
stack.append(1)
stack.append(2)
stack.append(3)

# Pop (remove) elements
print(stack.pop()) # Output: 3
print(stack.pop()) # Output: 2

Queue Implementation

from collections import deque
queue = deque()

# Enqueue (add) elements
queue.append(1)
queue.append(2)
queue.append(3)

# Dequeue (remove) elements
print(queue.popleft()) # Output: 1
print(queue.popleft()) # Output: 2

• Stack Push and Pop operations: O(1)
• Queue Enqueue and Dequeue operations: O(1) (using deque)

Trees and Graphs

Trees and graphs are non-linear data structures used to represent hierarchical and network structures respectively. Binary Trees, Binary Search Trees(BSTs), and graph traversals are important concepts.

Prepare better with Mock Interviews to better understand tree and graph related questions.

Sorting Algorithms

Sorting algorithms arrange elements of a list in a specific order. Common sorting algorithms include:

• Bubble Sort: Implemented and time complexity O(n^2)
• Selection Sort: Implemented and time complexity O(n^2)
• Insertion Sort: Implemented and time complexity O(n^2)
• Merge Sort: O(n log n)
• Quick Sort: Average O(n log n), Worst O(n^2)

Searching Algorithms

• Linear Search: O(n)
• Binary Search: O(log n) - requires sorted data

Conclusion

This hands-on guide provided a brief introduction to key DSA concepts in Python. By practicing these concepts and exploring more advanced topics, you can significantly enhance your problem-solving and coding skills. Consider using Flashcards to accelerate your memorisation.

Need help with Resume Review?

To further elevate your skills, explore Roadmaps and Aptitude resources. You will do well with Mentorship.