Array Data Structure | Illustrated Data Structures

Array Data Structure | Illustrated Data Structures - 이중 자막

Hey everyone, welcome to the second video of the illustrated data structure series.

In this video we will be discussing everything you need to know about the array data structure.

We will be talking about what the arrays are,

how they work, what are some of the limitations, different operations you can perform on an array and the complexity of those operations.

So, what is an array?

An array is a collection of items that are stored conductively in the memory.

Let's say that we have this representation of the memory with each block represent a slot in the memory.

Now, you might have an array of numbers or an array of characters, where each character is placed to the next character in the array.

There are two features of an array that you should keep in mind.

The first one is that all the items of an array have the same type,

so you can't have a mix of characters, numbers, and strings, they all have to have the same type.

And the second one is that Addy has to have the fixed size.

So for example, if you allocated 5 items for the Addy, you can't add the 6th item to it.

Let's look at some examples of Addys in C++.

Now don't worry if you are not familiar with C++ as the concepts that we will cover in this video.

They are same in the other languages.

For example, here we have an array of 3 integers, an array of strings, and an array of characters.

When each array has a type, we declare the type of item.

to hold, then we have the length of the array that is how many items that the array can hold at maximum.

And lastly, we have the values or items in the array.

Now again, the array that we declare, it's fixed in size.

So you can't allocate more space at the runtime.

so for example if you have this array of three numbers we won't be able to add a fourth element

to this array and secondly we can't have the mixed values inside this array so we can't have an

array where we have the characters strings and integers in the same array now you might be wondering

why do we have these two limitations let's look at them both one by one one.

Let's say that we have this array of three integers, which we have to represent in the memory.

Now, what our program is going to do is it is going to allocate three slots in the memory.

And then it is going to populate the values in those slots.

Now, since the computer memory is not only specific to us, and it is available for the other programs as well.

well, computer is going to keep using these memory slots and keep paragating the memory slots for the other things.

Now later on, let's say that we try to add a fourth element to the array.

Since our program I located only three slots for the array, the fourth slot may or may not be available.

And so the program is not going to allow us to populate the fourth value in the array.

And that is the reason why we have the areas which are fixed in size.

So we have to define the size of the array before we start using it,

so that the computer can reserve the consecutive memory blocks for the array to be used.

Now you might be wondering what is stopping us from allocating a really large number for our array so that whenever we need new numbers,

we can simply push them into the array.

The reason why you can't do that is because in doing so, you'll be keeping.

slots for yourself even if you don't need them and you won't be letting the other programs

which might need those memory slots from using those memory slots and this will cause the memory leak.

Alright, so next we have the case for the mixed types.

Why can't we have the areas with the mixed data types?

Before we talk about that, let's look at some of the example data types.

Let's say that we have these three different areas, an array of integers, an array of bullions, an array of characters.

Now the size of an integer is two bytes each.

A bullion value takes one byte in the memory and a character also takes a single byte in the memory.

Let's say that we have this memory representation where each block represents one byte in the memory.

Let's say that we have this array of integers that we need to represent in the memory.

We know that each integer takes two bytes in the memory.

So the first number in the array, that is four, it is going to take two blocks or two blocks.

9 is going to take another 2 blocks and 6 is going to take the last 2 blocks.

Now when it is time to access these array elements from the memory, since our program knows that the array is an array of...

So it knows that it has to read the first two bytes and it will get the first number of the array.

Skip bytes and read the next two bytes and it will get the second number.

Skip four bytes and read the next two bytes and it will get the third number and so on.

Now imagine if we had an array with the values of the mixed types.

So we have an integer which will take two bytes,

a string of three characters which will take three bytes, and a boolean which will take one byte.

Now when it is time to read these values from the memory,

since it is an array of mixed values,

our program won't know how many bytes should it read to get the first, second, or third value.

And that is the reason why all the items of an array have to have the same type.

Alright, so now you might be wondering why don't we have these limitations in the languages such as JavaScript, PHP, or Ruby.

How can we have the dynamically sized areas and also the support, the values with the mixed types?

And the answer to that is because there is a lot going on behind the scenes to make

Let's say that we have this array of numbers in JavaScript.

It is going to allocate three blocks and populate the values in the memory.

And our program is going to continue and keep using the other blocks in the memory for other stuff.

Later on,

when we push a new number to the array,

it is going to check and see if the next block is empty for us to consume.

if it is empty it is going to allocate that for our array and put the newly added number to that

And now if we try to push a new number to that, and let's say that the next memory block, it can't be allocated.

In that case, it is going to try and find out some other place in the memory where it can populate the whole array.

It is going to find that space,

allocate that for the array that we have,

move all the items that we have in the array there,

and free of the previously allocated array space and push the new item to the newly allocated array space.

And that is how these languages can have dynamically sized arrays.

Now the next question is about the arrays with the mixed type where you Here we have an array with an integer of 2 bytes,

string of 3 bytes, and a boolean of 1 byte.

How is JavaScript able to represent this array with a mixed type value?

And the answer to that is the capping of the size.

So what do we mean by that?

Now in this case, JavaScript is going to find the element with the maximum size in the array.

Now in this case,

string is taking the maximum size of three bytes,

so it is going to take three bytes and allocate them for each of the element of the array.

So in total, it will allocate nine bytes, three bytes per element in total for the whole array.

So, instead of 7 bytes, we'll have 9 bytes for this whole array.

Let's look at the video representation to understand more.

So first we have the integer.

Instead of allocating 2 bytes,

since the maximum size of element in the array is 3 bytes, so it is going to allocate 3 bytes for the integer.

then three bytes for the string and three bytes for the boolean.

Now when it comes the time to read the values from the memory, it knows that it has kept all the elements to three bytes.

So it is going to read three bytes and get the first element,

skip three bytes and read the next three bytes to get the second element.

Skip six bytes and read the next three bytes to get the third element and so on and that

is how it achieves the possibility of elements having the mixed types in the array.

Alright, so now that we know what the arrays are and how they work, let's look at the operations

that we can perform on the arrays and the algorithmic complexity of those of Let's say that we have this array of numbers.

The items of the arrays are indexed starting from 0 till the end.

And we use this index to read the elements from the array.

So for example, to read the first element of the array, we will write numbers of 0, and we will get the first number.

And to read the fifth element of the array, we will write numbers of five, and so on.

And the complexity of reading an element from the array is constant complexity, that is O of 1.

We will not be discussing how the complexity is calculated in this video,

but I have a separate video on this channel,

which goes into much more detail about the complexity analysis, so make sure to check that out.

Next we have inserting an at an index.

Let's say that we have the same array and we need to insert an element 3 at index 2.

Now what it will do is starting from index 2,

push all the items to the right to make space for the element to be inserted.

And once it has the space, it will push the element 3 to the right.

The algorithm complexity of this process would be linear.

That O of n.

Next we have the deletion of an element from the array.

Let's say that we want to remove the element from index 2.

We will simply remove the element and pull back each of the remaining elements in the array.

The algorithm complexity of deleting an element is also linear.

That is O of n.

Next, we have the updating of the value at an index.

Now this one is quite simple.

All we have to do is just replace the value at the index.

And the algorithmic complexity of updating a value is also constant.

And finally, we have traversing the array, which means simply visiting each element of the array.

An complexity of traversing the array is of course OFN.

And that is all about the arrays.

In our next video, we will be talking about the link lists.

So make sure to subscribe and I will see you in the next one.

번역 언어

번역 언어 선택

비디오 요약 자막 내보내기 구술 평가

더 많은 기능 잠금 해제

Trancy 확장 프로그램을 설치하면 AI 자막, AI 단어 정의, AI 문법 분석, AI 구술 등을 포함한 더 많은 기능을 사용할 수 있습니다.

Array Data Structure | Illustrated Data Structures - 이중 자막

더 많은 기능 잠금 해제

인기 있는 비디오 플랫폼과 호환

시작 준비되셨나요?