1.2 Array Operations - Traversal, Insertion | Explanation with C Program | DSA Course

Name: 1.2 Array Operations - Traversal, Insertion | Explanation with C Program | DSA Course
Uploaded: 2019-07-24T08:16:30.000Z
Duration: 56 min 51 s

Operations on Arrays in Data Structures

In this video, the speaker discusses various operations that can be performed on 1D arrays in data structures. The most important operations covered are traversal of an array, insertion and deletion of data, searching for a key element, and sorting of an array.

Traversing an Array

Traversal means visiting every element of the array exactly once.

To traverse an array, we need to print all the elements in the array.

We can do this by using a loop that starts from index 0 and goes up to size - 1 (where size is the number of elements in the array).

Each element is printed one by one as we iterate through the loop.

Inserting Data into an Array

There are three types of insertion: at the beginning of the array, at the end position of the array or at any specific position in the array.

To insert data into an array, we first need to initialize it with some values.

Initialization can be done either at compile time or runtime.

At runtime, we can ask for user input to populate our array with values.

Once initialized, we can use loops and conditional statements to insert new elements into our existing array.

Other Operations on Arrays

Other operations that can be performed on arrays include finding minimum and maximum elements from an array, finding duplicate elements from an array, reversing an array and finding second largest element from an array.

Overall, this video provides a good introduction to basic operations that can be performed on 1D arrays in data structures. The speaker explains each operation clearly and provides examples with code snippets.

Memory Allocation

In this section, the speaker discusses memory allocation for an array and how to take input from the user.

Allocating Memory for an Array

The number of bytes allocated in memory for an array is determined by multiplying the size of the array by 4.

To allocate memory for an array, ask the user how many elements they want to insert and use scanf to take input from the user.

Use a variable to store the size of the array and declare another variable using address of operator to store values in memory.

Populating Data in Array

To populate data in an array, use a for loop starting from 0 till size minus one.

Use printf to prompt users to enter elements of the array and use scanf within a for loop to take input from users.

After taking input from users, traverse through the array using another for loop and print out all elements using printf.

Printing Elements in Array

In this section, we learn how to print out all elements in an array.

Printing Elements in Array

Traverse through the array using a for loop starting from 0 till size minus one.

Use printf within a second for loop to print out all elements in the array.

Introduction to Arrays

In this section, the instructor introduces arrays and explains how to traverse an array using a loop. The instructor also discusses the concept of overflow condition and upper bound checking in arrays.

Traversing an Array

To traverse an array, use a loop with a variable that represents the index of each element.

Declare the variable before using it in the loop.

Use the variable to access each element of the array.

Print out each value as you access it.

Overflow Condition and Upper Bound Checking

If an array is full, you cannot insert any more elements into it. This is called an overflow condition.

When declaring an array, specify its size. The maximum index will be one less than this size.

There is no built-in upper bound checking for arrays in C. It is up to the programmer to check if they are trying to insert too many elements into an array.

To check for upper bound limit, write code that compares the current size of the array with its maximum size. If the current size exceeds this limit, print out an overflow message.

Inserting Elements at Specific Positions in Arrays

In this section, we learn how to insert elements at specific positions in arrays. We also discuss how shifting can be used when inserting new elements.

Inserting Elements at Specific Positions

To insert a new element at a specific position in an array:

Check if there is space available in the array (i.e., not already full).

Shift all elements from that position onwards one position to the right.

Insert new element at desired position.

Shifting Elements

Shifting involves moving all elements from a certain point onwards one position to the right or left.

When inserting new elements into an array, shifting can be used to make space for the new element.

To shift elements, use a loop that starts from the last element and moves backwards towards the desired position.

Inserting Data into an Array

In this section, the speaker explains how to insert data into an array in C programming language.

Declaring Variables and Entering Array Size

Declare two variables, num and booze, to store the values.

Enter the size of the array.

Enter the elements of the array.

The size of the array should be less than or equal to 50. If it is greater than 50, print "overflow condition" and do not insert anything extra.

Checking Boundaries and Taking User Inputs

To check boundaries, write code for checking boundaries as there is no concept of bounds checking of arrays in C.

Take two more inputs from users: data they want to insert and position at which they want to insert.

Swap elements starting from the last element only because swapping from any other position will overwrite some values that cannot be recovered.

Swapping Elements Using For Loop

Write a for loop for swapping elements starting from where we have started initially (from index 0).

Two ways are there to start a for loop:

Start from size minus one

Start from here (position minus one)

Use I variable in for loop.

Initially, I is equal to size minus one.

I should be greater than or equal to position minus one.

When I becomes 1 then stop swapping.

Inserting Data at Specific Position

After swapping all necessary elements, insert data at specific position using index (position minus one).

Increase array size by one after inserting data.

Printing Array Values

Traverse through all values in an array using a for loop starting from index 0 up until the new size of the array.

Print each value using printf statement with format specifier %d.

Conclusion

In this section, the speaker concludes the topic of inserting data into an array in C programming language.

The speaker summarizes the steps for inserting data into an array.

The importance of checking boundaries and swapping elements starting from the last element is emphasized.

Finally, the speaker reminds us to print all values in an array using a for loop.

Array Insertion

In this section, the speaker explains how to insert data into an array at a specific position. They discuss the limitations of arrays and provide code examples for inserting data at the beginning, end, and any other position in the array.

Inserting Data at Specific Positions

Arrays store data in consecutive locations.

Position can be 1, 2, 3, 4 & 5. All positions can be 6 except for position 10.

If you try to insert data in a non-consecutive location, it will not work.

To insert data at a specific position:

Check if the position is valid (not less than or greater than size + 1).

If invalid, print an error message.

Otherwise, use a for loop to shift all elements to the right of the insertion point one index over.

Insert new data at the desired position.

Inserting Data at Beginning or End of Array

Beginning

To insert data at the beginning of an array:

Use a for loop to shift all elements one index over from right to left.

Insert new data at index zero.

End

To insert data at the end of an array:

Simply add new data to index size (the next available index).

Time Complexity

The time complexity depends on where you want to insert your new element in relation to existing elements.

If you need to shift all elements over by n indices (where n is size minus insertion point), time complexity is Theta(n).

Best case scenario is when inserting at index one with no shifting required (time complexity = Theta(1)).

Worst case scenario is when inserting at last index with maximum shifting required (time complexity = Theta(n)).

Unsorted vs Sorted Arrays

Inserting data into an unsorted array is easier because you don't need to worry about maintaining order.

In a sorted array, you need to shift elements over until you find the correct position for your new element.

Best Algorithm Time Complexity

In this section, the speaker discusses the best algorithm time complexity for sorted and unsorted arrays.

Theta Time Complexity

The best time complexity is Theta.

In an exam, if a question is asked about the best algorithm time complexity, you should write down Theta.

For an unsorted array, you can insert a number in constant time by adding 2 to the add position minus 1.

For a sorted array, you cannot simply take a value and set it at the end. You have to take care of the relative ordering of elements in the sorted array.

Shifting Method

You can apply shifting method in an unsorted array also but it's not the best method.

In case of a sorted array, you are going to do two shift operations.

Deleting Data from Array

In this section, the speaker will discuss how to delete data from an array.

Next Video Preview

The next video will discuss how to delete data from an array.