Data Structures: Arrays vs Linked Lists

See complete series on data structures here:
• Data structures
In this lesson we will compare arrays with linked lists based on various parameters and understand the cost of various operations with these data structures.
Lessons on big-oh notation can be found in these series on time complexity:
• Time Complexity Analysis

[@ronalddaugherty]

finally someone explaining this information like their talking to beginners not seasoned engineers

[@romir_07]

I have one doubt...why time complexity in adding an element at ith position in linked list is big-O(n)..it should be big-O(i)

[@ujjwaldixit4244]

@@romir_07 in worst case ith position can be even nth position therefore we consider it as O(n)

[@girirajrdx7277]

@@romir_07 we add an element at the end but to find which element is the end…we need to start from head and all the way to the end ad worst vase here is obviously o(n)

[@sameerjain7193]

@@romir_07 big o is used to denote the worst case, that is why n. which ever is the max!

[@chloetzpiano6548]

dude,you basically just saved me my whole semester studying with difficult lecture before,now all is ez

[@leixun]

*My takeaways:* *Computation cost: array vs linked list* 1. Cost of accessing an element 1:10: array O(1) and linked list O(n) 2. Memory usage 4:26 3. Cost of inserting/deleting an element 8:30: array O(n) and linked list O(n) 4. Easy to use 11:35: array is easier than linked list

[@Dark._phoenix._]

Are you Chinese?👀

[@mycodeschool]

Hi Prasanth, Thanks for your kind words. We will first complete some of the existing playlists and then we will move to OOP concepts. We are building a mechanism to track video requests on our website. Anyway, for now, your request is in queue.

[@mcytc]

Time complexity is always the worst case scenario, which in this case is adding an element at the beginning of the array, requiring all elements to shift.

[@gta6515]

where have you explained oops?

[@romir_07]

I have one doubt...why time complexity in adding an element at ith position in linked list is big-O(n)..it should be big-O(i)

[@drakolubez6592]

@@romir_07 i is a constant, you need to shift (n-i) elements to right. This means the time complexity id O(n-1) , which is same as O(n)

[@ahmed_raaphat]

What a loss! :( :(

[@renon3359]

The way you explain, I could listen to these videos for hours and not get bored. Absolutely mindblowing content man, keep doing the good work.

[@shreyjha1974]

As a 9th grader I really appreciate how you are using pictures and analogies to explain what can be confusing concepts at first.

[@alirezaghodsipoor2239]

I can watch your videos as a movie and not get bored :) Awesome!

[@danielli8042]

nice layout and subtitles. I really like the video. very professional. keep it up :)

[@AnonymousCoder7]

Best of the Developers who knew about these Legends already raise you hand pls. ✌🏻🙌🏻

[@stephen6072]

Good videos, makes more sense than what was taught in my data structures course here in the U.S.

[@akshayarekhasubramaniyan9537]

srsly, i don't know your name and who you are but for now you are a god to me. thank you so much. i longed so badly for learning this, now i understood this

[@WillsonMock]

another really great video - i love the way you teach and how clearly you explain the concepts. i find this useful even when i'm not trying to implement in C / C++

[@md-ayaz]

The next "Khan Academy" but this time from India.

[@adarshtodi1158]

really??

[@danilo2735]

unfortunately, he died before achieve such a thing

[@mohammedfawaz289]

@@danilo2735 He did't die, but a friend of him.

[@danilo2735]

@@mohammedfawaz289 go to they facebook and you'll see the post

[@mohammedfawaz289]

@@danilo2735 Yea I saw it years ago, but I think that was his friend, not the one who speak in the video.

[@bhavincbarot]

Excellent. Very simplified and easy to understand for first time learners as well.

[@moha4998]

Learning DSA Now in 2021 and still so Helpful Harsha left a legacy behind. RIP

[@shahriarmim4696]

Dynamic Array that adjusts the size by increasing when it got exhausted to its previous maximum length, is called ArrayList in Java

[@jery7082]

Inserting node at end of linked list would be constant time if we have tail pointer!

[@nurilha]

But why is there no tail pointer?

[@dilloncote7551]

@@nurilha Tail pointers are optional and can be made the same way as a head pointer. He just didnt use it in the video.

[@pranavganorkar2379]

Excellent Way of Explaining Programming Concepts... Great Work Sir !!!

[@digambaringale5806]

It's so geat even now when there are lots of videos on this topic. Good job...

[@animeshnayan1]

part 2.. contd...we often say that our machine is 32-bit or 64 bit. On a 32-bit machine, there are 32 bits on address bus that is used to transport address of a memory to processor. So, maximum number of addresses can be 2^32. On 64-bit architecture, maximum number of addresses can be 2^64. Pointers size depends upon whether we are compiling for 32 bit architecture or 64 bit architecture. Typically, we compile for 32 bit. So that's why its 4 bytes.

[@jaiderariza1292]

The cost of inserting an element at the end 10:24 could be a constant O(1) if you use doubly linked list :)

[@maxima-4270]

love your tutorials. Wish you guys continued no matter what.

[@ramudu1]

Wonderful series of tutorials ..! only 10% of the videos in youtube makes sense and this is one of them. Good job mycodeschool. It would be good if you could cover some of the OOPS and virtual functions.

[@radhiekanagpal6257]

Easy to understand and quite precise in flow of learning. Amazed.

[@sourabhd99]

Best lectures I could have seen.. Regretting if I had got such lessons in my engineering schools :(

[@yashkiratsingh9683]

When insetring an element at the end of a linked list why we will be needed to traverse whole memory. It can be done by changing the last pointer.

[@mistersmith6752]

first you need to figure out which one is last - for it you traverse from the start :)

[@monishkumardurairaj3038]

Hi @@mistersmith6752.can we not use a static variable inside the class of the linked list to store the last address..???????

[@mistersmith6752]

@@monishkumardurairaj3038 Im not really sure what you are asking but you must understand that linked list is already an established data structure and if you want to change something you can implement a new class that does whatever you want , most likely it will be ineffective , but if you are a great programmer maybe you will create something usefull :) If a particular data structure is not working in some case just use another.

[@monishkumardurairaj3038]

@@mistersmith6752 what i am asking is suppose if we have a struct named list inside which if you have two variables one for storing value and another one(pointer) for storing address. why cant we have a third variable or pointer which may be static to store the last address of the list. since it is static the pointer can only be created by one instance and can be used by all the instances. eg: struct node { int value; node* next; static node* last; }

[@monishkumardurairaj3038]

@@mistersmith6752 i understood what i have asked is not possible in c.since the static variable cannot be declared inside a struct. so this cannot be done... thanks for the help .. note: but in c++ what i have asked previously is possible i guess.

[@rahilshah4098]

For Link List, By keeping two pointers one for Head and another for Tail of the List, inserting Element at the End will also of O(1)....

[@zerobytesfound]

Adding element to the end of a Linked List doesn't need to be O(N) if you store and control the position of the last element, like you do with your head element, and like you do on the array It could be O(1)

[@stopthecap8810]

you mean if you stored the position of the last node as another pointer variable in the struct definition? that could work but feels complicated

[@shubhamsabale8613]

nice online series of video of data structures i ever seen on u tube, mechanical engineer like me learn concepts clearly

[@sierrabravo4432]

Wish you would make your videos in Java, nonetheless you are the best on KZbin.

[@decreer4567]

Derrick Banas does this in Java

[@patrasculucian2403]

True but his tutorials are not for beginners

[@decreer4567]

A beginner shouldn't be on data structures and algorithms anyway. They still have to learn basic syntax.

[@patrasculucian2403]

The person who knows the syntax without knowing data structures is a beginner on data structures. That's what I meant. Derek's videos are much better to watch after you learn the basics from other who teaches slower. Then, Derek's videos are going to be awesome, you will refresh your memory, practice and master it at a hell of a fast pace.

[@decreer4567]

Are you sure because his videos are pretty slow? I normally turn it up to around 2X speed with how slow he goes sometimes

[@marymoore5043]

Thank you, excellent explanation of cost and memory use.

[@sundararajannarasiman5613]

Superb explanation. Programming and software engineering made simple.

[@piyushhibare]

excellent explaining

[@ronaldabellano5643]

I dont get the Memory requirements part. How does Linked List consume lot less memory if it uses more memory because of its pointer?

[@amarbhardwaj7963]

Because there is no unused memory in linked list.

[@akhiljain1695]

These videos are really helpful. You are doing a great job.!!!!! Please keep making more such videos.

[@animeshnayan1]

Pointers will always take same number of bytes. Pointers store the address of a particular byte in memory. Address of data is the address of starting byte. We look at rest of the bytes in the data using arithmetic. Size of pointer depends upon total addressable bytes in memory and not upon what data we are pointing to. With 32 bits, we can have 2^32 possible addresses. contd ...

[@anondoggo]

So tremendously helpful. Thank you so much!

[@rajankit749]

Awesome !! What a way of EXPLAINING THINGS .... +LEGIT

[@jyotinpankaj]

Thanks mycodeschool, no one ever explained concept like this.

[@VS-ey2lf]

mycodeschool you're the best

[@aaronbalthaser]

Why is adding a node to the end of the list O(n)? If you maintain a tail you can add nodes to the list in constant time no different than added to the head. I have seen many implementations with both head and tail. Is a linked list with a tail not a valid implementation?

[@nezarfadle7715]

You are absolutely right :)

[@SumanChakrabarti]

This is honestly better than watching the MIT presentations. Thank you!

[@usama57926]

thank u sir for such an amazing playlist

[@sufferererik]

this is so informative omg , thanks alot

[@EchoVids2u]

Correction: time complexity for inserting at the end of a linked list is O(1) if you have a tail pointer pointing to the last node of the list. Example (in Python): class Node: def __init__(self, d): self.data = d self.next = None class LinkedList: def __init__(self, d): self.head = Node(d) # Head stays the same self.tail = self.head # Tail points to ending Node def append(self, d): self.tail.next = Node(d) # NEW NODE self.tail = self.tail.next

[@yerotuavinash1162]

i think that your concept works on Double linked list

[@october3518]

The thing is ....I get bored easily lol but he actually made me interested and ask why this like this.

[@muhammedhussein928]

why the time complexity for inserting an element at the end of linked list is O(n) i think it should be o(1) because we just make the Null to the inserted element then we add the address of the element of last element to the previous element !! and Thanks for these Awesome Videos

[@plemyk]

Muhammed Hussein Because you need to start from the address of the head node to arrive subsequently to the exit node.We have no knowledge of the last node address,without first having been directed by the head.What you suggest is like trying to arrive to any destination on a map,but having no awareness of where you are.How can you arrive to your destination,if you have no point of reference.

[@muhammedhussein928]

thanks for this awesome explanation :) plemyk

[@minaraouf1051]

Really very good explanation. But there is a small mistake in this video and the video previous videos U mentioned that inserting an element in the array will have a cost of O(n), that's quite not right. Because it's Big-Theta(n) NOT Big_Oh(n). This is because you may insert an element in index and do the shifting staff for number of iterations less than the total length of the array. Let me show an example: Assume that u have array of 10 Elements, U only use the first 3 elements. Then you need to add an element in the first index, so you will shift the elements three times only (NOT 10 times). If you like to use the Big-Oh lower bound, then it will be O(m), & (m

[@sudhakarjha75]

We talk about worst case right???

[@tanmaykumar6856]

he has the best playlist on linked list

[@amuralikrishna22]

The way you are teaching is superb and do you have pdf version or any other format notes for quick revise.thanks...;

[@TravisFont]

It's all about allocation. Huge data set or small data set.

[@msKuchifai]

Your videos are awesome! I learnt a lot from them... I have a question. At 6:54 min at your video, the memory requirement section... shouldn't data and pointer variable be the same number of bytes? in your example, the data is 16 bytes but the pointer variable only 4bytes. Please clarify, thanks.

[@manavmohata1240]

size of pointer variable will always be same for all data types. the data type that we specify for pointers denote the data type of the variable whose address will be stored in the pointer variable.

[@shubhamdey9922]

really awesome... knowing the things dosent matter much fr a teacher but explaning it does.. nd myschool did it...

[@asdfghjkl1770]

amazing, i am preparing for googles kickstart. btw im 15 and python programmer ,web developer.

[@abhishekdhyade7500]

Made ppt using your content xD. Thank you

[@nitintomar7534]

You are champ man ! Nicely explained

[@dhruvgarg722]

awesome!! really well explained, but what about dynamic array or vector in c++

[@mightguy167]

crystal clear!

[@Raksh6]

Great videos! Keep up the good work and Thank you!

[@ashwinkarthikeyan1829]

All these videos on data structures are very useful. Thanks a lot. But can you upload videos of OOP using JAVA too please.

[@SamvitAgarwal]

Hey this was a great video! Since I use Python, which uses dynamic arrays(arrayLists) by default, could you explain how exactly these work and the time/space complexity for these? Thanks

[@abdelghanidraoui781]

Awesome course thanks for sharing !

[@varunkamani2528]

your channel is great..keep it up!

[@onurucar1112]

not all heroes wear capes! tysm

[@ruprajroy628]

Instead of dynamically memory allocation why arrays are of fixed size

[@shermanjoke]

shouldn't linked lists consume more memory than arrays? in each node, there will be memory allocated for data AND the link, whereas in arrays, there will only be memory allocated for data.

[@Mrsarchanaharish]

+Sherman Hung Rightly said - he compares 7 elements on an array vs 4 elements on a linked list.

[@patrasculucian2403]

- In an array you will always have empty unallocated memory - Let's assume that, in an array, we store big data of 16 bytes / element - if we have 10 empty elements in the array - 16*10 = 160 unallocated bytes in memory - In linked lists this will not be the case - We will have 20 bytes / element - the address of the next element is stored in an integer of 4 bytes - thus 16 bytes + 4 bytes - But we will never have unallocated memory. So it's an overall win for Linked Lists

[@_robo]

Yeah but why would you ever have empty elements in a dynamic array.

[@abhisheksinghjina1677]

i did not understand that part that a link list will take less memory as compared to that of an array.. please explain!!

[@piyushpahwa7897]

In the case of complex high size data, the fact that you will use exactly as many memory blocks as you need in the linked list than in case of the array is dominating over the fact that each memory block in the linked list contains an extra variable (of type node*) of size 4 bytes(which is pretty less in comparison to size of complex data part).

[@Alpha777beta]

awesome explanation

[@msKuchifai]

Thanks, that makes a lot of sense...also thanks for the prompt response! :)

[@sltest5622]

Thank you very much for all the videos!! I have a question, in the linked list, inserting an element at the end and at ith position should be O(1), isn't it? Because only pointers need to be changed..? Only access to elements at the end and at ith position would be O(n)?

[@vundigalarohit8654]

Your explanation is awesome man ! Why did u stopped posting videos ?

[@trenlop931]

11:46

[@sohelurrahman6565]

best lecture.... thankas

[@nic0lasc]

thank you very much! perfectly described!

[@VenkataraghavanRamasubbu]

Thank you for the great explanation!! I'd a doubt on linked list, when we insert a data at the end of linked list or in between linked list the time consumption is proportional to O(n). I thought however we're going to add it and just have to change the address of last one O(1). but we've to iterate from the first to find the tail node address so it comes to O(n) am I right?

[@sanjaychakrabortyaworldofc6953]

Nice lecture

[@azkamobin]

really great video!!!

[@dhaneshpt8641]

Thank you sir.

[@pawannegi1135]

good explanation ...

[@ahmedzahid8354]

Thanks sir well done job

[@shahrukhkhan31091]

Why do we always write as Struct Node { int data; Node* next; } and not as Struct Node { int data; int* next; } What difference does this make?

[@Opacity5]

exactly my question

[@manishrana3596]

i need that answer

[@MohitSharma-lz1nc]

(1)Node* next basically means a pointer next to a type of Struct Node. (2) int* next means a pointer next to a type int. The second implementation is completely wrong as we need a pointer to a next node(comprising of data and next pointer) and not an int type.

[@manishrana3596]

@@MohitSharma-lz1nc but we need that pointer just to store the address right, so int should work🤔🤔🤔

[@MohitSharma-lz1nc]

The data type of a pointer is needed in two situations: A)Deferencing the pointer B)Pointer arithmetic The address always comes in 4 bytes when we dereference using (.) or (->) then we are referencing to a memory block of 1)for Node* next - 8bytes( 4 bytes for int data + 4 bytes for pointer Node *) and in second case 2)for int* next - 4bytes(only 4 bytes either for int data or int* and neglecting the other part) For eg: Consider we have Node A and a pointer to node ie Node *B then I want A->next = B ; // next pointer pointing to B node . If we use int* next then do you think it is possible without errors?? So surely we will have issues in the above implementation. for more explanation see the below link : stackoverflow.com/questions/9802585/why-data-type-is-needed-in-pointer-declaration#

[@sakshisoni4151]

Can someone tell me that these videos are helpful for the gate (for data structure) preparation or not?

[@ashutoshpatil26]

yes its helpful

[@kuba1366]

i think deleting at the end of array is O(1), not O(n) so deleting times are not the same

[@LarissaFord]

I thought arrays had O(n) and not O(1)? because isn't big-O concerned with worst case scenarios where we may have to iterate through the entire array before finding our element, and would thus need n-time for an array of size n? I thought this because I understood hash tables to be special because they had a faster run-time than arrays, having a general case of O(1) run-time. Am I mistaken somewhere in there? Thanks for the amazing lecture!

[@LarissaFord]

oh wait, it would be constant time if we knew ahead of time where in the array (which index) an element is found. I think my question is still valid in terms of finding an element, but is that not what big-O is concerned with? is big-O concerned only with look up for a particular known element? *EDIT* gosh, I missed the part that said "Cost of accessing an element". this all makes sense now.

[@elimarpineda6496]

thank you so much for you greattttttt work!!!!!

[@shubhamjagtap108]

Please comeback and add more

[@nicholasgonzalez]

Thanks very good video!

[@cychou1845]

I now know why google hires bunches of Indian CS engineers...

[@Mercio2]

Very nice!

[@siayush]

well explained

[@akshupatel3092]

If you have a tail reference on the LinkedList would insertion at the end be O(1) ??

[@NitishKumarTutorials]

yes, right :) Data Structure Best Tutorial Check here for free kzbin.info/aero/PLbRk-vKGcVtbyctZWP9SUYewwUfx75CpZ

[@siddhantmodi7085]

Do pointers of Linked list needs extra memory to store them?

[@nikhilgaikwad3014]

Nice explains

[@monishkumardurairaj3038]

Kindly any one clarify my doubts.. in linked list why to traverse the entire list inorder to add the new node at the end. Instead just maintain a static variable inside the linked list class that will always hold the end address of the list. inadditon why to have the head variable to store the starting address can we not just access the starting address of the list which is gonna be the same. eventhough if you want to add the node at the beginning of the list you just have to change the address of the list to the new node created at the beginning . why waste 4 byte variable head for storing starting address?????????????

[@sonalipurohit6362]

Can you make a video on how to calculate address of 3-d array?

[@suprijasirikonda2065]

Y is d complexity O(n) for deleting d element at d end of an array (when it is full) ?

[@architatrey5018]

Sir make a video on unrolled link lists

[@tareqelgafy1826]

great ! Thank you

[@kondurubharath8279]

does a pointer variable require 4 bytes here..?? I heard from some sources that any pointer variable irrespective of the data type consumes 8 bytes..isnt this correct..???

[@AdityaVermaopenheartedme]

hi what about self referential pointers in a structure what amount of memory would they take?