One most basic and most popular data structure is array. It is so hard to find a programming language where there is no arrays defined. Normally arrays can hold primitive data types such as ints, floats, booleans and such but you can create arrays to hold more complex user defined data types as well. In here the focus is not to show you how to create an array, how to insert an item to array and such. Those depends on the prog language you are using. More focus in here is to analyse the data structure and basic actions that can be performed on arrays.
So to have it formally start, array with n elements can have addresses ranging from 0th index to (n-1)th index. Thats it. :) And basically you can insert an item to an array, search for an item and delete an item from array. Here we will look an un-ordered array. We will look at ordered array data structure in a another example. This is because when it is ordered it has some certain advantages. ;)
So to have it formally start, array with n elements can have addresses ranging from 0th index to (n-1)th index. Thats it. :) And basically you can insert an item to an array, search for an item and delete an item from array. Here we will look an un-ordered array. We will look at ordered array data structure in a another example. This is because when it is ordered it has some certain advantages. ;)
No duplicates
You can insert duplicate data to an array.There is no problem with that. Lets see such a scenario.
Insert - you can insert your data item to next available space. 1 move.
Search - When you want to search a data item it can be at the first index. So 1 move. Worst case is it can be at the last index. So n moves. So depending on where it resides number of steps differs. So it is fair to say it takes n/2 moves on average for searching.
Delete - Before you search you have to first find it. And after deletion you have to restructure the array so that items from right side of the deleted item are moved 1 place left. So on average for search the item it takes n/2 moves. So using the same logic it takes on average n/2 moves to restructure.
With duplicates
Insert - You can just insert an item to an array. no matter it is a duplicate or not. So 1 move.
Search - You cant just stop finding the first element that you are looking for. Because there can more of that in the array. So you will have to search fro the whole array to search a specific item. So n moves.
Delete - Just like no duplicates example logic, n moves to search. Then on average n/2 moves to restructure after deletion.
0 comments:
Post a Comment