Data Structures

Souramita Bhowmik
Assistant Professor
Department of Data Science
Dayananda Sagar University, Harohalli, Karnataka.
Email Id: souramita-ds@[Link]
Arrays in C
Definition of Array

•An array is a collection of elements of the same data type, stored in contiguous memory
locations, accessed using an index.
•Index starts at 0 in C.

•Example:
int marks[5] = {90, 85, 70, 95, 88};
marks[0] = 90, marks[1] = 85, …
• An array’s data items are stored contiguously in memory.
• An array is a linear collection of finite number of homogenous data elements.
• Each element in an array has a subscript (index) associated with it starting with 0.
• Number of elements, N –> length or size of an array.
If:
UB : upper bound ( the largest index)
LB : lower bound (the smallest index)
Then: N = UB – LB + 1
Length = N = UB when LB = 1
Length = N = UB+1 when LB = 0
Array
Size of array A = 6
10 20 30 40 50 60

A 0 1 2 3 4 5

LB UB

Size = upper bound – lower bound +1

Size = 5 – 0 + 1 = 6

A[0] – Base Element = 10

A[1] = 20, A[2] = 30, A[3] = 40, A[4] = 50, A[5] = 60
Why do we need arrays?
• Arrays allow you to group multiple values of the same data type under a single
name.
• This makes it easier to organize and manage related data. For example, you can
use an array to store a list of student's marks.
• Arrays store elements in contiguous memory locations, which means that
elements are stored one after the other in memory.
• This property allows for efficient sequential access to the elements of an array.
• You can easily iterate through the elements of an array using loops like for or
while.
Array Representation
• One dimensional Array: Finite ordered set of homogeneous elements.
• Finite means the number of elements in the array are initialized before using.
• Ordered means each elements in the array are arranged and can be retrieved using
it index. Index starts from zero.
• Homogeneous means all the elements in the array must be of the same data type.
• To declare an array, you specify the data type of its elements, followed by the
array name and the number of elements it can hold (the size of the array).

int a [100];
Memory Representation in Array
• Memory Allocation: The size of this memory block is determined by the data
type of the elements and the number of elements in the array.
• For example, an array of 5 integers (int data type) will occupy
5 * sizeof(int) bytes of memory.

• Indexing: Each element in array is assigned an index or position, starting from 0.

Memory representation 1D Array
• There is no need to keep track of address of each element.
• Only the address of the 1st element (base address) is needed.

A 32 15 48 27 74 10
0 1 2 3 4 5 <- Array Index
150 154 158 162 166 170 <- Memory address
Base address
Address of A[i] = Base address + sizeof(datatype) ( i – LB)
A[0] = 150+ 4( 0 – 0) = 150
A[1] = 150+ 4( 1 – 0) = 154 Integer – 4 bytes
A[2] = 150+ 4( 2 – 0) = 158 Char – 1 byte
A[3] = 150+ 4( 3 – 0) = 162 Float – 4/8 bytes
A[4] = 150+ 4( 4 – 0) = 166
A[5] = 150+ 4( 5 – 0) = 170
Array Initialization
• Declaration : datatype arrayname [arraysize] // int X[6]

1. Initializing at Declaration (Explicit Initialization):

int numbers[] = {1, 2, 3, 4, 5};

2. Initializing at Declaration (Partial Initialization):

// Initializes the first two elements, rest are set to 0
int numbers[5] = {1, 2};

3. Initializing at Declaration (Designated Initializers):

int numbers[5] = {[2] = 42, [4] = 10};
4. Initializing with a String
char greeting[] = "Hello, World!";

5. Initializing in a Loop:

6. Dynamic Initialization (at runtime):

Operations of Data Structures
• Insertion
• Deletion
• Searching
• Sorting
• Traversing
• Merging
Array Traversal
• Visiting the elementsi =of
1
ani =array once.
i=0 2 i=3 i=4

A 32 15 48 27 74 Size = 5
0 1 2 3 4

For i = 0 to 4 (size -1)

i=0 Print A[0] // 32

i=1 Print A[1] // 15
i=2 Print A[2] // 48
i=3 Print A[3] // 27
i=4 Print A[4] // 74
Array Insertion
• Insert item at the back is easy if there is a space. Insert item in the middle requires the movement of
all elements to the right
• Let A be an array as below
2 5 3 4

2 5 3 4

Let here we have to insert 6

2 5 3 4

2 5 3 4

2 5 6 3 4
Array Insertion
pos = 2
Size = 5
A 32 15 48 27 74
Insert element 10 at index 2
0 1 2 3 4
LB UB = size -1 pos = 2

For i = UB to 2 (pos), decrement i

A 32 15 48 27 74

i=4 Shift one position right, A[i+1] = a[i] 0 1 2 3 4 5

A[5] = A[4] pos = 2
i=3 Shift one position right, A[i+1] = a[i] 32 15 48 27 74
A
A[4] = A[3]
0 1 2 3 4 5
pos = 2
i=2 Shift one position right, A[i+1] = a[i]
A 32 15 48 27 74
A[3] = A[2]
i=1 Its less than position = 2, Exit loop 0 1 2 3 4 5
pos = 2
Insert at A[pos] = A[2] = 10
A 32 15 10 48 27 74
Size = size +1 = 6
0 1 2 3 4 5
Array Insertion
pos = 2
Size = 5
A 32 15 48 27 74 Insert element 10 at index 2
0 1 2 3 4
LB UB = size -1
pos = 2
For i = UB to 2 (pos), decrement i
A 32 15 48 27 74
i=4 Shift one position right, A[i+1] = a[i] 0 1 2 3 4 5
A[5] = A[4] pos = 2
32 15 48 27 74
i=3 Shift one position right, A[i+1] = a[i]A
A[4] = A[3] 0 1 2 pos =32 4 5
32 15 48 27 74
i=2 Shift one position right, A[i+1] = a[i]A
A[3] = A[2] 0 1 2 3 4 5
i=1 Its less than position = 2, Exit loop pos = 2
Insert at A[pos] = A[2] = 10 A 32 15 10 48 27 74
Size = size +1 = 6 0 1 2 3 4 5