Unit 1: Arrays/List

1.1 Introduction & Definition of an Array in Data Structure

Introduction

An array is one of the most basic and widely used linear data structures in
computer science.
It is a collection of homogeneous (same type) elements stored at contiguous
memory locations.
This allows easy access to elements using an index.

• Arrays are used to store data in a structured way.

• The index of an array usually starts from 0.

• They are widely used because they provide fast access (O(1)) to any
element.

Definition

An array is a collection of elements of the same data type, arranged in

consecutive memory locations, and accessed using a common name with an
index.

Formally:
If A is an array of size n, it can be represented as:

A=[a0,a1,a2,…,an−1] A = [a_0, a_1, a_2, …, a_{n-1}]

where each a_i is an element, and i is the index.

Characteristics of Arrays

1. Fixed Size – Once declared, the size of the array cannot be changed (in
static arrays).

2. Homogeneous Elements – All elements must be of the same data type.

3. Contiguous Memory Allocation – Elements are stored in consecutive

memory locations.

4. Index-based Access – Each element can be directly accessed using its

index.
 5. Efficient Traversal – Arrays allow sequential or random access
efficiently.

Example in Python

# Creating an array using Python list

arr = [10, 20, 30, 40, 50]

# Access elements

print("First element:", arr[0])

print("Last element:", arr[4])

# Traversal

for i in range(len(arr)):

print(f"Element at index {i}:", arr[i])

Output:

First element: 10

Last element: 50

Element at index 0: 10

Element at index 1: 20

Element at index 2: 30

Element at index 3: 40

Element at index 4: 50
1.2 Memory Allocation & Indexing

Memory Allocation in Arrays

• In arrays, memory is allocated in contiguous (continuous) memory

blocks.

• Each element of the array occupies a fixed amount of memory depending

on its data type.

o Example: An integer may take 4 bytes, a float may take 8 bytes.

• The base address is the memory address of the first element.

• Address of the i-th element can be calculated as:

Indexing

• Array indexing starts from 0 (zero-based indexing) in most programming

languages including Python.

• If an array has n elements, the valid index range is 0 to n-1.

• Elements can be accessed using their index number.

Using Python List (Dynamic Array)

# Creating an array (list in Python)

arr = [10, 20, 30, 40, 50]

# Indexing

print("First element (arr[0]):", arr[0])

print("Third element (arr[2]):", arr[2])

print("Last element (arr[-1]):", arr[-1]) # Negative indexing

Output:

First element (arr[0]): 10

Third element (arr[2]): 30

Last element (arr[-1]): 50

Memory Allocation in Python Arrays

We can check memory addresses using the id() function:

arr = [10, 20, 30, 40, 50]

for i in range(len(arr)):

print(f"Element {arr[i]} is stored at memory location:", id(arr[i]))

Note:

• In C/C++, arrays guarantee contiguous allocation.

• In Python lists, elements are objects, so they may not be stored

contiguously in memory.

• For true contiguous arrays, Python provides the array module.

Using Python array module (C-style array)

import array

# Array of integers

arr = [Link]('i', [10, 20, 30, 40, 50])

print("Base address of array:", arr.buffer_info()[0]) # starting address

print("Size of each element (bytes):", [Link])

# Access with index

for i in range(len(arr)):

address = arr.buffer_info()[0] + i * [Link]

print(f"arr[{i}] = {arr[i]} stored at {address}")

Output (example):

Base address of array: 234567890

Size of each element (bytes): 4

arr[0] = 10 stored at 234567890

arr[1] = 20 stored at 234567894

arr[2] = 30 stored at 234567898

arr[3] = 40 stored at 234567902

arr[4] = 50 stored at 234567906

Memory Allocation → Arrays store elements in contiguous memory.

Indexing → Zero-based indexing (0 to n-1), also supports negative indexing in

Python lists.

Python list = dynamic, not strictly contiguous.

Python array module = contiguous memory, similar to C arrays.

1.3 Operations on 1-D & 2-D Arrays/Lists

Arrays (or lists in Python) support a variety of basic operations. These are used
for accessing, updating, traversing, and manipulating elements.

Operations on 1-D Array (List in Python)

A 1-D array is a linear collection of elements.

Traversal (Visiting each element)

arr = [10, 20, 30, 40, 50]

print("Traversal of array:")

for i in range(len(arr)):

print(f"Index {i} -> Value {arr[i]}")

Insertion (Add element)

• At the end → append()

• At a specific position → insert(index, value)

[Link](60) # Insert at end

[Link](2, 25) # Insert 25 at index 2

print("After insertion:", arr)

Deletion (Remove element)

• By value → remove(value)

• By index → pop(index) or del arr[index]

[Link](25) # Remove by value

[Link](3) # Remove element at index 3

print("After deletion:", arr)

Searching (Find element)

• Linear search using loop

• in operator in Python

x = 40

if x in arr:
 print(f"{x} found at index", [Link](x))

else:

print(f"{x} not found")

Updating (Modify element)

arr[1] = 200 # Update value at index 1

print("After updating:", arr)

Summary of 1-D Operations

• Traversal

• Insertion

• Deletion

• Searching

• Updating

Operations on 2-D Array (List of Lists in Python)

A 2-D array is like a matrix (rows × columns).

# 2-D array (matrix with 3 rows & 3 cols)

matrix = [

[1, 2, 3],

[4, 5, 6],

[7, 8, 9]

]
 Traversal

print("Traversal of 2-D array:")

for i in range(len(matrix)): # row

for j in range(len(matrix[i])): # column

print(matrix[i][j], end=" ")

print()

Insertion

• Insert a row → append()

• Insert at position → insert(index, row)

[Link]([10, 11, 12]) # Add a new row

matrix[1].insert(1, 99) # Insert 99 at row=1, col=1

print("After insertion:", matrix)

Deletion

• Remove row → pop(row_index)

• Remove element → pop(col_index)

[Link](3) # Delete 4th row

matrix[0].pop(2) # Delete element at row 0, col 2

print("After deletion:", matrix)

Searching

x = 99

found = False
for i in range(len(matrix)):

for j in range(len(matrix[i])):

if matrix[i][j] == x:

print(f"{x} found at position ({i},{j})")

found = True

if not found:

print(f"{x} not found")

Updating

matrix[1][1] = 555 # Update element at row=1, col=1

print("After updating:", matrix)

Summary of 2-D Operations

• Traversal → row by row

• Insertion → row/column element

• Deletion → row/column element

• Searching → locate element in matrix

• Updating → change element value

1.4 Arrays and Their Applications in Data Structure (using Python)

Introduction

Arrays are a linear data structure used to store elements of the same type in
contiguous memory locations.
They are the building blocks for many other data structures and algorithms.
Applications of Arrays

Here are some of the most common applications of arrays in data structures:

Storing and Accessing Data Sequentially

• Arrays are widely used when we need to store fixed-size sequential data.

• Example: Marks of students, temperatures of days in a week.

Python Example:

marks = [85, 90, 78, 92, 88]

print("3rd student's marks:", marks[2])

Implementing Other Data Structures

• Arrays form the basis for implementing:

o Stacks

o Queues

o Heaps

o Hash tables

• These structures use arrays internally for efficient indexing.

Example: Stack using List

stack = []

[Link](10) # Push

[Link](20)

print("Stack:", stack)

print("Pop:", [Link]()) # LIFO

Matrices (2-D Arrays)

• Arrays are used to represent matrices in mathematics.

• Operations like addition, subtraction, multiplication are done using 2-D

arrays.

Example:

A = [[1, 2], [3, 4]]

B = [[5, 6], [7, 8]]

# Matrix Addition

result = [[A[i][j] + B[i][j] for j in range(len(A[0]))] for i in range(len(A))]

print("Matrix Addition:", result)

Searching & Sorting

• Arrays are the basis for searching (Linear, Binary Search) and sorting
(Bubble, Quick, Merge Sort) algorithms.

Example: Binary Search (on sorted array)

def binary_search(arr, x):

low, high = 0, len(arr) - 1

while low <= high:

mid = (low + high) // 2

if arr[mid] == x:

return mid

elif arr[mid] < x:

low = mid + 1

else:
 high = mid - 1

return -1

arr = [10, 20, 30, 40, 50]

print("Index of 30:", binary_search(arr, 30))

Image Processing

• Images are stored as 2-D arrays of pixels (grayscale or RGB values).

• Each pixel is represented by array values.

image = [

[255, 128, 64],

[0, 128, 255],

[64, 64, 64]

print("Pixel at (1,2):", image[1][2])

Graphs & Networks

• Graphs can be represented using adjacency matrices or adjacency lists

(both use arrays).

• Example: Social network connections, road maps.

# Graph adjacency matrix

graph = [

[0, 1, 1],

[1, 0, 0],

[1, 0, 0]
]

print("Is 0 connected to 2?", graph[0][2] == 1)

Simulation & Games

• Arrays are used in game boards (e.g., Chess, Sudoku, Tic-Tac-Toe).

• Also used in simulations like traffic, weather, or physics models.

# Tic-Tac-Toe board

board = [

['X', 'O', 'X'],

[' ', 'X', ' '],

['O', ' ', 'O']

print("Center of board:", board[1][1])

Advantages of Arrays

Easy to implement
Fast access (O(1) for random access using index)
Useful for implementing other data structures

Disadvantages of Arrays

Fixed size (static in languages like C, not in Python lists)

Insertion/Deletion is costly (O(n)) since elements may need shifting
Wastes memory if declared size is larger than needed

Summary

• Arrays are fundamental data structures.

 • Applications: Storing data, implementing DS (stack, queue, heap),
matrices, searching/sorting, image processing, graphs, games.

• Arrays are simple but extremely powerful in real-world applications.

1.5 Sparse Matrices in Data Structure (using Python)

Introduction

A matrix is a 2D array of numbers arranged in rows and columns.

In many real-life applications (graphs, networks, scientific data), most matrix
elements are 0.

Such a matrix is called a Sparse Matrix.

Definition:
A sparse matrix is a matrix in which the number of zero elements is much
greater than the number of non-zero elements.
If the number of zero elements > non-zero elements, the matrix is sparse.

Why Sparse Matrices?

• A normal 2D array wastes a lot of memory when storing zeros.

• Sparse matrix techniques save memory and make operations faster.

Example

Normal Matrix (Dense)

4 x 5 Matrix:

0 0 3 0 4

0 0 5 7 0

0 0 0 0 0

0 2 6 0 0
 • Total elements = 20

• Non-zero elements = 6

• Zero elements = 14 (70% are zeros → Sparse matrix)

Representation of Sparse Matrix

Triplet Representation (Row, Column, Value)

We store only non-zero elements with their row index, column index, and
value.

For the above matrix:

Row Col Value

0 2 3

0 4 4

1 2 5

1 3 7

3 1 2

3 2 6

Dictionary of Keys (Python way)

Use a dictionary with (row, col) as key and value as element.

Example:

sparse = {

(0, 2): 3,

(0, 4): 4,

(1, 2): 5,

(1, 3): 7,
 (3, 1): 2,

(3, 2): 6

Python Implementation

1. Triplet Representation

def sparse_matrix(matrix):

rows, cols = len(matrix), len(matrix[0])

sparse = []

for i in range(rows):

for j in range(cols):

if matrix[i][j] != 0:

[Link]((i, j, matrix[i][j]))

return sparse

# Example matrix

matrix = [

[0, 0, 3, 0, 4],

[0, 0, 5, 7, 0],

[0, 0, 0, 0, 0],

[0, 2, 6, 0, 0]

print("Sparse Representation (row, col, value):")

print(sparse_matrix(matrix))

Output:

[(0, 2, 3), (0, 4, 4), (1, 2, 5), (1, 3, 7), (3, 1, 2), (3, 2, 6)]

2. Dictionary Representation

matrix = [

[0, 0, 3, 0, 4],

[0, 0, 5, 7, 0],

[0, 0, 0, 0, 0],

[0, 2, 6, 0, 0]

sparse = {}

for i in range(len(matrix)):

for j in range(len(matrix[0])):

if matrix[i][j] != 0:

sparse[(i, j)] = matrix[i][j]

print("Sparse Matrix as Dictionary:")

print(sparse)

Output:

{(0, 2): 3, (0, 4): 4, (1, 2): 5, (1, 3): 7, (3, 1): 2, (3, 2): 6}

Advantages of Sparse Matrix Representation

Saves memory (only non-zero elements stored)
Faster operations in some cases (matrix addition, multiplication)
Efficient for large datasets (like graphs, images, scientific computations)

Applications of Sparse Matrices

• Computer Graphics & Image Processing → storing pixel intensity

• Graphs & Networks → adjacency matrix representation

• Machine Learning → storing feature vectors with mostly zeros

• Optimization Problems → storing constraints with sparse data

• Search Engines → storing term-document matrices

Summary

• Sparse matrix = mostly zeros.

• Represented using Triplet form or Dictionary form in Python.

• Used to save memory and increase efficiency in large-scale problems.

1.6 String Manipulation using Arrays in Data Structure

Introduction

• A string is a sequence of characters, usually stored in contiguous

memory locations (like an array of characters).

• In C/C++, strings are implemented as character arrays.

• In Python, strings are immutable objects (cannot be changed directly),

but we can use lists (arrays of characters) for string manipulation.
Why use Arrays for String Manipulation?

• Since strings are immutable in Python, converting them into arrays (lists
of characters) allows us to:

o Modify characters

o Insert or delete characters

o Perform efficient string operations

Basic String Operations using Arrays

Traversal

s = "HELLO"

print("Traversal of string:")

for i in range(len(s)):

print(f"Character at index {i} -> {s[i]}")

Conversion: String → Array of characters

s = "HELLO"

arr = list(s) # Convert string to character array

print("Array of characters:", arr)

Updating a Character

(Since strings are immutable, convert to list first)

s = "HELLO"

arr = list(s)

arr[1] = 'A' # Replace 'E' with 'A'

s_new = "".join(arr)
print("Updated string:", s_new)

Output:

HALLO

Insertion

s = "HELLO"

arr = list(s)

[Link](2, 'X') # Insert 'X' at index 2

s_new = "".join(arr)

print("After insertion:", s_new)

Output:

HEX LLO

Deletion

s = "HELLO"

arr = list(s)

[Link](3) # Delete character at index 3 ('L')

s_new = "".join(arr)

print("After deletion:", s_new)

Output:

HELO

Searching for a Character

s = "HELLO"
arr = list(s)

x = 'L'

if x in arr:

print(f"Character '{x}' found at index", [Link](x))

else:

print(f"Character '{x}' not found")

Reversing a String

s = "HELLO"

arr = list(s)

[Link]()

s_new = "".join(arr)

print("Reversed string:", s_new)

Output:

OLLEH

Palindrome Check

def is_palindrome(s):

arr = list(s)

return arr == arr[::-1]

print(is_palindrome("MADAM")) # True

print(is_palindrome("HELLO")) # False
Applications of String Manipulation with Arrays

• Text processing → spell checkers, search engines

• Pattern matching → substring search (KMP, Rabin-Karp algorithms)

• Data compression → Huffman coding

• Cryptography → encryption & decryption

• Compiler design → tokenizing source code

Summary

• Strings are sequences of characters, like arrays.

• Since strings are immutable in Python, lists (arrays) are used for
manipulation.

• Operations include: Traversal, Update, Insert, Delete, Search,

Reverse, Palindrome check.

• Widely used in text processing, pattern matching, cryptography,

compilers.