2.

1 Introduction

Array is the most basic data structure used in computer science. It is particularly
useful when the size of data items is small in size. All operations of data structure
are possible on array. Array can be linear in dimension or multi dimensional.
Pointer can be used to point to any location within the array. It is also possible to
create array of pointers. In this lesson you will see the algorithms for basic
operations on array and how linear and 2-D arrays are represented in memory.

2.2 Definition of Linear array

A linear array is collection of homogeneous finite number of data elements that

are stored contiguously in memory. The elements in an array are accessed using
an index number.

Size represents the size of the array, i.e. the total number of elements that can
be stored in an array. The smallest index number of an array is referenced by LB
called lower bound and the largest index number of an array is referenced by UB
called upper bound.

size = UB - LB + 1

The value of LB can also be negative. It is not mandatory for the first element to
be stored at index 1 always.

For example,
If LB = -4 and UB = 7, then size = UB - LB + 1; size = 7 - (-4) + 1; size = 7+4+1 =
12

Index Value

-2 12

-1 11

0 56

1 7

3
 4

Table 2.1

In the last table, the LB of the array is -2 and UB is 4. Hence the size of the array
is 4 - (-2) + 1 = 7.
But there are only 4 elements in the array which is 3 less than the size of the
array. The index number of the last element in an array at any given moment of
time is denoted by N.

Application of arrays

Arrays are particularly useful in following areas:

1. Creating a large number of data elements with single identifier and storing
them contiguously in memory.

2. Particularly useful for representing in memory data structures like stacks,

queues, trees and graphs.

3. Easy and effective data structure for implementing operations like sorting,
searching and merging.

2.3 Memory representation of linear array

Elements of the array are stored contiguously in memory. It makes it rather easy
to access each element of the array knowing that the two consecutive elements
are stored in two contiguous memory blocks. The address where the first
element of the array is stored is called base address of the array and is denoted
as base(AARAY_NAME).

The first element of the array can be accessed using base(a), where a is the
name of any array. We can access the memory location of kth element of the
linear array using the following formulae:

loc (a[k]) = base (a) + w ( k - LB)

where,
a is the name of any array

k is the index number of the array element whose location is to be accessed

base(a) refers to the base address of the array a.

w refers to the word size or bytes per storage location for each element of the
array. The value of w depends on the type of the array. For an array of integer
elements, the value of w is 2. For a float array, the value of w is 4 and for char is
it 1. In other words w represents the amount of memory taken by each element of
an array of a specified data type.

Index Value Memory

location
-2 12 100

-1 11 102

0 56 104

1 106

2 26 108

3 54 110

4 11 112

Table 2.2

Let us consider an integer array (a) as shown in the last table. The base address
base (a) is 100 as the first element of the array is stored at memory location 100.
The next element is stored at location 102 which means that the value of w is 2.
Let us suppose we want to know the location of element k = 2;

loc (a[k]) = base (a) + w ( k - LB)

loc (a[2]) = 100 + 2 ( 2 - (-2))

= 100 + 2 ( 4) = 100 + 8 =108

As you can see in the figure as well, the element with index 2 is stored at
memory location 108.
2.4 Basic operations on array

2.4.1 Traversing a Linear array

Traversing refers to visiting each element of an array exactly once and applying
any specified process to each element.

ALGORITHM TRAVERSE_ALL (TRAVERSING AN ARRAY) Apply PROCESS

operation to the array(ARR) with lower bound LB and upper bound UB. It is
assumed that the array is full.

1. Repeat For I = LB to UB

2. Apply PROCESS to ARR[I] ARR[I] = ARR[I] + 5

[End of For Loop]

3. Exit

INPUT N
FOR I = 0 TO N-1
PRINT I+1 N-I
 ALGORITHM TRAVERSE_N (TRAVERSING AN ARRAY) Apply PROCESS operation
to the array(ARR) with lower bound LB and upper bound UB. It is assumed that the
array is NOT full and N points to the index number of last element in the array.

1. I = LB

2. Repeat while I <= N

3. Apply PROCESS to ARR[I]

4. I = I + 1

[End of while Loop]

4. Exit

2.4.2 Inserting in Linear array

Second basic operation is to insert an element at given location in an array.

ALGORITHM INSERT (INSERTING IN AN ARRAY) insert ITEM at a given location K

in the array(ARR) with lower bound LB and upper bound UB. N is the index of the
last element in the array.

1. Set I = N [Last element in the array]

2. Repeat While (I >= K)

3. Set ARR[I+1] = ARR[I] [Move elements to next index position]

4. Set I = I – 1 [Decrement I by 1]

[End of While Loop]

5. Set ARR[K] = ITEM [Insert ITEM at location K]

6. Set 4 [Increment the value of N by 1]

7. Exit
For example, consider the following array:

2.4.3 Deleting from Linear array

Third operation given in this section is to delete an element at given

location from an array.
 ALGORITHM DELETE (DELETING FROM AN ARRAY) deletes an element at a given
location K in the array(ARR) with lower bound LB and upper bound UB and stores
it in ITEM. N is the index of the last element in the array.

1. Set ITEM = ARR[K] [Assign the element to be deleted at location K to ITEM]

2. Repeat For I = K to N - 1

3. Set ARR[I] = ARR[I+1] [Move the elements one position to the left]

[End of For Loop]

4. Set N = N – 1 [Decrement the value of N by 1]

5. Exit

For example, consider the following array:

Let LB= 1, UB =10

There are 6 elements in the array which means N= 6

Let us suppose the location K from where the element is to be delete is 4

According to the algorithm, I is initialized with 4 (i.e. K) and in the first iteration
the element at index 5 is shifted to index 4.

In iteration no. 2, the value of I which was incremented to 5 in first iteration

results in shifting the element at index 6 to index position 5.
In the last step of the algorithm, the value of N is decremented by 1 to make it 5
and hence makes the element at position 6 irrelevant. The final array looks like
this,

2.5 2-D array

2-D array is a logical representation of array elements in the matrix form. The
computer memory is single dimensional or linear. The logical and physical
mapping of linear array is same, but there are points to consider in the logical
and physical mapping of 2-D arrays. Logical representation is how the user views
the data elements and physical representation is how the elements are actually
stored in memory. The physical representation of 2-D array is discussed in the
next section.

Like in linear array, the elements in 2-D array can be accessed using two index
values. One represents the row number and the other represents the column
number of the element to be accessed.

Figure 2.1
The figure above shows the logical representation of 2-D array. The element are
stored in the form of matrix. Each element is indexed using two subscript values.

2.6 Memory representation of 2-D array

2-D array can be represented in memory using either of the two techniques:

 Row-Major Order
 Column-Major Order.

Row-Major Order- As already stated in the previous section, the computer

memory is linear. Hence, the 2-D array is also physically stored in memory
linearly. In case the row-major order is followed, the entire first row is stored in
memory allocated to 2-D array and then followed by 2nd row and so on.
Consider the following logical representation of 2-D array:

Figure 2.2

The same is represented in memory using row-major order as follows:

[1, 1] [1, 2] [1, 3] [2, 1] [2, 2] [2, 3] [3, 1] [3, 2] [3, 3]

Column-Major Order- In case the column-major order is followed, the entire first
column is stored in memory allocated to 2-D array and then followed by 2nd
column and so on.
The same matrix or 2-D array is represented in memory using column-major
order as follows

[1, 1] [2, 1] [3, 1] [1, 2] [2, 2] [3, 2] [1, 3] [2, 3] [3, 3]

The address where the first element of the 2-D array is stored is also called base
address of the array and is denoted as base(AARAY_NAME).
The first element of the array can be accessed using base(a), where a is the
name of any array and is always the element with row and column index value of
1 no matter which order of memory representation you follow. We can access the
memory location of [ I, j ] element of the 2-D array as follows:

Row-Major Order

loc (a[ I, J ]) = base (a) + w [ n ( I -1 ) + ( J -1 ) ]

where,
a is the name of any 2-D array

I and J are the index number's of the array element whose location is to be
accessed

base(a) refers to the base address of the array a.

w refers to the word size or bytes per storage location for each element of the
array. The value of w depends on the type of the array.

n is the number of columns in the 2-D array

Consider the following 2-D array

14 56 11

29 69 89

Table 2.3 (a)

Index Value Memory

location
[1, 1] 14 100

[1, 2] 56 102

[1, 3] 11 104

[2, 1] 29 106
 [2, 2] 69 108

[2, 3] 89 110

Table 2.3 (b)

Let us consider a 2-D integer array (a) as shown in the tables above. Value of w
is 2 and base (a) is 100. Let us suppose we want to know the location of element
a[ 1, 3];
loc (a[ I, J ]) = base (a) + w [ n ( I -1 ) + ( J -1 ) ]

loc (a[1, 3]) = 100 + 2 ( 3 (1-1) + (3-1))

= 100 + 2 ( 2) = 100 + 4 =104

As you can see in the figure as well, the element with index [1,3] is stored at
memory location 104.

Column-Major Order

loc (a[ I, J ]) = base (a) + w [ m ( J -1 ) + ( I -1 ) ]

where,

a is the name of any 2-D array

I and J are the index number's of the array element whose location is to be
accessed

base(a) refers to the base address of the array a.

w refers to the word size or bytes per storage location for each element of the
array. The value of w depends on the type of the array.

m is the number of rows in the 2-D array

Index Value Memory

location
[1, 1] 14 100

[2, 1] 29 102
 [1, 2] 56 104

[2, 2] 69 106

[1, 3] 11 108

[2, 3] 89 110

Table 2.4

Let us suppose we want to know the location of element a[ 1, 3];

loc (a[ I, J ]) = base (a) + w [ m ( J -1 ) + ( I -1 ) ]

loc (a[1, 3]) = 100 + 2 ( 2 (3-1) + (1-1))

= 100 + 2 ( 4) = 100 + 8 =108

As you can see in the figure as well, the element with index [1,3] is stored at
memory location 108.

2.7 Pointer

Pointer is used to store the base address of a memory reference or block. It can
be used to store the address of any element or node of a given data structure.
For example, base is a pointer that points to the base address of the array.
Pointer can be of any basic data type and is from derived data type class.

Pointers are particularly useful in traversing the data structure. The concept of
linked list data structure is not possible without pointers. The link between two
nodes of the linked list is maintained with the help of the pointer. The address of
the next node in the list is stored in the link part of the first node.

2.8 Pointer arithmetic and arrays in terms of pointers

It is possible to perform basic arithmetic operations like addition and subtraction

on pointer type. As already stated, pointer is used to point to some memory
location. Performing simple add operation on pointer, makes it point to the block
N blocks ahead of the current block it is pointing to and performing simple
subtract operation on pointer, makes it point to the block N blocks before of the
current block it is pointing to.

For example, consider the following array

 Index Value Memory
location
-2 12 100

-1 11 102

0 56 104

1 7 106

2 26 108

3 54 110

4 11 112

Table 2.5

Let us suppose, pointer PTR is pointing to the array element with index 0 whose
address is 104.
Adding 2 to the value of pointer as follows:

PTR = PTR + 2

Makes it point to the element with index no. 2 and new value of PTR is 108. The
value addition to the pointer is as follows;

PTR = PTR + 2 is interpreted as;

PTR= PTR + 2(w);

where w is the size of the word or memory block which is two in this case as the
array is of integer type
and integer takes 2 bytes in memory.

PTR= 104 + 2(2) = 104 + 4 = 8

It is possible to store the base address of an array in any pointer and then access
each element of the array using the concept of pointer addition.

2.9 Array of pointers

Array can also be created for pointer type. Type of pointer is eventually the type
of pointer array. Array of pointer is used to store a series of addresses in it. 2-D
array is a good example of array of pointers.

In case of row-major order memory management, the row number for each row
in the 2-D matrix points to the base address of that row alone in programming
and in case of column-major order memory management, the column number for
each column in the 2-D matrix points to the base address of that column alone.

It is mainly a programming concept.

2.10 Static and dynamic memory

Depending on whether the data structure in use in array or linked list, the
memory allocated to the data structure can either be static or dynamic. Array is a
fixed size data structure. Its size cannot be changed according to the
requirement. Also the size of the array to be created is pre-decided.

Hence the array uses the concept of static memory management whereby the
memory is of fixed size and is allocated to the data structure when the program is
compiled. Program is a sequence of instructions written in any programming
language for the given algorithm.
Linked list is flexible in size. It starts with no nodes and depending upon the
requirement, new nodes can be added to the linked list and also removed from
the linked list. The decision of adding nodes to the linked list can be taken when
the program is in execution.

The linked list follows the concept of dynamic memory management whereby
memory to its nodes can be allocated or de-allocated at any time. It is more
useful then the static memory management technique as it reduces the chances
of memory wastage.