Array in Data Structures
• Definition of Array
An array is a collection of elements stored in contiguous memory locations and accessible using a single
name. Each element in the array is accessed using its index.
Key Characteristics of Arrays
- Homogeneous: All elements are of the same data type.
- Fixed Size: Size is defined at the time of declaration and cannot change during execution.
- Random Access: Any element can be accessed directly using its index in constant time (O(1)).
Properties of Arrays
1. Contiguous Memory Allocation: All elements are stored one after another in memory.
2. Indexing: Array indices start from 0 up to (size - 1).
3. Efficient Read: Direct access to any element.
4. Static Structure: Size is fixed once declared (for static arrays).
5. Memory Efficiency: No overhead like pointers in linked lists.
Types of Arrays
1. One-Dimensional Array: A linear list of elements.
- Example: int A[5]; — holds 5 integers.
2. Two-Dimensional Array: Represents matrices or tables.
- Example: int B[3][4]; — 3 rows, 4 columns.
3. Multi-Dimensional Array: Arrays with more than two dimensions.
- Example: int C[2][3][4];
4. Character Arrays: Used for strings, e.g., char name[20];
5. Dynamic Arrays: Size can be allocated at runtime using pointers and memory management.
Implementation Using C++ Classes
• In object-oriented programming, arrays can be encapsulated inside a class to allow for data hiding and
modular design.
Why Use Classes for Arrays?
- To implement bounds checking
- To add custom behavior (e.g., auto-resizing)
- To group array operations together
- To maintain encapsulation and abstraction
Class-Based Array Concepts
- Private members: Internal array, size
- Constructor: Allocates memory
- Destructor: Deallocates memory
- Member functions: Functions for array operations (like insert, delete, etc.)
Operations on Arrays
Traversing an Array
- The process of accessing and visiting each element exactly once in order.
- Used for reading or displaying all elements.
Insertion in an Array
- Adding a new element at a specific position.
- May involve shifting elements to the right.
- Time complexity depends on the position:
- Best Case (end): O(1)
- Worst Case (start/middle): O(n)
Deletion in an Array
- Removing an element from a specified index.
- Requires shifting elements to the left to fill the gap.
- Time complexity also depends on the position:
- Best Case (end): O(1)
- Worst Case (start/middle): O(n)
Traversing An Array
• Algorithm 1: (Traversing a Linear Array) Here LA Is a
linear array with the lower bound LB and upper bond
UB
• This algorithm traverses LA Applying an operation
PROCESS to each element of LA.
1. [Initialize counter.] Set K := LB.
2. Repeat Steps 3 and 4 while K <= UB.
3. [Visit element.] Apply PROCESS to LA[K].
4. [Increase counter.] Set K := K + 1.
[End of Step 2 loop.]
5. Exit.
Insertion In An Array
• Algorithm 2: (Inserting into a linear array) Insert (LA, N, K, ITEM)
• Here LA is a linear array with N elements and K is a positive integer such
that k <= n. This algorithm inserts an element ITEM into the kth position
in LA.
1. [Initialize counter] Set J := N.
2. Repeat steps 3 and 4 while J <= K.
3. [Move Jth element downward.] Set LA[J+1] = LA[J].
4. [Decrease counter.] Set J := J — 1.
[End of Step 2 loop.]
5. [Insert element.] Set LA[K] := ITEM.
6. [Reset N.] Set N := N+ 1.
7. Exit.
Deletion In An Array
The following algorithm deletes the Kth element from a linear array
LA and assigns it to a variable ITEM.
• Algorithm 3: (Deleting from a Linear Array) DELETE(LA, N, K, ITEM)
• Here LA is a linear array with N elements and K is a positive integer
such that
K <= N. This algorithm deletes the Kth element from LA.
1. Set ITEM := LA[K].
2. Repeat for J = K to N-1:
[Move J + 1st element upward.] Set LA[J] := LA[J + 1].
[End of loop.]
3. [Reset the number N of elements in LA.] Set N: = N - 1.
4. Exit.
Memory Representation and Address
Calculation of 1D Arrays
• A one-dimensional array is stored in contiguous memory locations, and the elements are indexed starting from 0.
Example:
int A[5] = {10, 20, 30, 40, 50};
Assume base address A[0] is 1000, and int is 4 bytes.
| Element | Address |
|---------|-----------|
| A[0] | 1000 |
| A[1] | 1004 |
| A[2] | 1008 |
| A[3] | 1012 |
| A[4] | 1016 |
Address Calculation Formula:
Address of A[i] = B + (i - L) × W
Where:
- B = Base address
- i = Index
- L = Lower bound
- W = Size of each element in bytes
Memory Representation and Address
Calculation of 2D Arrays
• Two-dimensional arrays are stored in row-major or column-major order.
C++ uses row-major order.
Example:
int B[2][3] = { {10, 20, 30}, {40, 50, 60} };
Memory order:
B[0][0], B[0][1], B[0][2], B[1][0], B[1][1], B[1][2]
Assume base address = 2000, int = 4 bytes
| Element | Address |
|------------|-----------|
| B[0][0] | 2000 |
| B[0][1] | 2004 |
| B[0][2] | 2008 |
| B[1][0] | 2012 |
| B[1][1] | 2016 |
| B[1][2] | 2020 |
Cont….
Cont….
Cont….
• Row Major System:
The address of a location in Row Major System is calculated using the following
formula:
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
• Where,
• B = Base address
• I = Row subscript of element whose address is to be found
• J = Column subscript of element whose address is to be found
• W = Storage Size of one element stored in the array (in byte)
• Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
• Lc = Lower limit of column/start column index of matrix, if not given assume 0
(zero)
• N = Number of column of the given matrix
Cont….
• Column Major System:
The address of a location in Column Major System is calculated using the following
formula:
Address of A [ I ][ J ] Column Major Wise = B + W * [( I – Lr ) + M * ( J – Lc )]
• Where,
• B = Base address
• I = Row subscript of element whose address is to be found
• J = Column subscript of element whose address is to be found
• W = Storage Size of one element stored in the array (in byte)
• Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
• Lc = Lower limit of column/start column index of matrix, if not given assume 0 (zero)
• M = Number of row of the given matrix
Introduction to Sparse Arrays
• What is a Sparse Array?
A sparse array is a type of array in which most of the elements are zero (or default).
Why Use Sparse Arrays?
– Saves memory when arrays have a large number of zero entries.
– Improves performance by storing only non-zero elements.
– Useful in scientific computing, matrices, graphs, etc.
Representation:
Instead of all elements, store non-zero elements with row/column indices.
Example:
|0|0|5|
|0|0|0|
|0|8|0|
Sparse representation (triplet form):
| Row | Column | Value |
|-------|-------------|--------|
|0 |2 |5 |
|2 |1 |8 |
Advantages:
- Memory efficient
- Faster operations on meaningful data (non-zero data)
