Complete tutorial of Data Structure in Python

Python Data Structures: Comprehensive Guide

Table of Contents

1. Introduction to Data Structures
2. List
• Overview
• Predefined Methods
• Real-World Example
• List Comprehension
• Multi-Dimensional List
3. Tuple
• Overview
• Predefined Methods
• Real-World Example
4. Dictionary
• Overview
• Complexity
• Predefined Methods
• Real-World Example
5. Set
• Overview
• Complexity
• Predefined Methods
• Real-World Example
6. Frozen Set
• Overview
• Example
7. Array
• Overview
• Complexity
• Example
8. Linked List
• Overview
• Complexity
• Example
9. Stack
• Overview
• Complexity
• Example
10. Queue
• Overview
• Complexity
• Example

---

1. Introduction to Data Structures

Data structures are fundamental for organizing and storing data efficiently. Python provides built-in data structures like lists, tuples, dictionaries, sets, and more. Understanding these structures helps in solving problems effectively.

---

2. List

What is a List?

• A list is an ordered collection of elements.
• Mutable: You can modify its content after creation.
• Dynamic: Automatically grows or shrinks as needed.
• Allows duplicates.

Syntax

my_list = [1, 2, 3, 4, 5]

---

Characteristics of Lists

1. Indexing and Slicing: Access elements by index or retrieve sublists.
2. Dynamic Typing: Can store mixed data types.
3. Flexible Size: No need to predefine the size.

---

Operations on Lists

Basic List Operations

Operation	Description	Example
+	Concatenates two lists	[1, 2] + [3, 4] → [1, 2, 3, 4]
*	Repeats the list	[1, 2] * 2 → [1, 2, 1, 2]
Membership (in)	Checks if an item is in the list	2 in [1, 2, 3] → True
Iteration	Loops through the list	for x in my_list:

Accessing Elements

my_list = [1, 2, 3, 4, 5]

print(my_list[0])   # Access first element → 1

print(my_list[-1])  # Access last element → 5

print(my_list[1:4]) # Slicing (1st to 3rd index) → [2, 3, 4]

---

Predefined Methods in Lists

Method	Description	Example
append(x)	Adds an element to the end of the list	my_list.append(6)
extend(iterable)	Extends the list by appending all elements of an iterable	my_list.extend([7, 8])
insert(index, x)	Inserts an element at the specified index	my_list.insert(2, 10)
pop([index])	Removes and returns the element at the specified index. If no index, removes the last element	my_list.pop()
remove(x)	Removes the first occurrence of an element	my_list.remove(3)
index(x, [start, end])	Returns the index of the first occurrence of an element	my_list.index(4)
count(x)	Counts the occurrences of an element	my_list.count(3)
reverse()	Reverses the list in place	my_list.reverse()
sort()	Sorts the list in ascending order by default	my_list.sort()
clear()	Removes all elements from the list	my_list.clear()

Examples

my_list = [1, 2, 3, 4, 5]

my_list.append(6)

print(my_list)  # [1, 2, 3, 4, 5, 6]

 

my_list.remove(3)

print(my_list)  # [1, 2, 4, 5, 6]

---

Advanced Topics: List Comprehensions

What is List Comprehension?

• A concise way to create or modify lists using a single line of code.
• Syntax:

[expression for item in iterable if condition]

Examples

1. Create a list of squares

squares = [x**2 for x in range(1, 6)]

print(squares)  # [1, 4, 9, 16, 25]

2. Filter even numbers

even_numbers = [x for x in range(10) if x % 2 == 0]

print(even_numbers)  # [0, 2, 4, 6, 8]

3. Convert to uppercase

names = ["alice", "bob", "charlie"]

uppercase_names = [name.upper() for name in names]

print(uppercase_names)  # ['ALICE', 'BOB', 'CHARLIE']

4. Nested Comprehensions

matrix = [[i * j for j in range(1, 4)] for i in range(1, 4)]

print(matrix)  # [[1, 2, 3], [2, 4, 6], [3, 6, 9]]

---

Multi-Dimensional Lists

• Lists within lists to represent matrices, tables, or grids.

Example

# Creating a 3x3 matrix

matrix = [

    [1, 2, 3],

    [4, 5, 6],

    [7, 8, 9]

]

 

# Accessing elements

print(matrix[0][1])  # Access row 1, column 2 → 2

 

# Iterating through rows

for row in matrix:

    print(row)

 

# Flattening a 2D list

flat_list = [num for row in matrix for num in row]

print(flat_list)  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

---

Real-World Applications of Lists

1. Dynamic Data Storage:
• Example: Keeping track of items in a shopping cart.
2. Batch Processing:
• Example: Apply transformations to a list of images.
3. Tabular Data:
• Example: Representing rows in a table or grid.

---

Common Mistakes and Tips

Mistakes

1. Modifying a list while iterating over it
• Solution: Use list comprehension or iterate over a copy.
2. Using a mutable list as a default parameter
• Solution: Use None as the default and initialize the list inside the function.

 

---

3. Tuple

What is a Tuple?

• Definition: A tuple is an immutable and ordered collection of elements.
• Syntax: Defined using parentheses () or tuple() constructor.
• Immutable: Once created, elements cannot be modified, added, or removed.
• Fixed Size: The size of a tuple is fixed after creation.

Examples

my_tuple = (1, 2, 3, 4, 5)

empty_tuple = ()

single_element_tuple = (1,)  # Note the comma

tuple_from_list = tuple([1, 2, 3])

---

Characteristics of Tuples

1. Order is maintained: Elements are stored in the order you define.
2. Heterogeneous elements: Can store mixed data types.
3. Immutable: Safer to use when data integrity is crucial.

---

Why Use Tuples?

• Immutability makes tuples a good choice for:
• Data that should not change after creation.
• Keys for dictionaries (since mutable types like lists cannot be used as keys).
• Performance:
• Tuples are faster than lists because of their immutability.
• Use tuples to save memory and enhance execution speed.

---

Tuple Operations

Operation	Example	Output
Access elements	my_tuple[1]	2
Slicing	my_tuple[1:3]	(2, 3)
Length	len(my_tuple)	5
Concatenation	(1, 2) + (3, 4)	(1, 2, 3, 4)
Repetition	('a',) * 3	('a', 'a', 'a')
Membership	3 in my_tuple	True
Iteration	for x in my_tuple: print(x)	Prints each element

---

Tuple Methods

Tuples have fewer methods due to immutability:

Method	Description	Example
count(x)	Returns the count of occurrences of x.	(1, 2, 2, 3).count(2) → 2
index(x)	Returns the index of the first occurrence.	(1, 2, 3).index(2) → 1

---

Tuple Unpacking

You can unpack tuples into variables directly:

coordinates = (10, 20, 30)

x, y, z = coordinates

print(x, y, z)  # Output: 10 20 30

---

Use Cases of Tuples

1. Immutable Data Storage: E.g., GPS coordinates.
2. Dictionary Keys:

python

Copy code

location = {(40.7128, 74.0060): "New York"}

3. Returning Multiple Values from Functions:

python

Copy code

def calculate(a, b):

    return a + b, a * b

 

sum_, product = calculate(3, 4)

print(sum_, product)  # Output: 7, 12

4. Fixed Collections: Representing days of the week or months.

---

Performance Comparison: List vs. Tuple

Feature	List	Tuple
Mutability	Mutable: Can be modified.	Immutable: Cannot be modified.
Performance	Slower due to dynamic nature.	Faster due to immutability.
Size	Uses more memory.	Uses less memory.
Methods	Rich set of methods.	Fewer methods.
Use Cases	Dynamic, frequently changing data.	Static, fixed data.

---

When to Use List vs. Tuple

Use a List When:

1. Dynamic Data: You need to add, remove, or change elements frequently.
• Example: Managing a to-do list.

python

Copy code

tasks = ["Task1", "Task2"]

tasks.append("Task3")

2. Complex Operations: When you need built-in methods like sorting, reversing, etc.

numbers = [3, 1, 4, 2]

numbers.sort()

print(numbers)  # [1, 2, 3, 4]

Use a Tuple When:

1. Fixed Data: When the data is static or shouldn’t be modified.
• Example: Storing months of the year.

python

Copy code

months = ("January", "February", "March", "April")

2. Dictionary Keys: To represent immutable and hashable data.

python

Copy code

locations = {(10.0, 20.0): "Point A", (30.0, 40.0): "Point B"}

3. Function Returns: When a function needs to return multiple values.

python

Copy code

def get_status():

    return "Active", 200

 

status, code = get_status()

print(status, code)  # Output: Active 200

---

Real-World Examples

1. Tuple as Coordinates

coordinates = (40.7128, 74.0060)  # Latitude and Longitude

print(f"Latitude: {coordinates[0]}, Longitude: {coordinates[1]}")

2. Tuple for Storing Constant Data

days_of_week = ("Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday")

3. Tuples in Functions

def get_rectangle_properties(length, width):

    return length * width, 2 * (length + width)

 

area, perimeter = get_rectangle_properties(5, 10)

print(f"Area: {area}, Perimeter: {perimeter}")

---

Advantages of Tuples

1. Immutability: Safer to use when data should not change.
2. Faster: Operations on tuples are generally faster than on lists.
3. Memory-Efficient: Consumes less memory than lists.

 

---

4. Dictionary

Overview

• Unordered collection of key-value pairs.
• Keys must be unique and immutable.

Complexity

• Access by key: $O(1)$O(1)
• Insertion/Deletion: $O(1)$O(1)

Predefined Methods

 my_dict = {'a': 1, 'b': 2}

my_dict.keys()            # Get keys

my_dict.values()          # Get values

my_dict.items()           # Get key-value pairs

my_dict.get('a')          # Get value of key 'a'

my_dict.pop('b')          # Remove key 'b'

Real-World Example

• Phone directory:

phone_book = {"John": 123456, "Alice": 987654}

---

5. Set

A set in Python is an unordered, mutable collection of unique elements. Sets are commonly used to store and manipulate datasets where duplicates are not allowed, making them ideal for membership testing and removing duplicates.

---

Characteristics of Sets

1. Unordered: The elements in a set do not have a defined order.
2. Mutable: Elements can be added or removed (but not updated directly).
3. Unique Elements: Duplicate elements are automatically removed.
4. Hashable Elements: The elements in a set must be immutable (e.g., strings, numbers, tuples).

---

Set Syntax

Creating Sets

# Using curly braces

my_set = {1, 2, 3, 4}

print(my_set)  # Output: {1, 2, 3, 4}

# Using the set() function

empty_set = set()  # Only way to create an empty set

print(empty_set)  # Output: set()

# With duplicate values (duplicates are removed)

duplicate_set = {1, 2, 2, 3}

print(duplicate_set)  # Output: {1, 2, 3}

---

Set Operations

Operation	Syntax / Method	Description
Add Element	set.add(element)	Adds a single element to the set.
Remove Element	set.remove(element)	Removes an element (throws error if not found).
Discard Element	set.discard(element)	Removes an element (no error if not found).
Pop Element	set.pop()	Removes and returns an arbitrary element.
Clear Set	set.clear()	Removes all elements from the set.
Union	set1.union(set2)	Returns a new set containing all elements.
Intersection	set1.intersection(set2)	Returns a new set with common elements.
Difference	set1.difference(set2)	Elements in set1 but not in set2.
Symmetric Difference	set1.symmetric_difference(set2)	Elements in either set but not in both.
Subset Check	set1.issubset(set2)	Checks if set1 is a subset of set2.
Superset Check	set1.issuperset(set2)	Checks if set1 is a superset of set2.
Disjoint Check	set1.isdisjoint(set2)	Checks if sets have no common elements.

---

Examples of Set Methods

Adding Elements

my_set = {1, 2, 3}

my_set.add(4)

print(my_set)  # Output: {1, 2, 3, 4}

Removing Elements

my_set = {1, 2, 3}

my_set.remove(2)  # Removes 2

print(my_set)     # Output: {1, 3}

# my_set.remove(5)  # Throws a KeyError

my_set.discard(5)  # Does not throw an error if element not found

Union

Combines all unique elements from two sets.

set1 = {1, 2, 3}

set2 = {3, 4, 5}

print(set1.union(set2))  # Output: {1, 2, 3, 4, 5}

Intersection

Finds common elements between two sets.

set1 = {1, 2, 3}

set2 = {3, 4, 5}

print(set1.intersection(set2))  # Output: {3}

Difference

Finds elements in one set but not the other.

set1 = {1, 2, 3}

set2 = {3, 4, 5}

print(set1.difference(set2))  # Output: {1, 2}

Symmetric Difference

Finds elements in either set but not in both.

set1 = {1, 2, 3}

set2 = {3, 4, 5}

print(set1.symmetric_difference(set2))  # Output: {1, 2, 4, 5}

Subset, Superset, and Disjoint Checks

set1 = {1, 2}

set2 = {1, 2, 3}

print(set1.issubset(set2))     # Output: True

print(set2.issuperset(set1))   # Output: True

print(set1.isdisjoint({4, 5})) # Output: True

---

Iterating Over a Set

my_set = {1, 2, 3, 4}

for item in my_set:

    print(item)

---

Real-World Use Cases

1. Removing Duplicates from a List

names = ["Alice", "Bob", "Alice", "Eve"]

unique_names = set(names)

print(unique_names)  # Output: {'Alice', 'Bob', 'Eve'}

2. Finding Common Friends

friends_A = {"Alice", "Bob", "Charlie"}

friends_B = {"Bob", "Diana", "Charlie"}

common_friends = friends_A.intersection(friends_B)

print(common_friends)  # Output: {'Bob', 'Charlie'}

3. Finding Unique Words in a Text

text = "The quick brown fox jumps over the lazy dog"

unique_words = set(text.split())

print(unique_words)

# Output: {'The', 'quick', 'brown', 'fox', 'jumps', 'over', 'the', 'lazy', 'dog'}

4. Set Operations in a Survey

survey_A = {"red", "blue", "green"}

survey_B = {"blue", "yellow", "green"}

both_surveys = survey_A.union(survey_B)

only_A = survey_A.difference(survey_B)

common_colors = survey_A.intersection(survey_B)

print(both_surveys, only_A, common_colors)

---

Advantages of Sets

1. Efficient Membership Testing: Checking if an element exists in a set is O(1).
2. Automatic Duplicate Removal: Convenient for filtering unique items.
3. Flexible Mathematical Operations: Intersection, union, and difference.

---

Limitations of Sets

1. Unordered: No indexing or slicing.
2. Only Immutable Elements: Cannot store mutable types like lists or other sets.

 

---

6. Frozen Set

Overview

• Immutable set.

Example

f_set = frozenset([1, 2, 3])

---

7. Array

Overview

• Stores elements of the same type.

Complexity

• Access: $O(1)$O(1)
• Insert/Delete: $O(n)$O(n)

Example

from array import array

arr = array('i', [1, 2, 3])

arr.append(4)

Question List:

Array Practice Program?
Q1)  WAP to find max and second max char in String?
     String s = "hello";   output o is the max char and l is the second max
Q2)  WAP to find second max prime elements in the jagged array?
Q3)   WAP to sort only odd elements in an array?
      12 21 34 56 67 89 3 88 7
  o/p    12 3  34 56 7  21 67 88
MOST Important Array Interview Questions for Interview?
Check if a key is present in every segment of size k in an array
Find the minimum and maximum element in an array
Write a program to reverse the array
Write a program to sort the given array
Find the Kth largest and Kth smallest number in an array
Find the occurrence of an integer in the array
Sort the array of 0s, 1s, and 2s
Range and Coefficient of array
Move all the negative elements to one side of the array
Find the Union and Intersection of the two sorted arrays

Level 2
Write a program to cyclically rotate an array by one
Find the missing integer
Count Pairs with given sum
Find duplicates in an array
Sort an Array using the Quicksort algorithm
Find common elements in three sorted arrays
Find the first repeating element in an array of integers
Find the first non-repeating element in a given array of integers
Find the largest three elements in an array Time
Rearrange the array in alternating positive and negative items
Find if there is any subarray with sum equal to zero
Find Largest sum contiguous Subarray
Find the factorial of a large number
Find Maximum Product Subarray
Find longest consecutive subsequence
Find the minimum element in a rotated and sorted array
Find all elements that appear more than N/K times
GCD of given index ranges in an array
Minimize the maximum difference between the heights
Minimum number of jumps to reach the end
Find the two repetitive elements in a given array
Find a triplet that sums to a given value
Construct a N*M matrix from the user input
Find the row with the maximum number of 1’s
Print the matrix in a Spiral manner
Find whether an array is a subset of another array
Implement two Stacks in an array
Majority Element
Wave Array
Trapping Rainwater
Level 3

Maximum Index
Max sum path in two arrays
Find Missing And Repeating
Stock buy and sell Problem
Pair with given sum in a sorted array
Chocolate Distribution Problem
Longest Consecutive Subsequence
Print all possible combinations of r elements in a given array

---

8. Linked List

A Linked List is a linear data structure in which elements (called nodes) are linked using pointers. Each node contains two parts:

1. Data: The value stored in the node.
2. Pointer: A reference to the next node in the sequence.

---

Types of Linked Lists

1. Singly Linked List: Each node points to the next node.
2. Doubly Linked List: Each node points to both its next and previous nodes.
3. Circular Linked List: The last node points back to the first node, forming a circle.

---

Key Characteristics of Linked Lists

• Dynamic Size: Can grow or shrink during runtime.
• Efficient Insertions/Deletions: Unlike arrays, no shifting is required.
• Sequential Access: No direct access; traversal is required.

---

Implementation of a Singly Linked List in Python

Node Class

Each node stores data and a reference to the next node.

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

LinkedList Class

Manages nodes and provides utility methods.

class LinkedList:

    def __init__(self):

        self.head = None

    # Insert at the end

    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

    # Print the list

    def display(self):

        current = self.head

        while current:

            print(current.data, end=" -> ")

            current = current.next

        print("None")

Example Usage

ll = LinkedList()

ll.append(10)

ll.append(20)

ll.append(30)

ll.display()  # Output: 10 -> 20 -> 30 -> None

---

Commonly Used Methods for Linked Lists

Operation	Description	Complexity
append(data)	Adds a node at the end of the list	O(n)
prepend(data)	Adds a node at the beginning	O(1)
delete(data)	Deletes the first occurrence of a node	O(n)
search(data)	Searches for a node with the given data	O(n)
insert_after(node, data)	Inserts a node after a given node	O(1)
length()	Returns the length of the linked list	O(n)
reverse()	Reverses the linked list	O(n)

---

Method Implementations

1. Append a Node

Add a node to the end of the list.

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

2. Prepend a Node

Add a node at the beginning of the list.

def prepend(self, data):

    new_node = Node(data)

    new_node.next = self.head

    self.head = new_node

3. Delete a Node

Remove the first occurrence of a node with the specified value.

def delete(self, key):

    current = self.head

    # If the head node holds the key

    if current and current.data == key:

        self.head = current.next

        current = None

        return

    prev = None

    while current and current.data != key:

        prev = current

        current = current.next

    if not current:  # Key not found

        return

    prev.next = current.next

    current = None

4. Reverse a Linked List

Reverse the order of nodes in the list.

def reverse(self):

    prev = None

    current = self.head

    while current:

        next_node = current.next

        current.next = prev

        prev = current

        current = next_node

    self.head = prev

5. Search for a Node

Check if a node with the specified value exists.

def search(self, key):

    current = self.head

    while current:

        if current.data == key:

            return True

        current = current.next

    return False

---

Example: Full Linked List Implementation

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 = self.head

        while last.next:

            last = last.next

        last.next = new_node

    def prepend(self, data):

        new_node = Node(data)

        new_node.next = self.head

        self.head = new_node

    def delete(self, key):

        current = self.head

        if current and current.data == key:

            self.head = current.next

            current = None

            return

        prev = None

        while current and current.data != key:

            prev = current

            current = current.next

        if current is None:

            return

        prev.next = current.next

        current = None

    def display(self):

        current = self.head

        while current:

            print(current.data, end=" -> ")

            current = current.next

        print("None")

# Usage

ll = LinkedList()

ll.append(10)

ll.append(20)

ll.prepend(5)

ll.display()  # Output: 5 -> 10 -> 20 -> None

ll.delete(10)

ll.display()  # Output: 5 -> 20 -> None

---

Advantages of Linked Lists

1. Dynamic Size: No need for pre-allocated memory.
2. Efficient Insertions/Deletions: Faster than arrays for these operations.
3. Sequential Access: Data can be accessed in sequence.

---

Disadvantages of Linked Lists

1. No Random Access: Traversal is required to access elements.
2. Overhead: Each node requires extra memory for the pointer.
3. Cache Unfriendliness: Elements are not stored contiguously in memory.

---

When to Use Linked Lists

• Use a Linked List if:
• Frequent insertions or deletions are required.
• Memory usage is not a constraint.
• Random access is not needed.

 

---

9. Stack

Overview

• Follows Last In, First Out (LIFO).

Complexity

• Push/Pop: $O(1)$O(1)

Example

stack = []

stack.append(1)  # Push

stack.append(2)

stack.pop()      # Pop

---

10. Queue

Overview

• Follows First In, First Out (FIFO).

Complexity

• Enqueue/Dequeue: $O(1)$O(1)

Example

from collections import deque

queue = deque()

queue.append(1)  # Enqueue

queue.popleft()  # Dequeue 

Tree in DSA:

Most of the cases python real-time application prefer Binary Tree and Binary Search Tree .

Binary Tree contain two sub node to all adjacent node without any order but Binary Search tree 

maintain order to add elements on left and right position if current element is less than root 

element then it added into left otherwise on the right.

class Node: 
    def __init__(self, value): 
        self.value = value 
        self.left = None 
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, current_node):
        if value < current_node.value:
            if current_node.left is None:
                current_node.left = Node(value)
            else:
                self._insert(value, current_node.left)
        elif value > current_node.value:
            if current_node.right is None:
                current_node.right = Node(value)
            else:
                self._insert(value, current_node.right)
        else:
            print("Value already in tree!")

    def in_order_traversal(self):
        if self.root is not None:
            self._in_order_traversal(self.root)

    def _in_order_traversal(self, current_node):
        if current_node is not None:
            self._in_order_traversal(current_node.left)
            print(current_node.value, end=" ")
            self._in_order_traversal(current_node.right)

if __name__ == "__main__":

    tree = BinaryTree()

    tree.insert(10)

    tree.insert(5)

    tree.insert(15)

    tree.insert(2)

    tree.insert(7)

    tree.insert(12)

    tree.insert(17)

    print("In-order traversal of the tree:")

    tree.in_order_traversal()

Click to Join DSA Course