Representation of Array
The representation of an array can be defined by its declaration. A declaration means allocating
memory for an array of a given size.
Arra
y
Arrays can be declared in various ways in different languages. For better illustration, below are
some language-specific array declarations.
int arr[5]; // This array will store integer type element
char arr[10]; // This array will store char type element
float arr[20]; // This array will store float type element
However, the above declaration is static or compile-time memory allocation, which means that
the array element's memory is allocated when a program is compiled.
Here only a fixed size (i,e. the size that is mentioned in square brackets []) of memory will be
allocated for storage, but don't you think it will not be the same situation as we know the size of
the array every time, there might be a case where we don't know the size of the array. If we
declare a larger size and store a lesser number of elements will result in a waste of memory or
either be a case where we declare a lesser size then we won't get enough memory to store the rest
of the elements. In such cases, static memory allocation is not preferred.
Applications, Advantages and Disadvantages of Array
Array is a linear data structure that is a collection of data elements of same types. Arrays are
stored in contiguous memory locations. It is a static data structure with a fixed size.
pplications of Array Data Structure:
Arrays mainly have advantages like random access and cache friendliness over other data
structures that make them useful.
Below are some applications of arrays.
Storing and accessing data: Arrays store elements in a specific order and allow
constant-time O(1) access to any element.
Searching: If data in array is sorted, we can search an item in O(log n) time. We can also
find floor(), ceiling(), kth smallest, kth largest, etc efficiently.
Matrices: Two-dimensional arrays are used for matrices in computations like graph
algorithms and image processing.
Implementing other data structures: Arrays are used as the underlying data structure
for implementing stacks and queues.
Dynamic programming: Dynamic programming algorithms often use arrays to store
intermediate results of subproblems in order to solve a larger problem.
Data Buffers: Arrays serve as data buffers and queues, temporarily storing incoming
data like network packets, file streams, and database results before processing.
Advantages of Array Data Structure:
Efficient and Fast Access: Arrays allow direct and efficient access to any element in the
collection with constant access time, as the data is stored in contiguous memory
locations.
Memory Efficiency: Arrays store elements in contiguous memory, allowing efficient
allocation in a single block and does not require extra storage for linking different blocks.
Versatility: Arrays can be used to store a wide range of data types, including integers,
floating-point numbers, characters, and even complex data structures such as objects and
pointers.
Compatibility with hardware: The array data structure is compatible with most
hardware architectures, making it a versatile tool for programming in a wide range of
environments.
Disadvantages of Array Data Structure:
Fixed Size: Arrays have a fixed size set at creation. Expanding an array requires creating
a new one and copying elements, which is time-consuming and memory-intensive. Even
dynamic sized arrays internally use fixed sized memory allocation and de-allocation.
Memory Allocation Issues: Allocating large arrays can cause memory exhaustion,
leading to crashes, especially on systems with limited resources.
Insertion and Deletion Challenges: Adding or removing elements requires shifting
subsequent elements, making these operations inefficient.
Sparse Matrix and its representations
A matrix is a two-dimensional data object made of m rows and n columns, therefore having total
m x n values. If most of the elements of the matrix have 0 value, then it is called a sparse matrix.
Why to use Sparse Matrix instead of simple matrix ?
Storage: There are lesser non-zero elements than zeros and thus lesser memory can be
used to store only those elements.
Computing time: Computing time can be saved by logically designing a data structure
traversing only non-zero elements..
Example:
00304
00570
00000
02600
Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in the
matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero elements,
we only store non-zero elements. This means storing non-zero elements with triples- (Row,
Column, value).
Sparse Matrix Representations can be done in many ways following are two common
representations:
1. Array representation
2. Linked list representation
Method 1: Using Arrays:
2D array is used to represent a sparse matrix in which there are three rows named as
Row: Index of row, where non-zero element is located
Column: Index of column, where non-zero element is located
Value: Value of the non zero element located at index - (row,column)
Implementation:
// C++ program for Sparse Matrix Representation
// using Array
#include <iostream>
using namespace std;
int main()
{
// Assume 4x5 sparse matrix
int sparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};
int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;
// number of columns in compactMatrix (size) must be
// equal to number of non - zero elements in
// sparseMatrix
int compactMatrix[3][size];
// Making of new matrix
int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}
for (int i=0; i<3; i++)
{
for (int j=0; j<size; j++)
cout <<" "<< compactMatrix[i][j];
cout <<"\n";
}
return 0;
}
// this code is contributed by shivanisinghss2110
Output
001133
242312
345726
Time Complexity: O(NM), where N is the number of rows in the sparse matrix, and M is the
number of columns in the sparse matrix.
Auxiliary Space: O(NM), where N is the number of rows in the sparse matrix, and M is the
number of columns in the sparse matrix.
Method 2: Using Linked Lists
In linked list, each node has four fields. These four fields are defined as:
Row: Index of row, where non-zero element is located
Column: Index of column, where non-zero element is located
Value: Value of the non zero element located at index - (row,column)
Next node: Address of the next node
Time Complexity: O(N*M), where N is the number of rows in the sparse matrix, and M is the
number of columns in the sparse matrix.
Auxiliary Space: O(K), where K is the number of non-zero elements in the array.
Other representations:
As a Dictionary where row and column numbers are used as keys and values are matrix entries.
This method saves space but sequential access of items is costly.
As a list of list. The idea is to make a list of rows and every item of list contains values. We can
keep list items sorted by column numbers.