1 00:00:01,020 --> 00:00:07,080 Not look at our list which is an implementation often listen into office it is one of the most commonly 2 00:00:07,080 --> 00:00:12,360 used data structures beautifullest is because some of the important things about orderless and in the 3 00:00:12,360 --> 00:00:20,320 next lesson be able to write them off it as the name implies it is an implementation. 4 00:00:20,370 --> 00:00:29,100 Often listening to this update is resizable do so internally it uses an added since it is used internally 5 00:00:29,110 --> 00:00:29,260 . 6 00:00:29,370 --> 00:00:34,100 It obviously has some size associated with it and by default it is dead. 7 00:00:34,560 --> 00:00:40,980 So when this capacity is reached a new array is created that the size that is around 50 percent larger 8 00:00:41,040 --> 00:00:46,720 than the old arrays ice on the array contents are copied into the new ID. 9 00:00:47,010 --> 00:00:50,440 So whenever array sizes reach the resizing of the Oddy. 10 00:00:50,450 --> 00:00:52,080 About 50 percent. 11 00:00:52,530 --> 00:00:54,180 Business must have big disk value. 12 00:00:54,210 --> 00:01:00,510 After performing loff experiments because if it is too high a value like say 100 percent then it can 13 00:01:00,510 --> 00:01:02,120 be an overkill. 14 00:01:02,220 --> 00:01:04,880 That is it may consume too much of memory. 15 00:01:05,820 --> 00:01:08,470 Typically such are resizing should not matter. 16 00:01:08,700 --> 00:01:13,650 But if you feel you are dealing with a large number of elements then you can create an idealist with 17 00:01:13,650 --> 00:01:15,290 the high initial capacity. 18 00:01:15,300 --> 00:01:21,600 Using this constructor all you can also use this method in short capacity before adding large number 19 00:01:21,600 --> 00:01:22,890 of elements. 20 00:01:23,180 --> 00:01:30,680 That is the new capacity as an argument with this method and it allows storing duplicates and also not 21 00:01:30,700 --> 00:01:39,420 to use on here it's typical use cases you would use it when you want to iterate a list of elements like 22 00:01:39,420 --> 00:01:42,610 a list of elements fetched from a database. 23 00:01:42,720 --> 00:01:48,010 Since it is an RDBMS implementation you do get the benefit of fast random access. 24 00:01:48,240 --> 00:01:53,850 That is you can access the elements in constant time so the size of your collection does not matter 25 00:01:53,850 --> 00:01:55,020 . 26 00:01:55,130 --> 00:02:01,620 Now if appending elements to the list or removing the last element is a frequent operation then you 27 00:02:01,620 --> 00:02:07,460 can use an audit list as both these operations can be performed in constant time. 28 00:02:07,650 --> 00:02:12,810 Only thing to note about appending an element is that when the other illness and denote capacity is 29 00:02:12,810 --> 00:02:18,140 reached then appending a new element would trigger resizing. 30 00:02:18,230 --> 00:02:21,940 In that case there would be some additional time in. 31 00:02:22,630 --> 00:02:23,760 No let's look at some of them. 32 00:02:23,800 --> 00:02:25,380 It's not a list. 33 00:02:25,410 --> 00:02:26,690 And what does methods do. 34 00:02:26,750 --> 00:02:28,020 What are already discussed. 35 00:02:28,150 --> 00:02:31,220 Then be looked at list collection interfaces. 36 00:02:31,260 --> 00:02:35,670 However our list has its own way of implementing these methods. 37 00:02:36,040 --> 00:02:43,410 First is the IDE method which acts an element a specified index the specified next is something other 38 00:02:43,410 --> 00:02:45,130 than the last index. 39 00:02:45,210 --> 00:02:52,010 Then when we add an element all the elements following it will be shifted right by one position. 40 00:02:52,050 --> 00:02:58,500 So if there are an elements and you're adding an element at the zero position then all elements will 41 00:02:58,500 --> 00:03:05,090 be shifted right hence in the book is time complexity is linear. 42 00:03:05,130 --> 00:03:11,670 Similarly a real movement that removes an element from the specified index and in this case if an element 43 00:03:11,670 --> 00:03:17,190 is added more all the following elements will be shifted left by one position. 44 00:03:17,190 --> 00:03:22,980 So like in the case of I if the first element is removed then the verse gives complexity to bilinear 45 00:03:24,850 --> 00:03:30,930 unbonded it is because these two methods contains an index off both of these are search methods and 46 00:03:30,930 --> 00:03:38,010 contains method would return true if the specified element is present in the idlest while index off 47 00:03:38,010 --> 00:03:42,650 method returns the index number of the specified element in the other list. 48 00:03:42,780 --> 00:03:47,970 If the specified element is presumed and the artist on it will take an A minus one if the element is 49 00:03:47,970 --> 00:03:49,930 not present. 50 00:03:50,670 --> 00:03:54,870 Bought them at skandha other list from the beginning of that list. 51 00:03:54,970 --> 00:03:56,220 Unhandsome the bookcase. 52 00:03:56,220 --> 00:03:58,230 The complexity can be linear. 53 00:03:58,320 --> 00:04:01,790 That is when the specified element happens to be the last element in the list. 54 00:04:01,830 --> 00:04:09,810 Then the title is discovered and these methods use equals method to compare the input element bit each 55 00:04:09,810 --> 00:04:11,970 of the elements in the list. 56 00:04:11,970 --> 00:04:19,330 Recall that equals methods from the Object class and it can be overridden by any subclass. 57 00:04:19,860 --> 00:04:26,200 Not if there are frequent searches then go with the set implementation for example hash Sipkin such 58 00:04:26,200 --> 00:04:33,700 an element in constant time and after a few lessons that we'll be discussing Hasselt next is in the 59 00:04:33,870 --> 00:04:34,230 . 60 00:04:34,410 --> 00:04:39,420 And we know that to be most all the elements in the current list which are also present in the input 61 00:04:39,420 --> 00:04:47,340 collection and dumps off implementation the method invokes the contains method off the input collection 62 00:04:47,340 --> 00:04:51,140 object for each element in the list. 63 00:04:51,280 --> 00:04:58,300 No element is present then it uses that be movement of the other list to remove the element and dumps 64 00:04:58,320 --> 00:04:59,340 off complexity. 65 00:04:59,370 --> 00:05:06,660 It can be worse than quadratic and that's because it would be off and 42 dating all the elements in 66 00:05:06,660 --> 00:05:12,170 the current idlest then each contains invocation can be another. 67 00:05:12,170 --> 00:05:19,530 Often if the input collection object is a list if input collection object is one of the set implementations 68 00:05:20,040 --> 00:05:24,050 then it would be better as their contains method books faster. 69 00:05:24,120 --> 00:05:27,880 As discussed earlier on it would be an either or. 70 00:05:27,900 --> 00:05:34,920 And if the current element is removed from the list as it would result in Alimentarius so it can seriously 71 00:05:34,920 --> 00:05:36,050 affect performance. 72 00:05:36,090 --> 00:05:43,290 If you're dealing with large collections linguist on has said are better for one you will understand 73 00:05:43,290 --> 00:05:43,580 it. 74 00:05:43,590 --> 00:05:52,860 Once we covered those topics written on also has identical performance issues on here are some of the 75 00:05:52,860 --> 00:05:55,120 matters that run in constant time. 76 00:05:55,430 --> 00:06:02,250 Sit and get Minturn's run in constant time as an array is used as underlying data structure. 77 00:06:02,280 --> 00:06:05,840 We've discussed both iterator and mistreated or methods. 78 00:06:06,360 --> 00:06:07,470 So that's about it. 79 00:06:07,560 --> 00:06:10,760 And the next lesson will lead them off our list. 80 00:06:10,770 --> 00:06:11,240 Thank you