📘 PAPER 2: OBJECT ORIENTED PROGRAMMING WITH PYTHON UNIT 2 – Python Data Structures (university of allahabad)

 

🔴 UNIT 2 – Python Data Structures

---

1️⃣ Introduction to Python Data Structures

✅ What is a Data Structure?

A data structure is a way to store, organize, and manage data efficiently so that operations can be performed easily.

Python provides built-in data structures, such as:

• List

• Tuple

• Set

• Dictionary

---

2️⃣ Python Data Types (Revisited)

🔹 Mutable Data Types

Data that can be changed after creation.

• List

• Dictionary

• Set

🔹 Immutable Data Types

Data that cannot be changed.

• Integer

• Float

• String

• Tuple

---

3️⃣ Python Lists

✅ Definition

A list is an ordered, mutable collection of elements.

Example:

numbers = [10, 20, 30, 40]

---

🔹 List Characteristics

✔ Ordered
✔ Mutable
✔ Allows duplicate values
✔ Indexed

---

🔹 List Operations

Accessing elements

print(numbers[0])

Slicing

numbers[1:3]

Adding elements

numbers.append(50)

Removing elements

numbers.remove(20)

---

4️⃣ List Slicing

Syntax:

list[start : end : step]

Example:

a = [1,2,3,4,5]
print(a[1:4])

Output:

[2, 3, 4]

---

5️⃣ Indexing

• Positive indexing → Left to right

• Negative indexing → Right to left

a = [10, 20, 30]
print(a[-1])   # 30

---

6️⃣ List Concatenation

a = [1,2]
b = [3,4]
c = a + b

Output:

[1,2,3,4]

---

7️⃣ Searching in Python

🔹 Linear Search

Searches element one by one.

def linear_search(lst, key):
    for i in lst:
        if i == key:
            return True
    return False

✔ Simple
❌ Slow for large data

---

🔹 Binary Search

Works only on sorted lists

def binary_search(arr, key):
    low = 0
    high = len(arr)-1
    while low <= high:
        mid = (low+high)//2
        if arr[mid] == key:
            return True
        elif arr[mid] < key:
            low = mid+1
        else:
            high = mid-1
    return False

✔ Fast
✔ Efficient

---

8️⃣ Inductive Function Definition

Meaning:

A function defined using:

1. Base case

2. Recursive case

Example:

Factorial

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

---

9️⃣ Sorting Techniques

🔹 Selection Sort

Steps:

1. Find minimum

2. Swap with first element

3. Repeat

def selection_sort(arr):
    for i in range(len(arr)):
        min = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min]:
                min = j
        arr[i], arr[min] = arr[min], arr[i]

---

🔹 Insertion Sort

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key

---

🔟 In-Place Sorting

Definition:

Sorting without using extra memory.

✔ Selection Sort
✔ Insertion Sort

---

1️⃣1️⃣ Tuples

Definition:

Tuple is an ordered but immutable collection.

t = (10, 20, 30)

✔ Faster than list
✔ Used for fixed data

---

1️⃣2️⃣ Mutability Concept

Data Type	Mutable
List	Yes
Tuple	No
String	No
Dictionary	Yes

---

1️⃣3️⃣ Programs Using Lists

Find Maximum Element

lst = [4, 8, 2, 9]
print(max(lst))

Find Minimum Element

print(min(lst))

Find Mean

mean = sum(lst) / len(lst)