Should you avoid linked lists? (linked list vs arrays)

---

#StayHome #HappyCoding
Let's pit the linked list against the array. We all learn how to create linked lists and other linked data structures. We may have also heard about their asymptotically-fast insert and delete operations. But, linked lists' flexibility comes at a cost. This video takes you through some of the downsides, including additional memory usage, poor memory locality, and slower traversal speeds. I also include some example code (in C) to demonstrate these differences in contrast to arrays. (uses getrusage and make)
It also shows you how to define a preprocessor define from the command-line (-D).

Related Videos:



***

Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.

About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.

More about me and what I do:

To Support the Channel:
+ like, subscribe, spread the word

[JacobSorber]

I hope you all liked this comparison video. If there are other comparisons you would like to see explored, let me know.


Also, one commenter noted a bug in the linked list. Lines 30 and 31 in linkedlist.c need to be swapped (oops). Sorry about that. I've fixed the posted code. Unfortunately, YouTube doesn't allow me to update existing videos. So, those of you getting the code from the video, just make that change before you try to use the second insert function (it currently isn't called).

[Brettyoke]

Graduated from college last May, and was in your OS class about a year before that. Looks like your video making skills have improved! Hope you're doing well, thank you for your willingness and love for teaching, it made a lasting impact on me. Best wishes.

[enestastan]

One of the best explanatory performance comparison video I have ever seen. Thank you so much for the delecate job.

[LegendOfMurray]

great video!
note that keeping things contiguous not only prevents page faults, but also improves performance by taking advantage of spatial locality in the caches, as usually the caching system stores the data at the requested address AND some of the neighboring data.

[michaelkotthaus]

A really good comparison. It encourages me to always consider different approaches for one task. The "guest appearence" surrounds this episode prodigiously. :-)
For me - as a non-native speaker - this series helps me to improve my English skills.

[ChocolateMilkCultLeader]

Something about this is so much fun to watch

[psionl]

One method of old was to maintain a parallel array of "next" pointers (integers). Simply chain the elements of the next array together and have a "freep" pointer to the first element. That way, allocating and deallocating a value element is simply a matter of adjusting the freep pointer. Assuming that the value and next arrays are in the same cache, this should be quite fast.

[jynxriZr]

Thanks for the video. Thinking about your data structures is a good idea in general and I really like arrays (contrary to some folks especially in modern languages). However, I think the comparison is not really fair, particularly for linked lists because you added quite a bit of memory logic to the array functions. Similarly, you could also request 100 linked items in advance and flag them used, which would counter the memory locality argument a bit. I guess, if you'd pick an example for arrays, where you don't want to have unused gaps in your memory, it'd have performed worse in comparison to your implementation, not necessarily compared to the linked list, but maybe. I also suppose that realloc sometimes has to copy the old memory block if your memory space is fragmented, but I did not check on that. In the end, it always depends on the use case and it is good when you know what performs how under which circumstances, so thanks again.

[sameerplaynicals]

Yes, it doesn't matter if one links a node that is in the stack to a node in the heap, but one usually shouldn't because then things tend to get complicated. I am not saying it's not plausible but should be avoided in large projects. Please correct me if I'm wrong! Love your videos, by the way.

[hayfahvytsen]

Great video once again. One comment though, I know it's not the point of the video but it looks like insert_after_node() at 6:45 is not correct. Am I missing something?

[cnasarre]

Hi Jacob, I do know that this video is not that new but I just stumbled upon it today.
First I did not get through all of the comments and maybe my comment will be redundant but one way to improve LL efficiency could be to keep each 'deleted' block for future use hence not 'wasting' time to deallocate to reallocate later on. Not fancy, already know but still IMO worth mentioning.

[TheArtikae]

It’s a bit silly to compare speed without optimizations. Especially for sequential access on an array. Compilers just love that kind of thing.

[tekniktdr]

6:51 Is it me or insert_after_node() should have the statements in reverse order? I haven't programmed in C for a while, but I would say that there's a bug in this function.

[qwertyuiop-cuve]

I default to using a (resizable) array unless my usecase can take advantage of another datastructure's characteristics. With respect to your evaluation here I do have to point out that the remove function isn't really fair. Remove and insert are a pair performing opposite actions. If you don't do a search in the insert, the remove shouldn't either.

What the linked list is really good at, and the array is terrible at, is inserting or removing elements somewhere in the middle of a long list/array (when you already know the index/pointer).

I also notice you intermix terms remove/delete. The rule of thumb for naming I like to use, is to call it 'delete' when the operation includes freeing the memory associated with the element, and to call it 'remove' if you're just removing the element from the datastructure.

[islandcave]

Linked lists are better for updating a lot and mostly accessing sequentially. Dynamic arrays are better for random access but can be expensive to add to, but that is mitigated by having a bigger capacity then its size.

[boxedowl]

Never gonna have a lot of cache...

You say that but when I found out my wife's CAD workstation had as much Lvl3 cache as my first PC had main memory... I'm glad I was wearing my brown pants that day.

[aabdev]

Dear Jacob Sorber,
Does there exist a platform independent way to evaluate system Cache Size during run time according to indirect symptoms of program behavior?
Regards,
AB

[anon_y_mousse]

How I think of it, if you don't care about the ordering and don't need to maintain the ordering, then use a hash table with the data stored as arrays internally. An array of chains, each chain is an array, and deletions are a simple swap to the end and decrement. If you need the data in a sorted order, and obviously when that's not often, just call the sort function at that time. If it needs to be sorted all the time, either use a tree or a hybrid hash tree. I hardly ever, if ever at all anymore, use a plain array or a plain linked list to store any significant amount of data. I hope you've taught your daughter C because that would be awesome.

[MatthisF]

I was literally asking myself this question a week ago

[orocimarosay]

Nice video. I like that you have stressed its drawback well (I don't consider the fact that you have to hold one more pointer a drawback because memory is cheap but memory coherence is very important). I haven't used linked lists in my life tho not necessarily because they are slow but 99% of the time they are not useful over a vector (At least in the context of game development because I'm most accustomed to it than other areas).