See we cannot say that array is better or linked list is better because it all depends on the requirements. Maybe in one type of requirement array is good to use and maybe in another type of requirement it is good to use linked list data structure. So it all depends on the requirements plus it depends on the size of the data you are dealing with.
Or another factor is it also depends on which. type of operation you want to perform frequently with your data whether you want to access the data very frequently whether you are going to insert some another another data very frequently or you are going to delete some data from your existing data fine so which type of operation you are going to perform frequently with your data right so it all depends on many factors in this video we are going to compare all the factors where to use array and where it is good to use array and where it is good to use linked list or you can say in this video we are going to compare array and linked list or we are going to talk about advantages and drawbacks of arrays and linked list right so now the first factor is cost of accessing the element from the data structure see both are data structure arrays also data structure the linked list is also a data structure so first factor is cost of accessing in element first of all we are going to talk about array see how we are going to represent an array see so this is how we are going to represent an array suppose we have some elements here 6 7 0 1 right and you want to access some data from the array now as we know random access is possible in the area or you can say direct access is possible if you know the base address of the array then you can easily compute address of any element in the array in constant time right and the formula is suppose the base address for this is 100 for integer it is going to take 4 bytes it is 104 108 112 and 116 so you want to access this data indexes to simply how you will access simply write a of 2 suppose array name is a array name and index value how the compiler is going to compute base address plus i value is 2 into the size of the data type integer is going to take 4 bytes into 4 that is 108 so this is 108 so directly you can access this data by simply writing this thing so it is going to take constant time right you want to access this data this data or this data it does not depends on the number of elements in the array it is going to take constant time that is order of 1 only now in case of linked list how we are going to represent a linked list see so this is how we are going to represent a linked list linked list is having only three nodes now if you want to access this one from the linked list then you cannot directly go here because in linked list only sequential access is possible right because see these nodes are not in contiguous blocks in array the data is stored in contiguous block in you know in consecutive locations but here these are stored at random positions right so this is the linked list we have the head pointer head pointer is having thousand so using this address we can reach to here to the first node right now check out in the first node this is the address part see I have already discussed all the fundamentals about linked list in the previous video you can check out that video first of all right so now the address is 2000 Now you can go here at this node. Now here check out the address part. Here we have 3000. Now you can go to 3000 at this address and now you can access this one.
And now suppose in linked list there are 10 nodes and if you want to access the 10th node, then you have to traverse all the previous node first of all, then you can reach to that node only. So accessing of element depends on the number of node in the linked list, right? If you want to access this. data first then obviously then you can directly access if the head node addresses this one and in the first node only you found the data right if you want to access the in average case if you want to access the middle element then you have to traverse how many nodes and by two nodes right after that you can reach to the that middle node in average case so it also depends on the n the number of elements number of nodes in the linked list. proportional to number of nodes in the linked list.
So now the cost to access the data or you can say the time complexity is what? Order of n. In array it is order of 1. So, if on your data if you want to perform this accessing operation very frequently. So, obviously it is better to use this array rather than linked list. Fine.
Now, second factor is what memory requirement or you can. can say memory requirement plus memory utilization we we are discussing both the factors see array is what a fixed size data structure generally we we have to declare we have to give the size of the array at a declaration time only we cannot change it at runtime fine so what we generally do we give the maximum limit of the array when we declare the array then we declare what int a and size is 100 fine maybe we are using we are storing only 10 elements in there or 20 elements in there but at starting they have declared what size for 10 integers fine so that is what wastage of memory so in this array memory utilization is ineffective you can say fine but linked list is what dynamic size there we don't have to give the size at starting if you want to create another node at runtime only you create that node there is no wastage of space so in that case you can say in linked list memory utilizing is very efficient fine now if we talk about memory requirement see although memory requirement in array is less rather than linked list how see now see suppose we have declared an array of size 7 right although we are we can take maximum limit 50 or 100 but i'm going to take a simple example here a small example array size is 7 but actually i have stored only three integers so this is what unused space why so because for further maybe if you want to insert another data you can insert this array because array is fixed size so in starting only we declare maximum limit right so now in this case how much memory has been allocated to this array for seven elements are there and each element is going to get four bytes that is 28 bytes is to be allocated but actually how much memory is in use only one two and three elements three into four that is only 12 bytes this is what unused space now in case of linked list if you want to store only three elements then you will create only three nodes no need to give the size of the linked list in advance right at run time only you are going to create a node fine so now see this is the linked list having three nodes only so the memory requirement is how much see in the linked list this node is going to take take some extra space for storing this pointer variable. In 32 bit compiler, the pointer variable, the size of this is about 4 bytes. In 64 bit compiler, it is going to take 8 bytes, right? So here I am taking 4 bytes for storing the pointer variable.
So total for one node, total bytes would be 8, 4 for integer and 4 for storing this pointer variable or the set this means 8 byte. So total size is 8 into to 3 for 3 nodes that is 24 bytes fine and here 28 bytes right now suppose you want to insert one extra node sorry one extra element in the array simply you can insert here suppose I have inserted 5 here Fine, but see the size is what 28 bytes. No need to increase the size because at starting only we have give the maximum limit. But now in case of length list, if you want to create another node, then the size.
this size would be increased 24 plus 8 bytes for one another node to store this 5. So now the total would be 24 plus 8 byte for storing this 5. suppose here I want to insert one extra node 5 and you want to link here suppose address is 4000 so here we are going to store 4000 so now the total size is you can say 8 into 4 or 24 in plus 8 that is 32 bytes Now you can check here only 28 bytes here 32 bytes now if you want to insert one another node in this then plus 8 means 32 plus 8 that is 40 bytes but here if you want to insert one extra element then simply here you can insert no need to increase this size in 28 bytes only you can insert this one right so this is why I am saying that memory requirement in case of array is less than linked list in 28 bytes only you can store how many elements 7 elements maximum but But in this case, if you want to insert, if you want to create seven nodes, then this memory requirement would be seven into eight, that is 56 bytes, right? And here only 28 bytes. But memory utilization, see memory requirement and utilization both are different factors. Memory requirement is less in array, more in linked list.
But memory utilization is efficient in linked list. But it is not so much efficient in array. Because here wastage of space is a major drawback in array.
Fine. Now second case is, here we are taking integer data. fine so it is going to take 4 bytes now suppose we are going to take a complex data type that is going to take 16 bytes to store right so now if 16 bytes is to be taken then 16 into how much size is to be allocated for this array for 7 elements 16 into 7 that is 1 1 2 bytes Fine and we are going to store only suppose three elements. Fine now in case of linked list if you want to create only three nodes not four nodes only three nodes only three nodes.
Fine and for one node size is. what 16 for this data type because we are going to take a complex data type of 16 bytes 16 plus 4 for storing the address 20 each node is going to take 20 bytes so 3 into 20 that is only 80 bytes now see this is very efficient this is 80 bytes and here we have to allocate how many bytes one one two bytes so you can say if uh the size of data you are going to insert is large or you are going to deal with complex data type then it is better to use linked list data structure because linked list in that case is going to consume a you know very less memory than this array fine but it also depends maybe here you are declaring the size 7 and you have you are storing 7 elements in the array so in one one two bytes only you are using the complete one one two bytes block there is no wastage of space and here if you want to create seven nodes then seven into 20 then 140 bytes would be required and here only one one two bytes would be required so it all depends how much unused space you are taking in array or you are using the complete space you have declared in the array it depends on many factors fine but generally we say that memory utilization in linked list is if very efficient than this array and memory requirement in array is less and memory requirement in linked list is more now third factor is cost of insert insertion and deletion so first of all we'll discuss what is cost of insertion three cases can be there at beginning you can insert at end you insert and at any ith position you want to insert so now in array if sorted array is there then if you want to insert at the end suppose first of all you are taking at the end so directly you can insert here in the array because random access is possible you can directly calculate this address compiler can directly calculate this address using that formula and simply insert value here suppose i want to insert 4 here right so at the end it is going to take order of 1 constant time But if you want to insert here in the beginning of the array, then how you will insert? You have to shift all the elements right side. If you want to insert here, then you have to shift 4 here, then 0, then 7, then 6 and after that you can insert here. See this thing how to insert data in array we have already discussed.
So you can check out that video. Fine. So you have to shift how many elements? N elements. So it depends on the number of elements.
So it is going to take order of N. If you want. want to insert at beginning the cost is order of n if you want to insert suppose at middle at any ith position or you can say in average case this is the best case sorry this is the best case this is the worst case in average case if you want to insert in the middle of the array then you have to shift how many elements and by two elements fine so obviously it depends it is proportional to that number of elements in the array so in at ith position also we are going to take order of n or you can say we have already discussed theta n minus p p is the position where you want to insert it depends on the position right so now in case of linked list when you want to insert at beginning then here you want to insert this is the first node here suppose i want to insert one another node having value 4 right and suppose address of this node is in memory address 4000 has been allocated to this node you simply have to do what you simply have to adjust these links how you will insert see Here in this node at the beginning if you want to insert then here at the address part of this node you will store address of this node 1000. 1000 you are going to store here. Fine.
So you can say this is now going to link here. And in the head node you are going to store address of this one that is 4000. Now head is going to point here. This is the first node. Right. So at beginning it is going to take what?
Constant time. So at beginning it is going to take order of. 1 in case of linked list now at end here here after this if you want to insert then you cannot directly go there because in linked list only sequential access is possible here you can directly go there that is why it is order of 1 but here you have to traverse first of all suppose 1 at beginning in linked list it is order of 1 right Now suppose if you want to insert a node having value 5 at the end and suppose the address is 5000. You cannot directly insert here.
Because when you are writing a program then we are having only this head value, the head pointer value that is 4000. So here where we are we can reach to this location 4000. Now check out. the address part here we have 1000 so we can reach to this node now here in the address part we have 2000 so we can reach here here is 3000 so we can reach at 3000 address now we have reached at the end of the list now you can insert this node here how you will insert this 5000 would be you have to simply adjust the links 5000 would be stored here now you can see this this node is this node is going to point here fine and here simply you will store null we will discuss these operations in detail here i am just giving you an overview so you have to traverse the complete list list right so it depends on the number of nodes in the list that is why if you want to insert at the end then it is going to take order of n you have to traverse the complete list to reach till end right and suppose if you want to insert any position in average case suppose you want to insert at middle position then also you have to traverse how many nodes n by two nodes you have to reach till there by traversing n by two nodes so it is proportional to number of elements only so you can say in order in this bigger notation you can say it is order of n in average case also fine now how to delete the cost of deletion is same the cost of insertion if you want to delete a data from the end of the array then directly you can reach here and you can delete the data it is going to take order of n if you want to delete from beginning then suppose if I want to delete the six then you have to shift shift 7 here 0 here and 6 4 here all the elements you have to shift fine so this is going to take order of n it depends on how many elements are there in the array if you want to insert if you want to delete from any position or you can say in average case if you want to delete from the middle position then you have to shift how many elements and by two elements to the left side so it depends on or you can say it is proportional to number of elements elements in the array so it is going to take order of n fine in this case also if you want to delete from starting then simply delete this and what you have to do you have to adjust this this head only here if you want to delete this one in head you are going to store thousand only fine so it is going to take order of one but from the end if you want to delete then you cannot directly delete this five why so because only sequential access is possible in linked list So to reach till this node you have to traverse the complete list. After that you can delete this one.
Fine. So it depends on number of elements. You have to traverse n elements after that you can delete the last node.
So at the end if you want to delete then it is going to take order of n time. From any position if you want to delete. Suppose in average case you want to delete from the middle of the linked list.
Then you have to reach till middle of the linked list. Till that node you have to traverse how many nodes? and by two nodes right so that is also proportional to number of elements in the list so that is why in average case also or from any position also it is going to take order of n so this would be same as in case of in case of insertion fine now next point is easy to use which one is easy to use array or linked list obviously we will say array is easy to use then linked list fine next factor you can say searching operations. So in array linear and binary search both are possible but in linked list only linear search is possible. Right?
So these are some major factors on which we have compared array and linked list. you are asked to write down difference between array and linked list i can i guess you can easily write down the difference now or you can also write down the advantages of array and disadvantages of array as well as advantages and drawbacks of linked list based on these factors right so from next video we are going to see the major operations performed on linked list with their code traversal insertion and deletion so i'll see you in the next video till then bye take care