Data Structures: Crash Course Computer Science #14

[@reaper84]

the videos always seem like a compressed version of my first two years of studying computer science. though not as thorough as the lectures back then, these videos really hold up and explain everything extremely well. great job!

[@amateruss]

Crash course is a great way to refresh your knowledge about almost anything.

[@curiosull]

Just remember, if you are new, that this 10m video is a 1 semester or a few books study compressed, so take it lightly.

[@aboxinspace]

They've explained it better here than at my college... I should be laughing, but it hurts.

[@lolmaker]

lol my school started this like over a month ago and still hasn't finished XD. But its pretty simple tbh

[@damenwhelan3236]

Proof that one on one IS more efficient than telling a group of people to memorize datum.

[@johndoh1000]

Am I doing it wrong? I've binge watched up until now, and I plan on continuing until the end. FORTY SEMESTERS WORTH OF COMP SCI IN TWO DAYS!!!

[@119sigma]

@@aboxinspace Ditto. I am revisiting it 2 years later and I am just amazed how well it explained the concepts in just ten minutes. It helps though having studied it before in my opinion though.

[@hammar324]

I told my friends that I now know how to access a 5 dimension matrix. They are no longer my friends.

[@osgnuru]

I'm trying to get my teacher friends to show this series to their students. I love this. All students should see this in class.

[@tuckercoffin2164]

Dear Carrie Anne and crashcourse, I hope you're seeing this. You are all amazing. Thanks so much for making these very good quality videos and keeping them for free. I'm considering supporting you after I'm done with binge watching the entire series. I'll definitely recommend this series to others. I'm impressed. You're amazing.

[@ianrbuck]

Data structures was my favorite subject in my CS courses in college! It all just makes so much sense, and thinking about how each piece of data relates to all the others is like a fun puzzle.

[@Klarpimier]

0:59 "Almost all programming languages start at index zero" Me: *slowly turns and glares at Matlab*

[@RazerBlackShark]

MaTLaB Is NoT a ReAl ProGrAmMiNg LanGuAge

[@Canonall]

Pascal does this as well

[@zyaicob]

*shouts at LUA*

[@Canonall]

@Thomas Samoht you are right, my bad.

[@SufianDira]

LUA starts at 1 for some reason

[@busyrand]

I'm learning to Program now, and surprisingly understood everything. Had to stop and scroll back a few times, but that was a beautifully clear explanation of each concept!

[@derpmaster2086]

For anyone who may just be starting to learn low level languages, be careful when using "NUL" vs "NULL" because they can mean two different things. "NUL" refers to the NUL character or ASCII zero. "NULL" refers to a null pointer - a reference to a non-existent location in memory.

[@zen_of_chloe]

"Null" is its name and NULL was its original abbreviation. So not as wrong as all that. en.wikipedia.org/wiki/ASCII

[@OmegaF77]

NULL could also be nullptr. NUL can also be '\0' (char type).

[@Death_User666]

thanks much sir

[@aeebeecee3737]

Thank you

[@MrMineHeads.]

I am LOVING THIS SERIES! LOVE YOU CARRIE ANNE AND CRASH COURSE!

[@victorcovasan9155]

right now I just hope this will be a never-ending course

[@cholten99]

Always great folks but that was pretty much an entire term's class-worth of data structures in 10 mins. It'd be fascinating to know how many people who encountered this for the first time kept up! As a side-note it's really good how you refer everything back to memory locations. So often these days people are taught to use data structures as basic language building blocks with no idea what's going on "under the hood". So, object orientation next week? :-)

[@tsmwebb]

Yep, nice but very, very concentrated. As I was listening I too thought that it might be hard to follow or even a bit misleading for a person new to the material. Universal referents and particular implementations got a bit tangled up. Still, an impressive effort given the time constraint.

[@tsmwebb]

Interesting. As a C# programmer did you find the discussion of stings at all confusing?

[@MasterGeekMX]

In my college is the opposite, and we had to build a Java class implementing the basic of each and one of the structures that the video showns. For example in an exam I had we needed to implement a funcion in a binary tree in wich we pass an array of numbers in any order and then the numbers got stored in the tree in order.

[@tsmwebb]

+Pepys Thanks, maybe my criticism was misplaced. I suspected that people would watch that and think "oh, that's what a sting ~is~" rather than "that's one good way to implement a string." Your mention of C# jumped out at me since it is an example of a language that does strings differently than presented. Sorry that I misinterpreted your programming experience.

[@MakeMeThinkAgain]

Many CrashCourse episodes are like crammed with a little too much info to get in one pass. Sociology for example. I tended to work with languages that were weak in data structures so I had to create my own with strings. Slow, but a great way to learn about data structures. (Hint: the secret is to have a delimiter character for each dimension that is never included in the data content.)

[@BlueGuitarMusic]

You said in the beginning you weren't gonna go into programming yet I feel like I've learned a ton about the fundamentals of code languages and where programming happens. You tricked me into learning way too much!

[@AyeAyeCaptain]

i am so in love with the narrator.She is so adorable !

[@captainnakou]

I'm a computer engineer and I'm doing some Java stuff for like 5 years, and this video gave me the envy to go back doing some C again, like I did back at school. And I like that.

[@LexYeen]

This series is why I'm getting into arduino programming, and this video just helped me get past a hurdle I encountered on my project. Thanks! =D

[@Dodgerific]

I love these videos and feel that I am actually finally understanding computers! thank you

[@alieser7770]

dont mean to be rude or discouraging, but this is basically nothing ;(

[@BlueyMcPhluey]

this series is like my hit of crack every week that keeps me going

[@jmanaa9969]

You basically covered last semester programing course in a 10 min video, I am impressed. But it might be too much information for people who are seeing the topic for the first time.

[@trannusaran6164]

"It'd be weird if roots connected to leaves that connected to roots." *Looks nervously at Bryophyllum daigremontianum* >_>

[@Schindlabua]

Found the botanist! Seriously though, that's a dope plant.

[@sceKernelDestroy]

I am happy you are here :)

[@vertigo6982]

I think most people would be freaked out a lil by how peanuts grow.

[@jamiebertram9744]

This is the fastest coverage of basic data structures I have ever seen

[@harshamohite1289]

As someone studying computer science, this is a fantastic refresher of all the basic concepts. So clearly explained!

[@IceMetalPunk]

Wow. This was super fast! If I didn't already know this stuff, I could easily get lost in all the information!

[@KenBellows]

one thing left out in this otherwise really good overview is the main disadvantage of linked lists: random access (that is, getting the value at a certain index into the list) becomes much more difficult, and is much less efficient than in simple arrays. each data structure has its tradeoffs and use​ cases

[@kaosz7777]

God I love crash course :) I only wish you made actual courses on this subject. I am a currently earning my BS in CS and I absolutely love to talk about data structures. Programming is my blood. However, there are so many techniques and different ways to structure your data that I want to know everything I can.

[@tategeiger5317]

I love how the oscilloscope is different each time

[@prowhiskey2678]

0:44 list != array An list uses pointers to get to the next index. An array uses ons block of memory. Meaning that a list is faster if you are iterating over the shops structure, but An array is better of you need to het a specific indexeert element.

[@niharikapatil902]

You guys are amazing! I have my interviews in the next two weeks and this really helps me speed up

[@jordanlevitt1638]

im currently doing a course on data structures and we've only just reached pointer variables so this video is linking everything tgr before I've even learned it. cheers

[@melonlord1414]

Thank you! Now I understand why I always got errors when Iworked with Arrays. They don't want to grow dynamicly^^

[@dohoanggia]

Spent the whole semester for this. Thank you!

[@Yujideluca]

i just love this woman, thank you so much

[@villadelfia]

Note that in some languages, strings are not null-terminated, but rather they start with how many characters the string contains. There's pros and cons to each approach. (Also, the C++ standard library is called the Standard Library. The standard template library used to be a non-standard library that has since been added to the standard.)

[@Dsiluigi]

You didn't play the "A new level of abstraction!" jingle! How could you?!

[@mikejohnstonbob935]

It's the same abstraction.

[@gustavolrcoelho]

I feel cheated. I demand a reupload with proper jingle.

[@zavi3rz]

It has been abstracted so it's no longer shown.

[@anthonyz9197]

I love the jingle and spontaneously combust whenever it comes on.

[@brainwashedbyevidence948]

Anthony Z Soo you catch on fire?!?

[@Implond]

A lot of programming languages are very particular about the type of data you give to a function, whereas more flexible ones can accept multiple types. The trade off is inflexibility against precision.

[@Tuchulu]

Sam Whelan some programming languages don't let you play with pointers.

[@rev.davemoorman3883]

A$= "at"+10+"shun"

[@angeldude101]

The main drawback is that miss-typing isn't caught until the system tries to do an operation expecting one type and you give it another. Static typing generally catches this before any of your code gets run. Even worse is when the system preforms a different operation because it's a different type. The first time I used python, 10 < 5.

[@louis058]

Addendum: Null character terminated strings are the most common way of doing it, but it's also possible to just store the length of the string as a number as the first field, then the string. Then, we know where to stop because we see the length before reading the string.

[@Hav0c1000]

I absolutely loved this crash course at 75% playback speed!

[@doumkatekz]

Same. And I usually watch things at 1.5

[@christopherkotchey2593]

Exactly what I was just thinking - they're going over this one a lot faster than the previous videos.

[@aeebeecee3737]

Create complex data structure just really similar as you create a pile of structured files and folders in windowsOS, the pointer similar as shortcut that point to a folder or file in windows, so you can create linked data.

[@kunalmandalia1165]

Good job giving us an easy to understand taste of different data structures

[@aeebeecee3737]

This series is so clearly and helpful.

[@JOJO_THE_PROGRAMMER]

Great video good for those who have studied already these concepts in detail

[@ladydarkangelyuki]

hopefully you will talk about data hashing, this is crucially important in the modern world of programming.

[@MasterGeekMX]

Here in México in my college they teach you about all of this plus the paradigm of object-oriented programming in two courses, called "Object-oriented algorithms and linear storage patterns" and "Object-oriented algorithms and non-linear storage patterns", We just call them by the initials, wich in spanish are APALOO and APANLOO, respectively.

[@niffler6110]

What a great Video!! such clever use of graphics and sounds in education....I enjoyed it wholeheartedly

[@109Rage]

Not all strings need to end in NULL. Seeing as strings are just arrays, and some languages store the length of an array, a string's length would just use the same value.

[@DreadKyller]

True, and both ways have their advantages and disadvantages. Let's say you have a really long string, like loading an entire file (not generally a good idea to load it into a string, use buffers or something instead, but this is an example), then null-terminated strings are smaller, as you'd need more than the size of a character to represent the length of the string if the string stored its length up-front, while the null-terminated string would only add the size of an additional character. Now this isn't a large amount of space, but because scenarios like this exist, the string data type in many languages use large numbers like ints or longs, even if the string is only very short, meaning if you're using hundreds or thousands of strings in a program (for example think about localization files for programs or games) then you're using up a lot more memory this way. On the other extreme though, there are many calculations where you want to know the size of the array, but don't wish to modify or read the array, just know its size, in a null-terminated string the entire array must be iterated down until the null is found to calculate the size (it can possibly be stored afterwards so you only iterate once, but anyways) while storing the size up-front allows you to simply read this value, making these types of operations faster. So both have some advantages and disadvantages and if you're lucky enough to be using a language where you can choose to use either or then choose based on the task, and otherwise other languages that don't have them sometimes have ways for you to implement them yourself if need be.

[@Pitazboras]

There is one more disadvantage of null-terminated strings: you cannot store nulls inside the string, as they are interpreted as termination signs.

[@knife_wizard]

If you store your strings as immutable structures in memory, the size issues kind of vanish, depending on whether or not length references number of bytes, or number of UTF-8 glyph encodings(Which can be different). Moreover, you can have multiple variants of "String" all implementing the same interface, and encoding length as different width values in the structure. Though, as soon as you get past the length being one byte, it's pretty valid to stop caring about what data type you're encoding length as(Max for a 1 byte value is 1:256). Now, if they ARE mutable, things get fun, and you get into heuristically predicting the possible max size of your string, and giving it a data type wide enough for... however long your string gets. Granted, if your string gets beyond about 9 QUINTILLION characters(on a 64-bit processor, which is the modern standard) you have a very different problem. All told, storing the length of strings has a great many advantages over not doing so, and most modern languages DO do so, because most concerns of space sort of evaporate in the face of modern hardware, and the vast amounts of memory available(Not to mention the fact that 8 bytes to store the lengths of the longest things humans have ever written PALES in comparison to what 8 bytes of length can store)

[@UteChewb]

The main problem with null terminated strings is that you have to be careful of the target size of the character array, this is why you should use strncat rather than strcat. Also it is easier to resize a target string because you can easily determine the size of the strings without traversing the source arrays then allocate the desired memory and do the copy. In fact overall null terminated strings are considered unsafe programming because there is the risk of someone using a buffer overflow to hack you if you don't carefully determine the lengths.

[@MartinOlminkhof]

+Piotr Zaborski you typically wouldn't want to stored null characters in a string, it's a special character

[@emelineemeline9114]

She is so much more preferable to my monotone prof! I'm learning heaps - THX

[@ChemicalVapors]

A string doesn't necessarily terminate in a null. Although this is typical in C-like languages, many other languages store strings with the length of the string, eliminating the need for null terminating. (and allowing the null character to be included in a string)

[@Gguy061]

That algorithm that allows this video to be played at half speed....that's a favorite of mine

[@VladSvoka]

Graphs are usually stored as list of nodes and tuples of edges.

[@stealthwolf1]

I'm gonna put watching this video on my resume

[@ashish3944]

Lol

[@ganaraminukshuk0]

This is why we always say zeroth instead of first.

[@zen_of_chloe]

"Standard Template Library" is the old name. It's the C++ Standard Library now. Glad C++ got a shout-out anyway.

[@sorenvandenberg9909]

Hell yeah someone else likes c++

[@s3cr3tpassword]

Theres no elevator scene after the new level of abstraction!!!! Argh i watch this every week for that!!!!

[@superoxidedismutase5757]

I love you Carrie Anne.

[@ernikitamalviya]

Wow..........this was best for my quick revision of DS. Thanks @CrashCourse!!

[@brutalbutler]

wow an actual video where I knew about evrrything and wasn’t confused at any time during it??

[@alexovey]

Thanks a lot. I enjoyed the crash course. I now know what data structures are. planning to delve deeper

[@miguelbernal9314]

Hello, Carrie Anne: Your explanations and videos are great!!! Thank you so much for helping me understand computing better. Small petition (although given my ignorance it may be huge X-D): Could you please say or list the levels of abstraction required to display, for example, a "C" on a computer screen? 20+? Thanks again for being awesome :-) Miguel

[@gamingbutnotreally6077]

Very basic but still awesome! Thanks

[@malpol]

I can't feel time by hearing your voice It's just awsome

[@aeebeecee3737]

The range that includes range that includes range that includes range... and you can jump to another range then jump to another range then jump to another another range... so you can build any structure as you want.

[@SalamiMommie]

thanks for mentioning string cat. Super useful

[@mayukh4130]

how can i like this video more than once

[@DjangoLowe]

I'm surprised you did touch on classes and its differences from structures. Good show!

[@sunnz]

would love to see a video on heap and hash in this format!

[@sujithdubbaka5170]

Great video, easily digestible content

[@sokonumi]

I have taken so many classes that have gone over linked lists and I never truly understood it until watching this video, thank you so much!!

[@confidential303]

Alisa Kotliarova you serious??

[@paxdriver]

Wonderful episode and series!! Thank you guys! I wish you showed a more in depth example of the push/pop with link nodes graphically to help. Matrix too lol great job, I'd love 15-30 mins eps just you know you :p ... Always end up watching them 3 times anyway lol

[@DominicLondon]

Another fantastic video. Should help me with my Algorithms exam tomorrow 😊.

[@RonaldTagra]

Amazing videos. Thanks. In fairness, the reason why you think these videos explained better than in your college (or you think your college was useless) because you have understood and have existing background already. Imagine if your knowledge is zero.

[@rjwhite4424]

I think these videos are sooo interesting. wish their were more

[@Biscuitsdefortune]

[@sophiacai8157]

The first node, the one at the top, is the root, and the ones at the end are called leaves. They ought to call those pointers "branches!"

[@aeebeecee3737]

Pointer is a jumping structure, it can let you jump to another one. Just like open a portal and jump, open a portal and jump, open a portal and jump...

[@Robay146]

Yes! Another episode! I've beeeen waiting! 😃

[@thesaurusrex7919]

Boi I sure hope this all makes sense in 3 years when I have to learned this

[@HikaruKatayamma]

Strings don't always end with a NULL. Sometimes they have a byte or word at the beginning that declares the length, though that's fairly uncommon.

[@florianwege7563]

Matrices are rectangular/2 dimensions specifically.

[@Markd315]

Bruh I studied this for an entire semester and all I got out of it that she didn't cover was pqueues, skiplists, red-black, AVL trees, hashtables, sparse matrices and heaps. Heaps and hashmaps definitely would have been a good to cover here those are super useful and not just minor variations on a general theme.

[@jakykong]

I appreciate the discussion about linked lists, but it's not unfortunate that Lisp has only barely been mentioned in this series so far. Not out of an ideological bent (although I readily admit to having one), but simply because linked lists are inconvenient in most other languages and get abstracted out into vector objects, whose implementation is often not linked lists anyway.

[@tenshi53]

Told my friends I know how to access a 5 dimensionnal matrix. They were impressed!

[@patrikpavic3936]

You haven't talked about the more complicated data structures like Segment trees, Fenwick trees, Red black trees, Trie, Suffix tree, Suffix array , Wavelet trees which can do quite a lot!!

[@eigenmishi_in_3d]

So good! Thank you for the excellent summary

[@ProfessionalTycoons]

Crash Course Computer Science! Amazing.

[@trava4156]

when this video teaches you more about what a data structure is than your entire semester Data Structures class....-_-

[@kannan3801]

data structures in Java and C++ already there..so no worriers Also there are trees ,linked list,array,index,struct.

[@AlphaFoxDelta]

Very good summary!

[@rev.davemoorman3883]

Earliest programming advice: Once you understand tables (arrays in ML or Assembly) you are 80% there

[@kevindt100]

haha Nope. Atlease not for me. Stupit C++ pointers there the killer.

[@MartinOlminkhof]

+kevindt12 would it blow your mind to realise that arrays are essentially pointers?

[@kevindt100]

Explance please do.

[@edinramiro202]

.

[@rev.davemoorman3883]

Once upon a time, programmers used the machine language directly to make the computer run quickly. This removed a layer of abstraction which just slowed everything down. ML is like programming with DNA!

[@aeebeecee3737]

Science are growing up, benefit opportunity are growing up and the same the extinction opportunity are growing at the same time.

[@insanitycubed8832]

0:22 could've fooled me.

[@RickTrajan]

Insanity Cubed who are they kidding? we are all john green.

[@ikemkrueger]

4:14 The "C" programming language uses "struct". A struct is the predecessor of a "class".

[@prowhiskey2678]

Ikem Krueger struct == Class, but with a default public accessor. At least in C++.

[@knife_wizard]

So, the first lesson of linked lists; WHY are you using a linked list?If it's not for; Rapid random insertion and deletion AND Adjoinment of lists to the tail of pre-existing lists AND Reading of the list from head to tail You probably shouldn't be using a linked list. It's just not possible to ensure the locality of the entire list in memory, or even a major portion, risking cache misses and other such fiddly things.

[@Pitazboras]

Not sure why you use AND - what structure would you suggest if I only need rapid random insertion and deletion that preserves order, without the other two?

[@knife_wizard]

Depending on the size, either an array list, or a segmented array list. The idea is to minimize pointer indirection, really. And, in the original suggestion, order is arbitrary, not to say that you couldn't obtain good behavior from a specialized list with proper segmentation. My point was more, "Data structure design is hard, don't use a structure unless you understand it" I would prefer people KNOW the trade-offs they make choosing a purely linked list, or purely array list. It's an important decision to make, and deserves a lot of thought!

[@keistzenon9593]

This is A LOT to take in.. i have the feeling most comments are from people who know most of this... i learned this stuff hands on through programming.. i wonder how valuable these videos are to newcomers?

[@bee5120]

Question: can a Linked-List (doubly, circular, single, etc.) be put as children nodes in a BST (binary search tree) and what would be the advantage of that besides packing in a lot of information in a tree-like manner for sorting? If it's possible, what's the general logic to retrieving a particular linked-list node stored in a BST?

[@kaziislam2785]

Um, you mean using a linked-list object being used as nodes of the BST, or the linked-lists themselves are integrated into the tree?

[@bee5120]

The first one. Nevermind, I don't think that's possible since they're two different data structures.

[@xXAkirhaXx]

I don't see why not, as long as the data in your doubly linked list =/= the data in your BST. i.e. your BST would just be a data structure filled with linked lists. If you're wondering if you can store data from a linked list in a BST, also very possible, but then what would you use the linked list for? The addresses for the data you want should all be in the BST, and easier to get to.

[@colin7231]

Yeah, it would be possible. the data type of a node on a tree would be a linked list. however, this might not be super practical depending on your application. if you had to do a search, you now have to search a linked list on every given node, which, in worst case, would add linear complexity to search node, changing a BST search from O(n) to O(n²)

[@RegularTetragon]

that's entirely possible. Sometimes you just have tree data that requires that you store a linked list. Basically, in the tree structure struct BinaryTree { BinaryTree* left BinaryTree* right LinkedListNode value } You could also make LinkedListNode a pointer, which means that all that's being stored by the binary tree is 3 pointers, as opposed to multiple data structures.

[@WhyComplex]

If string concatenation = a strcat Then does a string array = stingray?

[@pet3590]

stringray

[@Pitazboras]

strcat = string catenation catenation and concatenation are synonyms but strcat has more obvious meaning than strcon, so that's why it was chosen for a name of the method (I presume).

[@xplinux22]

Stringray, strray, and strarr are three likely candidates.

[@aggbak1]

strarray, but I can see the intention of the joke.

[@Hambonillo]

String Array = Fruit of the Loom

[@tueemsyhu4846]

I like this series!😀😊👍

[@farefouse]

Cool video, very well explained!

[@SotamiesTrolli]

This course is so good. They weren't mentioned but K-D trees frustrate me a lot

[@anisoftware8493]

YOU GUYS ARE THE BEST

[@satyendrasingh33]

Error after 7.30 - Doubly linked list is explained as Tree.