DSA Notes

C
DSA
Software Engineering
Software Architecture
Operating System
Big Data
Data Mining and Warehousing
TOC
Ada
CPP
DBMS

All Topics (20)

  • 1. Data Structure
  • 2. Objectives of Data Structure
  • 3. types of data structures
  • 4. Operations on Data Structure
  • 5. Array
  • 6. Types of Arrays
  • 7. Memory Representation of Array
  • 8. Address Calculation in One-Dimensional Array
  • 9. What is a Two-Dimensional Array? (With Simple Explanation & Example)
  • 10. Representation of 2D Array in Memory (Row Major & Column Major Order)
  • 11. Address Calculation in 2D Array (Row Major Order)
  • 12. Basic Operations in Array (Traversal, Insertion, Deletion)
  • 13. Sparse Matrix
  • 14. Why Use Sparse Matrix Instead of Simple Matrix?
  • 15. Advantages & Disadvantages of Array.
  • 16. Linked List
  • 17. Difference Between Array and Linked List.
  • 18. Types of Linked List
  • 19. Operations on Linked List
  • 20. Dynamic Memory Allocation (DMA) vs Array vs Linked List

11. Address Calculation in 2D Array (Row Major Order)

When a 2D array is stored in memory, it occupies continuous memory locations.
To find the exact memory location of any element, we use a formula.

 General Formula (Row Major Order)

For an array:

A [ R ] [ C ]

 The address of element A[i][j] is:

Loc ( A [ i ] [ j ] ) = Base Address + Size × [ C × ( i − Lr ) + ( j − Lc ) ]

 Meaning of Terms

  • Base Address (BA) → Starting address of array
  • Size → Size of each element (e.g., float = 4 bytes)
  • C → Total number of columns
  • i → Row index of element
  • j → Column index of element
  • Lr → Lower bound of row index
  • Lc → Lower bound of column index

 Important Notes

 In most languages (C/C++), indexing starts from 0
 So:

  • Lr = 0
  • Lc = 0

 Total columns:

C = Uc − Lc + 1

 Total rows:

R = Ur − Lr + 1

 Solved Example (Step-by-Step)

 Question

Find the address of B[6][8]
Given:

  • Array: B[11][13]
  • Base Address = 1000
  • Type = float (size = 4 bytes)
  • Storage = Row Major Order

 Step 1: Identify Values

  • i = 6
  • j = 8
  • BA = 1000
  • Size = 4 bytes
  • Rows (R) = 11
  • Columns (C) = 13

Since indexing starts from 0:

  • Lr = 0
  • Lc = 0

 Step 2: Apply Formula

Loc( B [ 6 ] [ 8 ] ) = 1000 + 4 × [13 × (6 − 0) + (8 − 0)]

 Step 3: Solve Inside Bracket

= 1000 + 4 × [13 × 6 + 8]
= 1000 + 4 × [78 + 8]
= 1000 + 4 × 86

 Step 4: Final Calculation

= 1000 + 344
= 1344

 Final Answer

Address of B [ 6 ] [ 8 ] = 1344

12. Basic Operations in Array (Traversal, Insertion, Deletion)

Arrays support three main basic operations:

1. Traversal
2. Insertion
3. Deletion

 1. Traversing a Linear Array

 Definition

Traversing means accessing each element of an array exactly once to perform some operation like printing, searching, or counting.

 Example Array

A = [5, 7, 2, 4]
Index: 0 1 2 3
  • Lower Bound (LB) = 0
  • Upper Bound (UB) = 3

 Algorithm (Traversal)

Procedure Traverse(A, LB, UB)
Step 1: Set K = LB
Step 2: Repeat while (K ≤ UB)
           Print A[K]
           K = K + 1
Step 3: Exi

 Working

K = 0 → print 5
K = 1 → print 7
K = 2 → print 2
K = 3 → print 4
K = 4 → stop

 2. Insertion in Array

 Definition

Insertion means adding a new element at a specific position in the array.

 Important Condition

 Before insertion, check Overflow:

If (n + 1 > size) → Overflow

 Types of Insertion

  • At beginning
  • At middle
  • At end (easy)

 Example

A = [A, B, C, D]
Insert X at position 2

After shifting:

A = [A, B, X, C, D]
 

 Algorithm (Insertion)

Procedure Insert(A, n, size, loc, item)

Step 1: If (n + 1 > size)
             Print "Overflow"
                     Exit
Step 2:  For K = n−1 down to loc
             A[K+1] = A[K]
Step 3: A[loc] = item
Step 4: n = n + 1
Step 5: Exit
 

 Key Point

 Elements are shifted right side to create space.

 3. Deletion in Array

 Definition

Deletion means removing an element from a specific position in the array.

 Important Condition

 Before deletion, check Underflow:

If (n == 0) → Underflow

 Example

A = [A, B, C, D]
Delete element at position 1

 After shifting:

A = [A, C, D]
 

 Algorithm (Deletion)

Procedure Delete(A, n, loc)

Step 1: If (n == 0)
             Print "Underflow"
               Exit
Step 2: Data = A[loc]
Step 3: For K = loc to n−2
              A[K] = A[K+1]
Step 4: n = n − 1
Step 5: Print "Deleted element =", Data
Step 6: Exit

 Key Point

 Elements are shifted left side after deletion. 

so, 

Traversal accesses all elements, insertion adds a new element by shifting elements right, and deletion removes an element by shifting elements left.

13. Sparse Matrix

A Sparse Matrix is a matrix in which most of the elements are zero and only a few elements are non-zero.

 If number of zero elements >> non-zero elements → Sparse Matrix

 Example

  0   0   5   0
  0   0   0   0
  3   0   0   0
  0   0   0   7

 Uses

  • Scientific applications
  • Engineering computations
  • Graph algorithms
  • Large data processing

 Advantages

  • Saves memory
  • Faster computation
  • Efficient storage

 Types of Sparse Matrix

1️⃣ Triangular Matrix

 Definition

A Triangular Matrix is a square matrix in which elements are zero either above or below the main diagonal.

 (a) Lower Triangular Matrix

 All elements above diagonal = 0

Example:

  2   0   0   0
  3   4   0   0
  5   6   7   0
  8   9   1   2

 (b) Upper Triangular Matrix

 All elements below diagonal = 0

Example:

  2   3   4   5
  0   6   7   8
  0   0   9   3
  0   0   0   1

2️⃣ Tridiagonal Matrix

 Definition

A Tridiagonal Matrix is a square matrix in which non-zero elements are present only:

  • On the main diagonal
  • Just above the diagonal
  • Just below the diagonal

 Example

  2   1   0   0
  1   3   2   0
  0   2   4   2
  0   0   1   5
 

14. Why Use Sparse Matrix Instead of Simple Matrix?

🔹 Reason

1️⃣ Storage Efficiency

In a sparse matrix:

  • Number of zero elements is very high
  • Number of non-zero elements is very less

 Storing all elements (including zeros) in a normal matrix wastes memory.

 So, we store only non-zero elements to save memory.

2️⃣ Less Memory Usage

 In simple matrix:

  • Memory is used for all elements (zero + non-zero)

 In sparse matrix:

  • Memory is used only for non-zero elements

 Hence, memory is saved

3️⃣ Faster Computation

 While performing operations:

  • We process only non-zero elements
  • Zero elements are ignored

 This reduces computation time

4️⃣ Avoid Wastage

 Zero values have no contribution in calculations
 Storing them is unnecessary

 Sparse matrix avoids storing useless zeros

 Sparse Matrix Representation

Sparse matrix can be represented in different ways:

a). Array Representation (Triplet Method)

b). Linked List Representation

 A) Array Representation (Triplet Form)

 In this method, we store only non-zero elements in a 2D array.

Each row stores 3 values:

 
(Row, Column, Value)
 

 Structure of Triplet Array

Row Column Value
i j A[i][j]

 Example Matrix

0 0 3
0 4 0
2 0 0
 

 Triplet Representation

Row Column Value
0 2 3
1 1 4
2 0 2

 Only non-zero elements are stored ✔

 Important Point (Exam Tip)

Sometimes first row stores:

(total rows, total columns, total non-zero elements)

Example:

Row Column Value
3 3 3
0 2 3
1 1 4
2 0 2

 B) Linked List Representation

 Each non-zero element is stored as a node:

(Row, Column, Value, Next Pointer)

 Nodes are connected using pointers
 Saves even more memory dynamically

15. Advantages & Disadvantages of Array.

 Advantages of Array

a) Easy Storage of Same Data Type

 Array is a convenient way to store multiple values of same type (like int, float) in a single structure.

b) Fixed Size (Known in Advance)

 We can store a known number of elements in an array.
 Useful when size is already defined.

c) Supports Multidimensional Data

 Arrays can be:

  • 1D (single list)
  • 2D (matrix)
  • Multi-dimensional

 Useful for matrix and table representation.

d) Fast Access (Random Access)

 Elements can be accessed using index number.
 Access time is very fast (O(1)).

e) Memory is Contiguous

 Elements are stored in continuous memory locations
 Improves performance

 Disadvantages of Array

a) Fixed Size (Static Nature)

 Size must be declared at compile time.
 Cannot increase or decrease later.

b) Memory Wastage

 If allocated size is more than required → memory is wasted
 If size is less than required → overflow problem

c) Insertion is Costly

 To insert an element:

  • Elements need to be shifted

 Takes more time

d) Deletion is Costly

 Deleting an element also requires shifting elements

 Inefficient operation

e) Stores Only Fixed Elements

 Cannot dynamically add/remove elements
 Not flexible

Page 3 of 4