.png)
DSA Chapter 2 (Python Version): Arrays / Lists — The Core Structure of Python Programming
In Python, we use lists as the primary array-like data structure. They are dynamic, indexed, and highly flexible, making them extremely powerful for interviews and competitive programming.
What is a List in Python?
A list is a dynamic sequence of elements stored in contiguous memory (conceptually).
arr = [10, 20, 30, 40, 50]
Properties:
-
Ordered
-
Mutable(elements can be modified)
-
Dynamic (auto-resizes)
-
Allows mixed data types
Why Lists Are Important in Python DSA?
✔ Foundation for strings, matrices, stacks, queues, heaps, trees, and graphs
✔ Direct O(1) indexing
✔ Supports slicing, reversing, comprehensions
✔ Most interview problems start from lists
Time Complexity of Python List Operations
| Operation | Time Complexity | Explanation |
|---|---|---|
| Access element | O(1) | Indexing |
| Append | O(1) amortized | Uses dynamic resizing |
| Insert at end | O(1) amortized | Same as append |
| Insert at beginning | O(n) | Shift needed |
| Delete at beginning | O(n) | Shift needed |
| Search | O(n) | Linear scan |
| Pop() at end | O(1) | Removes last element |
| Pop(i) at index | O(n) | Shift needed |
Creating and Accessing List Elements
arr = [10, 20, 30, 40, 50]
print(arr[0]) # 10
print(arr[3]) # 40
print(arr[-1]) # 50 (last element)
Traversing a List
for x in arr:
print(x)
Using index:
for i in range(len(arr)):
print(arr[i])
Searching in List
Linear Search
def linear_search(arr, key):
for i in range(len(arr)):
if arr[i] == key:
return i
return -1
Insertion in List
Insert at index
arr.insert(2, 99)
Append at end
arr.append(60)
Extend with another list
arr.extend([70, 80])
Deletion in List
Delete by index
del arr[2]
Delete and return last element
arr.pop()
Delete by value
arr.remove(40)
List Slicing (Very Important)
arr = [10, 20, 30, 40, 50]
print(arr[1:4]) # [20, 30, 40]
print(arr[::-1]) # reverse list
print(arr[:3]) # first 3 elements
print(arr[2:]) # from index 2 to end
Most Important Python Array/ List Interview Problems
These are mandatory for placements.
1. Reverse a list
arr = arr[::-1]
or
arr.reverse()
2. Find max/min
maximum = max(arr)
minimum = min(arr)
3. Rotate list by k
def rotate(arr, k):
k %= len(arr)
return arr[-k:] + arr[:-k]
4. Move all zeros to end
def move_zeros(arr):
return [x for x in arr if x != 0] + [0]*arr.count(0)
5. Remove duplicates
arr = list(set(arr))
6. Find missing number 1 to n
def missing(arr):
n = len(arr) + 1
return n*(n+1)//2 - sum(arr)
7. Second largest
arr_sorted = sorted(set(arr))
second_largest = arr_sorted[-2]
8. Kadane’s Algorithm (Max subarray sum)
def kadane(arr):
max_so_far = arr[0]
curr = 0
for x in arr:
curr = max(x, curr + x)
max_so_far = max(max_so_far, curr)
return max_so_far
9. Two-sum problem
def two_sum(arr, target):
seen = {}
for i, num in enumerate(arr):
diff = target - num
if diff in seen:
return [seen[diff], i]
seen[num] = i
10. Count frequencies
from collections import Counter
freq = Counter(arr)
Python Practice Questions
-
Write a Python program to find the largest element in a list.
-
Reverse a list without using built-in functions.
-
Rotate a list by k steps.
-
Remove duplicates while preserving order.
-
Find the missing number in a list from 1 to n.
-
Implement linear search without using
in. -
Count occurrences of each element without using Counter.
-
Find the second largest element.
-
Implement Kadane’s algorithm.
-
Move all zeros to end.
(If you want, I can provide answers for all 10.)
✔ Conclusion
Python lists are extremely powerful and serve as the foundation for:
-
Strings
-
Matrices
-
Dynamic programming
-
Graph algorithms
-
Backtracking
-
Tree & heap implementations
Mastering list operations ensures a strong DSA base.
ALSO CHECK
ALSO CHECK
Comments
Post a Comment