ARRAY

Data Structure
Inserting an Element in an Array
• If an element has to be inserted at the end of an existing array, then the
task of insertion is quite simple.
• We just have to add 1 to the upper_bound and assign the value
• ALGORITHM:
Step 1: Set upper_bound = upper_bound+1
Step 2: Set A[upper_bound] = VAL
Step 3: EXIT
• To insert an element in the middle of an Array
• The algorithm INSERT will be declared as INSERT (A, N, POS,
VAL).
• The arguments are
• A, the array in which the element has to be inserted
• N, the number of elements in the array
• POS, the position at which the element has to be inserted
• VAL, the value that has to be inserted
• ALGORITHM:
Step 1: [INITIALIZATION] SET I=N-1
Step 2: Repeat Steps 3 and 4 while I>= POS
Step 3: SET A[I + 1] = A[I]
Step 4: SETI=I–1
[END OF LOOP]
Step 5: SET N=N+1
Step 6: SET A[POS] = VAL
Step 7: EXIT
Program to insert a number at given position
of an Array
#include <stdio.h>
int main()
{ int i, n, num, pos, arr[20];
printf("\n Enter the no. of elements in the array : ");
scanf("%d", &n);
for(i=0;i<n;i++)
{ printf("\n arr[%d] = ", i);
scanf("%d", &arr[i]); }
printf("\n Enter the number to be inserted : ");
scanf("%d", &num);
printf("\n Enter the position at which the number has to be added :");
scanf("%d", &pos);
for(i=n–1;i>=pos;i--)
arr[i+1] = arr[i];
arr[pos] = num;
n = n+1;
printf("\n The array after insertion of %d is : ", num);
for(i=0;i<n;i++)
printf("\t %d", arr[i]);
return 0;
}
OUTPUT:
Enter the number of elements in the array : 2
arr[0] = 1
arr[1] = 3
Enter the number to be inserted : 2
Enter the position at which the number has to
be added : 1
The array after insertion of 2 is :
123
Delete an Element from an Array
• Deleting an element from an array means removing a data element
from an already existing array.
• If the element has to be deleted from the end of the existing array, then
the task of deletion is quite simple.
• We just have to subtract 1 from the upper_bound.
• ALGORITHM:
Step 1: SET upper_bound = upper_bound-1
Step 2: EXIT
Delete an Element from middle of an Array
• The algorithm DELETE will be declared as DELETE(A, N,POS).
• The arguments are:
• (a) A, the array from which the element has to be deleted
• (b) N, the number of elements in the array
• (c) POS, the position from which the element has to be deleted
• ALGORITHM:
Step 1: [INITIALIZATION] SET I= POS
Step 2: Repeat Steps 3 and 4 while I<=N–1
Step 3: SET A[I] = A[I+1]
Step 4: SET I=I+1
[END OF LOOP]
Step 5: SET N=N–1
Step 6: EXIT
Program to Delete a number from a given
position in an Array
#include <stdio.h>
int main()
{ int i, n, pos, arr[10];
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
for(i=0;i<n;i++)
{ printf("\n arr[%d] = ", i);
scanf("%d", &arr[i]); }
printf("\nEnter the position from which the number has to be deleted : ");
scanf("%d", &pos);
for(i=pos; i<n–1;i++)
arr[i] = arr[i+1];
n--;
printf("\n The array after deletion is : ");
for(i=0;i<n;i++)
printf("\t %d", arr[i]);
return 0;
}
• OUTPUT:
Enter the number of elements in the array : 4
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
Enter the position from which the number has to be
deleted : 2
The array after deletion is :
124
Advantages of Array
Efficient access to elements: Arrays provide direct and efficient access to any element in the
collection. Accessing an element in an array is an O(1) operation, meaning that the time required to
access an element is constant and does not depend on the size of the array.

Fast data retrieval: Arrays allow for fast data retrieval because the data is stored in contiguous
memory locations. This means that the data can be accessed quickly and efficiently without the need
for complex data structures or algorithms.

Memory efficiency: Arrays are a memory-efficient way of storing data. Because the elements of an
array are stored in contiguous memory locations, the size of the array is known at compile time. This
means that memory can be allocated for the entire array in one block, reducing memory
fragmentation.
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.

Easy to implement: Arrays are easy to implement and understand, making them an ideal
choice for beginners learning computer programming.

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
• Fixed size: Arrays have a fixed size that is determined at the time of creation. This means that if
the size of the array needs to be increased, a new array must be created and the data must be
copied from the old array to the new array, which can be time-consuming and memory-intensive.

 Memory allocation issues: Allocating a large array can be problematic, particularly in systems
with limited memory. If the size of the array is too large, the system may run out of memory,
which can cause the program to crash.
• Insertion and deletion issues: Inserting or deleting an element from an array can be inefficient
and time-consuming because all the elements after the insertion or deletion point must be shifted
to accommodate the change
 Wasted space: If an array is not fully populated, there can be wasted space in the memory
allocated for the array. This can be a concern if memory is limited.

 Limited data type support: Arrays have limited support for complex data types such as objects
and structures, as the elements of an array must all be of the same data type.

 Lack of flexibility: The fixed size and limited support for complex data types can make arrays
inflexible compared to other data structures such as linked lists and trees.
Applications of Array in C/C++:

 Arrays are used to implement vectors, and lists in C++ STL.

 Arrays are used as the base of all sorting algorithms.

 Arrays are used to implement other DS like a stack, queue, etc.

 Used for implementing matrices.

 Data structures like trees also sometimes use the array implementation since arrays are easier to handle than
pointers. For example, a segment tree uses array implementation.

 Binary search trees and balanced binary trees are used in data structures such as a heap, map, and set, which
can be built using arrays.

 Graphs are also implemented as arrays in the form of an adjacency matrix.

• Approach: To create an array of linked lists below are the main requirements:

An array of pointers.

 For keeping the track of the above-created array of pointers then another pointer is needed that points to the
first pointer of the array. This pointer is called pointer to pointer.

• Below is the pictorial representation of the array of linked lists:

1. Pointer to Pointer ( ** ):
- At the top-left, there’s a double pointer (**), which points to an array of
pointers. This double pointer serves as an entry point to the entire data
structure.

2. Array of Pointers:
- The double pointer (**) points to an array of single pointers (*). Each
element in this array is a pointer to the head of a linked list. This array
essentially acts as an array of heads for multiple linked lists.
3. Linked Lists:
- Each pointer in the array points to the first node of a linked list.
- Each node in a linked list contains some data and a pointer to
the next node in the list. The linked lists can have varying lengths,
and they are dynamically linked, meaning they are not contiguous
in memory.

4. Data Storage:
- The nodes in the linked lists contain data. Each linked list can
grow or shrink independently as nodes are added or removed.
In summary:
- The ** pointer points to an array of * pointers.
- Each * pointer points to the head of a linked list.
- Each linked list consists of nodes, where each node
contains data and a pointer to the next node.