CS_GATE@PRITESH_SAKLECHA 1

Array
• Array: An array is collection of similar items stored at contiguous memory
locations.

A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]

• Types of Array :
• One dimensional array
• Two dimensional array
• Declaration of 1-D array
int A[10];

No of elements in an array = (upper bound – lower bound +1 )

CS_GATE@PRITESH_SAKLECHA 2
• Address calculation of index in one dimensional
array:

• A[L…….U]
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]

• A[i] = B + W* (i-L)
• Here B = Base address
• W = size of element
• L = lower bound
• i= index

CS_GATE@PRITESH_SAKLECHA 3
• A is an array [-7,7] of elements. The starting
location is 100. each element occupies 2 byte of
storage. Calculate the location of an element A[0].

CS_GATE@PRITESH_SAKLECHA 4
• A one dimensional array A has indices 1 to 75.
each element is a string and takes up to three
memory words. The starting address of array is
1120. The address of element A[49] is
• (a) 1267
• (b) 1164
• (c) 1264
• (d) 1169

CS_GATE@PRITESH_SAKLECHA 5
• Two dimensional arrays:
• Declaration of 2-D array
int A[10][20];
A[0][0] A[0][1] A[0][2]
A[1][0] A[1][1] A[1][2]
A[2][0] A[2][1] A[2][2]

• 2-D array stored in

• RMO(row major order)
A[0][0] A[0][1] A[0][2] A[1][0] A[1][1] A[1][2] A[2][0] A[2][1] A[2][2]

• CMO(column major order)

A[0][0] A[1][0] A[2][0] A[0][1] A[1][1] A[2][1] A[0][2] A[1][2] A[2][2]

CS_GATE@PRITESH_SAKLECHA 6
• A 2D array defined as a[4….7,-1…..3] requires 2
bytes if storage space for each element. If the
array is store in row major order then calculate the
address of elements at location a[6,2]. Assume
that the base address is 100.

CS_GATE@PRITESH_SAKLECHA 7
• Each element of an array a[-20…20,10….35]
requiers one byte of storage. If the array is
implemented in column major order and base
address of array is 500. then find the address of
element a[0,30].

CS_GATE@PRITESH_SAKLECHA 8
• Let A be a two dimensional array declared as follows:
A: array [1 ... 10] [1 ... 15] of integer;
Assuming that each integer takes one memory location,
the array is stored in row-major order and the first
element of the array is stored at location 100, what is
the address of the element a[i][j] ?
(A) 15i+ j+ 84
(B) 15j+ i+ 84
(C) 10i+ j+ 89
(D) 10j+ i+ 89

CS_GATE@PRITESH_SAKLECHA 9
• Most common operations that we can perform on
an array:
• Creation
• Insertion
• Deletion
• Updating
• Searching
• Sorting

CS_GATE@PRITESH_SAKLECHA 10
• Create an array with 100 elements and initialize with
0.

• Create an array with n elements and initialize with 0.

• Insert an element in an array that consist n elements.

• Insert at first position
• Insert at last position
• Insert at required position.

CS_GATE@PRITESH_SAKLECHA 11
CS_GATE@PRITESH_SAKLECHA 12
CS_GATE@PRITESH_SAKLECHA 13
CS_GATE@PRITESH_SAKLECHA 14
• Delete an element in an array that consist n elements.
• Delete from first position
• Delete from last position
• Delete from required position.

CS_GATE@PRITESH_SAKLECHA 15
• Searching:
• Linear Search:

12 5 7 25 8 19 17 23 65 92

CS_GATE@PRITESH_SAKLECHA 16
• Searching:
• Binary Search:
10 20 30 40 50 60 70 80 90 100

CS_GATE@PRITESH_SAKLECHA 17
Linked List

• A linked list is a linear data structure, in which the

elements are not stored at contiguous memory
locations. It is a special type of data structure in
which elements are store in the form of nodes and
each node consist minimum two fields.

Data pointer
Points to next node
• The elements in a linked list are linked using
pointers as shown in the below image:
Start
10 20 30 40 X
CS_GATE@PRITESH_SAKLECHA 18
• Advantages:
• Link list grow and shrink at run time.
• Efficient memory utilization.
• Insertion and deletion is easier and efficient.
• No need of contiguous memory
• Disadvantage:
• More memory required to store data items.
• Access to arbitrary data items is time consuming.
 Key terms
 Data
 Internal pointer
 External pointer
 Null Pointer
 Empty link list

CS_GATE@PRITESH_SAKLECHA 19
Types of link list
• Singly link list
• Circular link list
• Doubly link list
• Circular doubly link list

CS_GATE@PRITESH_SAKLECHA 20
Basic Operations on a Linked list
• Creation
• Insertion
• Deletion
• Traversing
• Searching
• Concatenation

CS_GATE@PRITESH_SAKLECHA 21