ARRAYLIST VS LINKEDLIST

In this one, we explore how ArrayLists and LinkedLists works at memory level and how scripting languages handle their "arrays."
Sign Up to CodeCrafters:
app.codecrafters.io/join?via=...
Follow me on twitter:
/ coredumpped
Follow me on Github:
github.com/jdvillal
Questions and business contact:
[e-mail]

[@scheimong]

20:34 Fuck I need that card in my wallet

[@nxthingbutv0id958]

Me too, I hope he sells it as merch one day

[@naautilus0]

best animation quality yet, the pointer hell is somehow very understandable

[@MrPilotStunts]

This is the single best video on the topic ever! When i was studying cs, our prof didn't even try explain how data is stored, he just moved on to using pointers, i had no previous experience with them and was like wtf are pointers. You put it all flawlessly into words AND animations, and a picture is worth a thousand words. Great video that brings so much clarity, every cs undergrad needs to see this. Thanks a lot!

[@AapoAlas]

Nitpick: JavaScript engines typically do implement arrays as continuous blocks of data, and generally setting just one item at index 10k will then allocate up to that number (or more). They just have to pessimise the array for the holes in it.

[@wil-fri]

I remember writing a filter and it was returning null items, you have to be very careful with JS

[@about2mount]

They use C++ struct arrays, not normal arrays, class arrays or vectors.

[@ezsnova]

baby wake up core dumped just uploaded

[@yumyum7196]

🤣lmao seriously tho

[@ivankudinov4153]

I prefer 'baby wake up core dumped'

[@giankadev3026]

What a spectacular video, I'm just creating my own programming language and this fits me like a glove.

[@stevebrownlee6141]

I absolutely adore JavaScript, but concurrently adore these videos. The quality is capital. I aspire to produce quality material like this.

[@rubenvanderark4960]

Just found your channel! Really happy to see you just uploaded. I love your intuitive visuals to explain all sorts of mechanics

[@seid44]

absolutely one of the best channels out there right now. u go even more indepth than some of my college classes and make it seem easy. big ups bro

[@michaelciccotosto-camp4033]

I remember really struggling with these sorts of topics when I was at university. These are some of the best explanations for OS/low-level programming concepts I've ever come across!

[@dzuchun]

yes, I am to watch a livestream of yours solving CodeCrafters challenges Jon had done the same a week ago with Git, and I watched through the entire thing. that was indeed really interesting, and I'd like to solve these myself too 😊

[@Firestorm-tq7fy]

Waited for this video after the previous teaser. Ur videos are the most accurate on the subject there are

[@biasedbit]

Incredible work with these videos so far. Hitting all the key points at just the right level of detail. The animation work is just... * chef's kiss * Keep it up 🙌

[@lukasaudir8]

The quality of this channel is amazing, I wish you all the success and I'm excited to see many more interesting and educative videos like yours, you have a good way of getting your point across... I'm a

[@loic1665]

I learn so much deim your videos!! Thanks a lot !!! I'm waiting for the next one!

[@code-monet9468]

One of the best videos I ever watched in my life

[@digggggg898]

Love the quality of the videos I will recommend other people in my class to them because they’re concise and easy to understand. Keep it up!

[@sameerakhatoon9508]

you've mentioned about thinking to solve codecrafters challenges on stream. Yes please!

[@deathdogg0]

I wasn't able to leave a comment on your post from yesterday but I guessed arrays and I was right! I love these deep dives

[@knofi7052]

George, your videos are really awesome! I already knew all these concepts but I have never seen them better explained. Anyway, I love C and Assembler because they are teaching how computers work...😊

[@Blezerker]

Javascript bashing ✅ Engaging and interesting systems programming content ✅ Funny retorts for armchair programmers ✅ Im so glad i found this channel early and subbed

[@eddyvytime]

this content is pure gold!

[@Albert-nc1rj]

Amazing as always Would love to watch those streams

[@azadomer5273]

I recommend everyone starting to understand the data structure to subscribe this channel and save this video, well done very nicely demonstrated!

[@user-do1eg2kt3v]

Very good video, this is the kind of teaching that works for me so thank you

[@mariospada00]

Thank you so much for this video, excellent explaination! I have a question, though: as you showed, in languages like Rust, besides specifying the array's size, it's also necessary to specify the data type (integer, float, etc...), and from what I understood, it's because this way the compiler already knows how many bytes to read for each element. However, at 19:45, in the case of Python, how does the interpreter know if, once a pointer is dereferenced, the retrieved object is an integer, a string, or another element with indefinite length? Because according to your (beautiful) animation it seems like every object has it's own specific size.

[@CoreDumpped]

Interpreters attach 'tags' to values in memory, so when the value is needed, it first reads the tag to identify the type of the value and know how many bytes to read. The answer is explained in my video: The size of your variables matters.

[@diogenes_of_sinope]

Great videos, thank you for your efforts!

[@Hersonrock12]

I did try to use the *void pointer once! It was hilarious when you mentioned it

[@JamyGolden]

Wow, so informative, thanks so much. I’d watch a live coding session.

[@ejon]

This channel is about to blow up🎉

[@ZeroUm_]

I've been working with Java for almost 20 years, and I don't think I've ever thought about what happens when you remove an element from an ArrayList. Thanks for the eye opener.

[@SoniaHamiltonSnowfrog]

Me too, but with Go. Now I understand the motivation for slices vs arrays

[@pedroivog.s.6870]

Hi, the video has been pretty interesting so far. Just a suggestion: please put the link to the previous videos you recommended. Otherwise, in a year or so, it will be much harder to find. Unfortunately, KZbin showed exactly where the current video is in the channel's timeline.

[@sergeylypko5817]

The content is great. Would be interesting to see your overviews about how rust's compiler works and about compilers theory in general. As well as interpreters actually.

[@SPimentaTV]

What a fantastic video! Now all I want is to program in Assembly to learn how really an computer works, and to optimize all those inefficiencies those languages introduce! Great presentation 👌

[@nexby323]

You are very good please continue like that and I will be happy if you touch on the assembly perspective of the things too 😄

[@ShubhanshuMishra]

You are back🎉

[@labCmais135]

Yes , really good

[@silloo2072]

Heeeesss baackkk

[@samaellovecraft]

Thanks for the knowledge!

[@D0Samp]

I have yet to see the combination of a linked list and array list in the wild that I was taught in my AlgoDat course and never again afterwards. It stored the data in a big array that can be relocated to grow, but also a separate mapping from indexes to array offsets. That sounds like a linked list (just with array indexes instead of full pointers) that enforces some form of memory coherence for both list nodes and data. As far as I know, you can refine this concept to a linked list of array slices, which is how text editors support efficient cutting and pasting of text.

[@kienha9036]

About 17:45, I'm no great expert on system programming, but the severity of data locality is unlikely severe. The cost of pointer-based array instead of a template array resides in the unpredictable position of object allocation, which confuse the CPU cache prefetcher. In reality, most workload allocates objects (as each object in the containing array) closely or in a predictable fashion, so prefetching works adequately well. And of course, pointers are still grouped together as always. For example, if we add items to a list in a loop, it is trivial for the CPU prefetcher to assume the next approriate location. Hotspot specifically, each thread has its own thread heap, so as long as the array/list is not multithreaded (which is unlikely), the pattern will be maintained. Moreover, with the nature of GC, the compacting phase will very likely move spreaded objects all over the heap to a single location, both avoiding fragmentation and maintaining the fetch pattern. There are exceptions, like if a BaseType array could contain both DerivativeType1 and DerivativeType2 with completely different object layout (only possible with reference-based array), then it's difficult for the CPU to make a good sense of the fetch pattern, which will likely suffer from "data locality". But as always, the template array would also suffer from this, so it's rather an unfortunate universal technical difficulty.

[@diyathkumara2443]

The early bird gets the typo

[@CoreDumpped]

Fixed, thanks :D

[@diyathkumara2443]

@CoreDumpped Thank you for all the effort you put into crafting explanations + animations even a newbie like me can grasp so easily 🙏

[@weakspirit_]

i love that little departure to interpreted language land

[@bartekabuz855]

I would have never suspected that an IT person can actually explain something well enough for people to understand. Good job buddy

[@tonchozhelev]

The reason why most programmers are bad at explaining things, is that they don't fully understand most of the things they would try to explain. And the reason for that, is that most of the time they were given a surface level explanation themselves, and they just accepted it.

[@not_kode_kun]

​@@tonchozhelev EXACTLY

[@vimandmanyothers554]

Programmers and IT people aren’t the same

[@not_kode_kun]

@@vimandmanyothers554 it shouldn't be the same, i agree, but sadly the line is very blurry these days. a lot of programmers nowadays have no real clue what their code is actually doing, all they care about is whether it works or not. this stems from the overly-corporate nature of the modern internet and digital world. as long as it gets them money on the short term, who cares if it's performant, well-written, robust code? the mindless consumers certainly don't, so why should the multimillion dollar companies care? sad world we live in

[@3osufdh4rfg]

@@tonchozhelev I have en education in embedded systems and having watched all the few videos they've done so far I've already learned several important things that no-one bothered to explain about how different data-structures are implemented by the compiler and why/how that has significant performance implications.

[@krystofjakubek9376]

It should be pointed out that the cache behavior of linked lists is NOT inherit to the linked list structure but rather to the allocator used to allocate the nodes. If we have an allocator allocators linearly the nodes will be located in memory in exact the same way as with the array. Alternative approach is to store enough elements in each node so that a full cache line is always used. Removal and addition from the middle of a node can be solved with splitting and merging. Also I am certain that pretty much all javascript interpreters really do use arrays whenever possible and only resolve to hash map as a fallback when the wasted size is too much or keys are some other type than numbers. This is not too difficult to implement internally and the performance boost is significant.

[@huben_1337]

This is very important to note. I also think iv read v8 uses property access for very small and likely to not be modified arrays. This way it can do direct property access without hashmap lookup or array indexing.

[@derDooFi]

no need to be so self-conscious at the end there. this channel is great

[@darkfllame]

that's why i propose all scripting languages should be pseudo compiled: the bytecodes are as specific as assembly instruction (not as much but you get it), and the generic stuff actually happens at "compile" time, every scripting languages should do that, even at the cost of longer "compile" time. I want to do one, but I struggle everytime when making the parser so you will probably never see that. Also in java, if it's not a primitive, it's an object, every arrays of non-primitives in java are arrays of objects, and you can verify it with the JNI.

[@elzabethtatcher9570]

Amazing video. And thank you for not pedaling surfshark or some unrelated crap. Video bookmarks would be welcome!

[@randykamindo4795]

Amazing video!

[@PedroShin]

amazing video!

[@kossboss]

your content is 👑. my kids will study from this channel one day 🥹 and their kids 😇 and their kids kids for generations learning low level concepts and rust. 🥂

[@bobsprite6711]

Excellent!

[@timur-yusipov]

Good content, thx!

[@sashibhushanarajput1194]

This is incredible

[@thecrazyeagle9674]

What a gem of a channel. Keep it up!

[@SoreBrain]

This was indeed a banger

[@indiannews544]

You are doing revolutionary work bro Keep going ,keep posting more often

[@fdb-js5uh]

Maybe it would be better to say that modern JS JIT compilers, like V8, often optimize arrays?

[@pritonce6562]

More reasons to hate JS :D (And yes to the streams) Also if you intend to expand your community on other platforms a discord server might be a good idea too.

[@yeknomhtooms]

i wish i had the opportunity to access all these kind of videos when i was studing computer science!

[@CoreDumpped]

Me too!

[@johnabrossimow]

12:03 did you cousin also write a getter for "self.lenght" (of self.items[self lenght]) to be the same value as "self.length" ?

[@sidreddy7030]

Omg I loved this video. Super cool to know how python’s list works under the hood. Can’t wait for what you’ve got next!

[@xyz-vrtgs]

Really great video, although I would have liked it if you talked about bounds checking in a normal array when you were talking about indexing out of bounds

[@bruno-dv5qq]

love your videos

[@mhFFFFFF]

“This explains why we use zero instead of one for the first element” What a hero 🙌. Finally a non-stupid “programmers just count from zero” explanation

[@Darkev77]

Please do Hashmaps next and how are its elements linked and how does it look like in memory

[@7th_CAV_Trooper]

Linked lists are for tape storage. Similar structures are used for block or heap storage.

[@Method5440]

I think when he says ‘and so Forth’ he’s actually telling us what programming language to use.

[@silloo2072]

😂

[@silloo2072]

We are 2 orange S

[@liburnkrasniqi4003]

God please never stop making vids my guy AGHHHHHHHHHHH

[@AlleBalle54]

another great video

[@anon_y_mousse]

Thanks. I had always assumed ArrayList was just some sort of alias for a Deque, but now I know, it's just a dynamic array type. Java is one of those languages that I've avoided fully learning and any language that reuses that name for a container type too. As it is now, I probably have far too much knowledge of Java.

[@sa-hq8jk]

i recommended the first 3 videos in this series to some computer science students i was tutoring because i felt like they went in depth into these concepts, while at the same time using terms and concepts that beginner programmers are familiar with. i felt like this video used a lot more terms and concepts which might be difficult for beginner programmers to understand compared to the last three. i think this series would be better for introductory students if the smaller concepts mentioned in this video like data structures, time complexity, etc. had heir own video before having a video about dynamically sized collections

[@sa-hq8jk]

in other words i felt like the pacing in this series took a sharp turn that might be too overwhelming for me to be able to recommend it to other computer science students. judging by the pacing of the first three videos in this series, it seemed like these videos were attempting to cater toward beginner-intermediate programmers with around a year of experience, but this video didn’t come across that way, although i may be wrong in my assumption for the targeted audience of these videos

[@someonespotatohmm9513]

@@sa-hq8jk I think there is enough context to understand what a datatype is without giving the textbook definition of what a datatype is (which i doubt will be helpfull to anyone anyway). A definition of time complexity would probaply have been nice, it is easy to understand and aply in these cases and can also easily be googled if needed.

[@sa-hq8jk]

@@someonespotatohmm9513 i didnt mean what exactly a data type is, but more of how a struct is a type which combines other types, and how they are grouped together in memory and interpreted by the compiler and by memory

[@abombfuenmayor]

Excellent videos. Love your channel!

[@KeshavKumar-gc9pu]

Very well explained, these kinds of animations are extremely useful.

[@c4cypher]

The Lua Table has entered the arena.

[@VaughanMcAlley]

It would be interesting to see what Lua’s cache hit & miss rate is compared with other languages…

[@stefanmladenovic2040]

Yet another banger from project CD!

[@mayureshpisat2274]

Thankyou so much for these videos plz keep making them they are so good

[@Boronesss]

which tools are you using to create these animations. looks pretty good

[@shant0]

absolute mad lad

[@xBiggs]

I created a linked list in C with two levels of indirection with varying orders of magnitude up to a billion elements. However, I never got valgrind to report cache misses above 0.7% when pushing all, then accesseing all then popping all. I understand that valgrind will report a simulation of the cache rather than the actual cache, but it was the best I could do to measure because my kernel does not have perf.

[@sevos]

Man this animations Where were they for all these years?

[@Nerdimo]

If only I had you as my professor

[@lucianobestia]

May I give two thumbs up ?

[@jaya_surya]

Thanks

[@drf289]

Your cousin may know more than me, but he still misspelled "length" in that code :P 11:50

[@yarrakobama3417]

There‘s no way i was too lazy to comment „Dynamically sized data structures“ on yesterday’s post 😂 I had it 😭😭

[@kiwiladi]

excellent

[@Fowdre]

I've been wondering for some time now, what do you use to animate your videos?

[@keeprocking3620]

In Lua arrays are done the same way as in JS: they are in fact maps with values being indexed by numeric indices

[@DrakiniteOfficial]

Despite its quirks I love JavaScript for many reasons, one of which is that we want better performance in arrays, we can use typed arrays. The hash map approach is quite clever IMO, since in most JS code you won't be looping more than a few hundred (or few thousand at the most) times in a normal array, and if you see doing more than that, then well, you should probably reconsider your approach. All about being the right tool for the job. And if JS is just too slow, you've got WASM. And if WASM is too slow.......... then ditch JS/WASM and build a native app. 🤣

[@CoreDumpped]

Yes I agree, the right tool for the right job. What I really dislike is that people trying to convince the world that JS should be used everywhere.

[@Darkev77]

@14:59, is it not possible in this case to move the first element to the right and then update the base memory address to its moved location?

[@devnarula6733]

afaik js arrays are actual arrays and not hashmaps... you can do array.string_key = value because like everything else js array is ALSO an object, but it contains an array as well, you are just assigning a property to the array object. If you do array[12]=some_val to a new array you will see the length actually change but if you do array.string_key=val length does not change... so basically it is {[,,,,,,,,,,,some_val], string_key: val}, js engines optimize it anyways

[@0-0_ora]

what do you think about Fast LinkedList with algorithmic time complexity?

[@philtoa334]

Nice.

[@Kardiiacc]

Hey Core Dumped, it would be so cool if you could make a vid on what object orientated programming is

[@alfredomoreira6761]

Be aware that modern javascript engines optimises arrays if they have no holes (java like) and even more if they are of the same type (c like) : check for SMI, DOUBLE_SMI, HOLEY_SMI, etc js arrays. So modern js engines are no more just an interpreter but also a list of runtime JIT compilers run depending of the context of the running code (the more a bit of code is run the more it uses the most complex JIT compiler with the most optimisation). hence why js nowadays can be as fast as some compiled languages.

[@L1Q]

pointer arithmetic was baked directly into intel 8086 cpu instruction set, no wonder systems programming langugaes at the time would also reflect the feature in their syntax

[@CoreDumpped]

Does this has anything to do with that take that I've been recently reading a lot claiming that C beats everything because CPUs are designed to be 'C-compiled code' efficient?

[@gtgunar]

4:30 I'm pretty sure it's APL that invented the bracket notation for array elements.

[@kleinmarb4362]

Please do streams would be so nice

[@andrey730]

Does it mean that python lists are bound to be this cache-miss nighmare? Any ideas if there are ways to make them more efficient, like numpy?

[@Blezerker]

20:34 i REALLY need this card. Coredumped plz

[@CoreDumpped]

Selling them could cause Oracle to sue me since I don't have their legal permission to use the product name "JavaScript". I've been thinking about using "JS" instead, but don't know if people would buy it.🤔

[@young_oak]

Thanks for your hard work!!!🎉