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口语等
兼容主流视频平台
Trancy 不仅提供对 YouTube, Netflix, Udemy, Disney+, TED, edX, Kehan, Coursera 等平台的双语字幕支持，还能实现对普通网页的 AI 划词/划句翻译、全文沉浸翻译等功能，真正的语言学习全能助手。
支持全平台浏览器
Trancy 支持全平台使用，包括iOS Safari浏览器扩展
多种观影模式
支持剧场、阅读、混合等多种观影模式，全方位双语体验
多种练习模式
支持句子精听、口语测评、选择填空、默写等多种练习方式
AI 视频总结
使用 OpenAI 对视频总结，快速视频概要，掌握关键内容
AI 字幕
只需3-5分钟，即可生成 YouTube AI 字幕，精准且快速
AI 单词释义
轻点字幕中的单词，即可查询释义，并有AI释义赋能
AI 语法分析
对句子进行语法分析，快速理解句子含义，掌握难点语法
更多网页功能
Trancy 支持视频双语字幕同时，还可提供网页的单词翻译和全文翻译功能