Data Structures and Algorithms
Lecture Slides for
in C and Python
Chapter 4
Array
1
Chandan Banerjee and Atanu Das Data Structures and Algorithms in C and Python
2 Chapter Outcomes
After going through this chapter learners will be able
to explain the basic concepts of array data structures.
to analyze the advantages and disadvantages of array.
to understand the basic operations on array.
to design and implement array data structure using C and Python.
to calculate memory address in row-major and column-major order.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
3 Content
4.1 Introduction
4.2 Array Operations Using Static Memory Allocation
4.3 Array Operations Using Dynamic Memory Allocation
4.4 Slicing, Searching and Updating Array Elements
4.5 Applications of Array Using Static Memory Allocations
4.6 Applications of Array Using Dynamic Memory Allocations
4.7 Representation of 2D Arrays in Computer Memory
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
4 Introduction
There may be situations in which we need to work with a large number of similar
data values. To make such work easier, a concept is developed that is called "array".
An array is a collection of homogeneous (similar or analogous) data items stored at
contiguous memory locations. The idea is to store multiple similar items together.
This makes it easier to calculate the position of each element by simply adding an
offset or index to a base value.
The memory location of the first element of the array is called the base address or
the starting address.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
5 Introduction
Definition
An array is a collection of homogeneous data items stored at contiguous memory locations.
This collection of homogeneous data elements is stored with a single name. The array is a
linear data structure.
int a, b, c, d, e; Total 5 x 2 = 10 bytes of memory will be occupied.
int a[5]; Total 5 x 2 = 10 bytes of contiguous memory will be occupied.
ArrayName [indexValue] Suppose, a[2] = 5; a[4]=10;
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
6 Basic Operations
Sl. Name of Actions in the Operations
No. the
Operations
1. Traversing Visit or print all the array elements sequentially.
2. Insertion Insert an element at the given position. Insertion at random
position is possible.
3. Deletion Delete an element from the given position/index. Deletion at
random position is possible.
4. Searching Searches for an element using the given index or by the value.
5. Update Updates an element at the given index.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
7 Advantages
We can store multiple data items of the same type by using only a single name.
The reading element from an array is simple and efficient. Random access is
possible here. The access time of the array is O(1) in both the best and
worst cases. This is because any element can be instantly read using indices
(base address calculation) without traversing the whole array.
The array is one of the foundations of other data structures. For example,
other data structures such as linked list, stack, and queue, etc., are
implemented using the array.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
8 Disadvantages
Programmers have to declare the size of an array at the beginning of the pro-
gram. So, if we are not aware of how many elements we are going to store in
the array, it would make the task difficult.
An array is a static data structure. It means that an array is of fixed size.
The memory which is allocated to an array cannot be increased or reduced
during runtime.
The size of an array is fixed. If at some point, we need to store more
elements in it then it can’t be performed. Since an array is of fixed size, if
we allocate more memory than the requirement, the memory space will be
wasted. Similarly, if we allocate less memory than the requirement, it will also
create a problem.
The elements of an array are stored in consecutive memory locations. So,
insertions and deletions are very difficult and time-consuming if the array
size is large.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
9 Array vs. List
Array List
Array is a linear data structure where List is a dynamic data structure where
contiguous memory allocations take place. non-contiguous memory allocation takes
place.
Arrays are used to store homogeneous Lists allow storage of heterogeneous or
data elements. non-homogeneous data elements.
Array memory is static and continuous. List memory allocations are dynamic and
non-continuous.
We don’t need to keep track of next We have to keep track of the next
memory locations with arrays. location with lists.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
10 Insertion of Element in Array
Algo-4.1: Algorithm of insertion operation in an array
Step 1: TEMP = N-1, POSITION = POSITION – 1.
Step 2: Repeat Step 3 While TEMP ≥ POSITION.
Step 3: Array [TEMP + 1] = Array [TEMP]. TEMP = TEMP – 1.
Step 4: Array [POSITION] = Data.
Step 5: N = N + 1.
Step 6: Exit.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
11 Deletion of Element in Array
Algo-4.2: Algorithm of deletion operation in an array
Step 1: POSITION = POSITION – 1, TEMP = POSITION.
Step 2: Return ARRAY [POSITION].
Step 3: Repeat Step 4 while TEMP ≤ N-1.
Step 4: TEMP = TEMP + 1.
Step 5: N = N – 1.
Step 6: Exit.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
12 Array Operations Using Dynamic
Memory Allocation
When we create an array, we must specify the size at the time of the declaration itself,
and it cannot be changed during the program execution time (or run time). This is a major
problem when programmers do not know the number of values to be stored in an array
beforehand.
To solve this, the programmer can use the concept of dynamic memory allocation. The
allocation of memory during the program execution time is called dynamic memory allocation.
In C programming, the programmer can use predefined or standard library functions to
allocate memory dynamically. There are four standard library functions (which was
described in chapter one) that are defined in the header file known as "stdlib.h". These
dynamic memory functions are:
1. malloc()
2. calloc()
3. realloc()
4. free()
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
13 Applications of Array Using Static
Memory Allocations
To store a list of values: Single-dimensional arrays are used to store a list of
values of the same data type. In other words, single-dimensional arrays are used
to store a row of values in a linear form.
To perform matrix operations: Programmers can use two-dimensional arrays to
create a matrix of similar data types. We can perform various operations on
matrices using two-dimensional arrays such as matrix addition, matrix
multiplication, etc.
To implement search algorithms: We use single-dimensional arrays to implement
search algorithms such as linear search, binary search, etc.
To implement sorting algorithms: We use single-dimensional arrays to
implement sorting algorithms such as insertion sort, bubble sort, selection sort,
quick sort, merge sort, etc.
To implement data structures: Programmers can use single-dimensional arrays
to implement data structures such as stack and queue using arrays.
Arrays are also used to implement CPU scheduling algorithms.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
14 Representation of 2D Arrays in
Computer Memory
Continuous memory locations are also used to store two-dimensional (2D) arrays similar to a
1D array. The computer’s memory stores 2D arrays as rows, one following another. The first
byte’s memory address is considered as the memory location of the entire 2D array. The
compiler can easily identify the memory location of any element in the 2D array if the first
byte’s memory location and the number of columns are known.
A 2D array is treated as an array of arrays instead of just an array with two indexes. If A is
2D M x N array, it is a collection of m x n data elements. The pair of lengths (M x N) is
called the size of the array. Each element is identified by a pair of integers (J, K) called
subscripts, where 1 ≤ J ≤ M, 1 ≤ K ≤N. The pair of lengths (M x N) is called the size of the
array.
The length of a given dimension can be calculated from the formula, Length = UB − LB + 1,
where UB and LB are the lower bound and upper bound of the array.
We can find the length of the array by the following procedure for a 2D array:
First, we will find the length of the 1D row array by the formula, L1 = UB1 − LB1 + 1.
Do this again one-dimensional column array: L2 = UB2 − LB2 + 1.
Length of the array (number of elements in the 2D array): L = L1 x Data
L2. Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
15 Representation of 2D Arrays in
Computer Memory (Example)
Given an array, int A (1 : 5, 1 : 4)
1. The length of the row of the 1D array, 5 − 1 + 1 = 5.
2. The length of the column of the 1D array, 4 - 1 + 1 = 4.
3. Length of the given array = 5 x 4 = 20.
So, there are 20 elements stored in the given 2D array, A.
2D arrays can be represented in the computer’s memory using two ways. The two
most common memory layouts are row-major and column-major for multi-
dimensional arrays.
The row-major layout of a matrix puts the first row in contiguous memory, then
the second row right after it, then the third, and so on. The column-major layout
puts the first column in contiguous memory, then the second, etc. When working
with 2D arrays (matrices), row-major and column-major are easy to describe as
shown in the following slides.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
16 Row-major Order Representation of Array
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
17 Column-major Order Representation of Array
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
18 Representation of Array
Column-major order Row-major order
To find the address of LA[K] in time independent of K, the computer uses the formula:
LOC[LA[K]] = Base (LA) +W(K-1), where w is the number of words per memory cell for the
array LA, and 1 is the lower bound of the index set of LA.
A similar situation also holds for any 2D M x N array A. For a 2D M x N array A, the computer
keeps track of base [A] and the address of the first element A[1, 1] of A. The computer
computes the address LOC(A[J, KJ) of A[J, K] using the formula given below:
Column major order
LOC (A[J, K]) = Base(A) + w [M (K − 1) + (J − 1)]
Row major order
LOC (A[J, K]) = Base (A) + w[N (J − 1) + (K − 1)]
It may be noted that the formula is linear in J and K, and one can find the address LOC(A[J, K])
in time independent of J and K.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
19 Representation of Array (Example)
Consider a 20 x 4 matrix array A. Suppose, base(A) = 2000, and there are
w = 4 words per memory cell. Calculate 2D array locations using row-major
order and column-major order. Assume that the array index starts from 0 (i.e.
, A[0, 0] is the first location) as we found in C programming.
The address of A[12, 3] in row-major order as follows:
Using the formula: LOC(A[J, K]) = Base (A) + w [N (J) + (K)]
LOC(A[12, 3]) = 2000 + 4 [4(12 ) + (3)] = 2000 + 4 [51] = 2000 + 204 = 2204.
The address of ARRAY [12, 3] in column-major order as follows:
Using the formula: LOC(A[J, K]) = Base(A) + w(M(K) + (J)]
LOC(A[12, 3]) = 2000 + 4 [20(12) + (3)] = 2000 + 4 [243] = 2000 + 972 =
2972.
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
20 List of C Programs
Examples
• Accessing the elements of an array
• Finding the length of an array
• Looping of array elements
• Slicing of an array
CProg-4.1: Inserting an element into an array using static memory allocation
CProg-4.2: Deleting an element from an array using static memory allocation
CProg-4.3: Inserting an element into an array using dynamic memory allocation
CProg-4.4: Deleting an element into an array using dynamic memory allocation
CProg-4.5: Adding two matrices using static memory allocation
CProg-4.6: Multiplying two matrices using static memory allocation
CProg-4.7: Adding two matrices using dynamic memory allocation
CProg-4.8: Multiplying two matrices using dynamic memory allocation
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
21 List of Python Programs
Examples
▪ Accessing the elements of an array
▪ Finding the length of an array
▪ Looping of array elements
▪ Slicing array between index 1 and index 4
▪ Slicing array elements from index 4 to the end
▪ Slicing 2-D Arrays
▪ Searching for an element in an array
▪ Updating array with assignment operator and array module
▪ Updating array using append() method
▪ Slicing array elements from the beginning to index 3
▪ Updating array using extend() method to add multiple items
PyProg-4.1: Inserting an element into an array
PyProg-4.2: Deleting an element from an array
PyProg-4.3: Adding two matrices
PyProg-4.4: Multiplying two matrices
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das
22
END
Data Structures and Algorithms in C and Python
Chandan Banerjee and Atanu Das