[0:00]Hello, welcome to the second part of the tutorial. Today, we're going to dive into the exciting world of data structures, where we'll explore linked lists, an array, an array list, and also a hash map. And we'll try to find out how they work under the hood, and we'll implement all of them step by step. So let's start with the link list. What is a link list? A link list is a linear data structure similar to an array, but the way they store the data is completely different. For example, in an array, we have a continuous block of memory where we store the elements, and in a link list, we don't have this restriction. We can store the data in different places in the memory, and they are connected using pointers. For example, here we have the first node that contains the value three, and it has a pointer to the next node. And the next node contains the value five, and it has a pointer to the next node, which is seven, and so on. And the last node always points to null. So basically, we have a sequence of nodes, and each node stores the data and a reference to the next node. And the main advantage of the link list compared to arrays is when we want to insert or delete elements. For example, when we want to insert an element in an array, if it is full, we need to create a new array with double the size and copy all the elements from the old array to the new array. But in a link list, it's not the case because we don't have a continuous block of memory. And the main disadvantages compared to arrays is when we want to access elements. For example, in an array, we can access the elements by index in constant time, but in a link list, we need to traverse the list from the beginning until we find the element, and that takes O(n) time. So now let's implement the link list step by step. First, we need to create a class that represents a node, and this class will contain the data and also a reference to the next node. So let's create a new class and call it node. And inside, we will have a property that represents the data. And let's make it generic so we can store any type of data.

[2:22]And we'll have a constructor that takes the data as a parameter. And we need also a reference to the next node. And the type will be node of T, and let's call it next. And when we create a new node, the next node will be null. Now that we have our node class, let's create our link list class. And inside, we will have a head node, which is the first node in the list. And it will be of type node of T, and let's call it head. And we'll have also a property for the size, which is the number of elements in the list. And let's initialize it to zero. Let's make our list generic so we can store any type of data. Now let's implement the first method, which is add at the beginning. So let's call it add first, and it will take the data as a parameter. And inside, we will create a new node.

[3:16]And this new node will point to the current head. And after that, we will update the head to be the new node. And finally, we will increment the size. Now let's implement the add last method, which adds an element at the end of the list. And it takes the data as a parameter. First, we need to create a new node. And we need to find the last node in the list. So let's create a temporary node and call it current, and let's assign it to the head. And we will loop until we find the last node. So while current.next is not null, we will update the current to be current.next. And when we exit the loop, the current will be the last node. So we will assign current.next to be the new node. And finally, we will increment the size. And we need to handle an edge case here. If the list is empty, we need to assign the new node to be the head. So if head is null, we will assign head to be the new node. Now let's implement the remove first method, which removes the first element from the list. First, we need to handle an edge case. If the list is empty, we will throw an exception. Otherwise, we will assign the head to be the head.next. And finally, we will decrement the size. Now let's implement the remove last method, which removes the last element from the list. First, we need to handle an edge case. If the list is empty, we will throw an exception. And if the list contains only one element, we will set the head to null. Otherwise, we need to find the second to last node. So let's create a temporary node and call it current, and let's assign it to the head. And we will loop until we find the second to last node. So while current.next.next is not null, we will update the current to be current.next. And when we exit the loop, the current will be the second to last node. So we will assign current.next to be null. And finally, we will decrement the size. Now let's implement the get method, which returns the element at the specified index. First, we need to validate the index. If the index is less than zero or greater than or equal to the size, we will throw an exception. Otherwise, we will create a temporary node and call it current, and let's assign it to the head. And we will loop until we reach the specified index. So for int i equal to zero, i less than index, i plus plus, we will update the current to be current.next. And when we exit the loop, the current will be the node at the specified index. So we will return current.data. Now let's implement the size method, which returns the number of elements in the list. And it will simply return the size property. Now let's test our linked list. So let's create a new linked list and add some elements. Let's add 10, 20, 30, and 40. And let's print the size. And as you can see, the size is four. Now let's remove the first element. And let's print the size again. And as you can see, the size is three. And let's print the elements. And as you can see, the elements are 20, 30, and 40. Now let's remove the last element. And let's print the size again. And as you can see, the size is two. And let's print the elements. And as you can see, the elements are 20 and 30. Now let's get the element at index zero. And as you can see, the element is 20. And let's get the element at index one. And as you can see, the element is 30. So that's it for the linked list. Now let's move on to arrays. What is an array? An array is a linear data structure that stores a fixed-size sequential collection of elements of the same type. And the main advantage of arrays is when we want to access elements by index in constant time. And the main disadvantage is when we want to insert or delete elements. For example, when we want to insert an element in an array, if it is full, we need to create a new array with double the size and copy all the elements from the old array to the new array. And when we want to delete an element, we need to shift all the elements after the deleted element to the left. So now let's implement the array step by step. First, we need to create a class that represents an array. And inside, we will have a private array of generic type. And let's call it items. And we'll have a private integer that represents the count of elements in the array. And let's initialize it to zero. And we'll have a constructor that takes the size of the array as a parameter. And inside, we will initialize the items array with the specified size. Now let's implement the add method, which adds an element at the end of the array. And it takes the item as a parameter. First, we need to check if the array is full. So if count is equal to items.length, we need to create a new array with double the size. So let's create a new array and call it new items, and the size will be count times two. And we need to copy all the elements from the old array to the new array. So for int i equal to zero, i less than count, i plus plus, we will assign new items[i] to be items[i]. And after that, we will assign items to be new items. And finally, we will add the new item to the array. So items[count] will be the item. And we will increment the count. Now let's implement the remove at method, which removes the element at the specified index. First, we need to validate the index. If the index is less than zero or greater than or equal to the count, we will throw an exception. Otherwise, we need to shift all the elements after the deleted element to the left. So for int i equal to index, i less than count minus one, i plus plus, we will assign items[i] to be items[i + 1]. And finally, we will decrement the count. Now let's implement the get method, which returns the element at the specified index. First, we need to validate the index. If the index is less than zero or greater than or equal to the count, we will throw an exception. Otherwise, we will return items[index]. Now let's implement the size method, which returns the number of elements in the array. And it will simply return the count property. Now let's test our array. So let's create a new array with size three and add some elements. Let's add 10, 20, 30, and 40. And let's print the size. And as you can see, the size is four. Now let's remove the element at index one. And let's print the size again. And as you can see, the size is three. And let's print the elements. And as you can see, the elements are 10, 30, and 40. Now let's get the element at index zero. And as you can see, the element is 10. And let's get the element at index one. And as you can see, the element is 30. So that's it for the array. Now let's move on to array list. What is an array list? An array list is a dynamic array that can grow or shrink in size as needed. And it is similar to an array, but it handles the resizing automatically. And the main advantage of array lists is when we want to insert or delete elements. It resizes the internal array automatically when elements are added or removed. And the main disadvantage is when we want to access elements by index, it takes O(n) time in the worst case, because it might need to resize the array. So now let's implement the array list step by step. First, we need to create a class that represents an array list. And inside, we will have a private array of generic type. And let's call it elements. And we'll have a private integer that represents the size of the array list. And let's initialize it to zero. And we'll have a constructor that initializes the elements array with a default capacity of 10. Now let's implement the add method, which adds an element at the end of the array list. And it takes the element as a parameter. First, we need to check if the array is full. So if size is equal to elements.length, we need to resize the array. So let's create a new array with double the size. So let's create a new array and call it new elements, and the size will be elements.length times two. And we need to copy all the elements from the old array to the new array. So for int i equal to zero, i less than size, i plus plus, we will assign new elements[i] to be elements[i]. And after that, we will assign elements to be new elements. And finally, we will add the new element to the array. So elements[size] will be the element. And we will increment the size. Now let's implement the remove method, which removes the element at the specified index. First, we need to validate the index. If the index is less than zero or greater than or equal to the size, we will throw an exception. Otherwise, we need to shift all the elements after the deleted element to the left. So for int i equal to index, i less than size minus one, i plus plus, we will assign elements[i] to be elements[i + 1]. And finally, we will decrement the size. Now let's implement the get method, which returns the element at the specified index. First, we need to validate the index. If the index is less than zero or greater than or equal to the size, we will throw an exception. Otherwise, we will return elements[index]. Now let's implement the size method, which returns the number of elements in the array list. And it will simply return the size property. Now let's test our array list. So let's create a new array list and add some elements. Let's add 10, 20, 30, and 40. And let's print the size. And as you can see, the size is four. Now let's remove the element at index one. And let's print the size again. And as you can see, the size is three. And let's print the elements. And as you can see, the elements are 10, 30, and 40. Now let's get the element at index zero. And as you can see, the element is 10. And let's get the element at index one. And as you can see, the element is 30. So that's it for the array list. Now let's move on to hash map. What is a hash map? A hash map is a data structure that stores key-value pairs. And it uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. And the main advantage of hash maps is when we want to insert, delete, or access elements by key in constant time on average. And the main disadvantage is when we want to iterate over the elements, it takes O(n) time, because we need to iterate over all the buckets. So now let's implement the hash map step by step. First, we need to create a class that represents a hash map. And inside, we will have a private array of linked lists of generic type. And let's call it buckets. And we'll have a private integer that represents the size of the hash map. And let's initialize it to zero. And we'll have a constructor that initializes the buckets array with a default capacity of 10. And we need to initialize each bucket with a new linked list. So for int i equal to zero, i less than buckets.length, i plus plus, we will assign buckets[i] to be a new linked list. Now let's implement the put method, which adds a key-value pair to the hash map. And it takes the key and the value as parameters. First, we need to get the index of the bucket. So let's create a method called hash that takes the key as a parameter and returns the index. And inside, we will return key.hashCode() modulo buckets.length. And we need to make sure that the index is always positive. So we will add Math.abs to the result. Now back to the put method. We have the index, so let's get the bucket. And we need to check if the key already exists in the bucket. So for int i equal to zero, i less than bucket.size, i plus plus, we will get the entry. And if entry.key is equal to the key, we will update the value. And we will return. Otherwise, we will add a new entry to the bucket. And we will increment the size. And we need to create a class that represents an entry. And this class will contain the key and the value. So let's create a new class and call it entry. And inside, we will have a property that represents the key. And let's make it generic. And we'll have a property that represents the value. And we'll have a constructor that takes the key and the value as parameters. Now back to the put method. We will add a new entry to the bucket. And we will increment the size. Now let's implement the get method, which returns the value for the specified key. First, we need to get the index of the bucket. So let's get the bucket. And we need to check if the key exists in the bucket. So for int i equal to zero, i less than bucket.size, i plus plus, we will get the entry. And if entry.key is equal to the key, we will return entry.value. Otherwise, we will return null. Now let's implement the remove method, which removes the entry for the specified key. First, we need to get the index of the bucket. So let's get the bucket. And we need to check if the key exists in the bucket. So for int i equal to zero, i less than bucket.size, i plus plus, we will get the entry. And if entry.key is equal to the key, we will remove the entry from the bucket. And we will decrement the size. And we will return. Now let's implement the size method, which returns the number of elements in the hash map. And it will simply return the size property. Now let's test our hash map. So let's create a new hash map and add some elements. Let's add 10, 20, 30, and 40. And let's print the size. And as you can see, the size is four. Now let's get the element with key 10. And as you can see, the element is 10. And let's get the element with key 20. And as you can see, the element is 20. Now let's remove the element with key 10. And let's print the size again. And as you can see, the size is three. And let's get the element with key 10 again. And as you can see, the element is null. So that's it for the hash map. In this tutorial, we have covered linked lists, arrays, array lists, and hash maps. And we have seen how they work under the hood and implemented all of them step by step. I hope you enjoyed this tutorial. And if you have any questions, please let me know in the comments below. Thank you for watching.