DEV Community

Linked Lists — BaseCS Video Series

Vaidehi Joshi on February 06, 2018

You might have heard about linked lists, or you might think that you're supposed to know about them. Maybe you do know a little bit about them, but...
Collapse
 
andy profile image
Andy Zhao (he/him) • Edited

Super excited for this release! I'm both a visual and auditory learner, so this is perfect! 👌

Collapse
 
juanita profile image
Juanita Soranno

I. can't. even. explain how excited the prospect of this series makes me. I actually understand Big O now. Thank you! I'm sharing this with my team as we speak. Keep it up :)

Collapse
 
salmaeng profile image
Salma Elshahwy

so helpful, Thank you

Collapse
 
katylava profile image
katy lavallee

Is there going to be a single url where I can discover the rest from? I thought it might be this page, but I guess this is just about linked lists?

Collapse
 
ben profile image
Ben Halpern

This is just the linked list page, but @vaidehijoshi 's profile will have the new ones. If you follow her you'll get new posts in your notifications.

Collapse
 
katylava profile image
katy lavallee

thanks!

Collapse
 
ben profile image
Ben Halpern

As someone without a CS degree myself, and a less-than-stellar grip of some of these topics, this series excites me a lot. And I'm not just saying that because I helped make it 🙃

Collapse
 
isaacdlyman profile image
Isaac Lyman

This is great! One question: does the head node of a linked list contain data also, or just a pointer? I ask because you refer a couple of times to the second box in the linked list as "the first node," which confused me because visually it looks like the second node. And in the circular linked list, the tail node doesn't point back to the head. So this makes me think that the head node is "empty". Is that right?

Collapse
 
stefannibrasil profile image
Stefanni Brasil • Edited

Hi, Isaac, that's really good question. Hope I can help you. But yes, the nodes usually contain data. But it depends on what you want to do, you may need to use the 'head' just use it as a pointer, so it's not required to have data on your head node.

Collapse
 
coolnerdcool profile image
Michel

Yeah!
So glad that I've found this new series.

XOXO

Collapse
 
igormp profile image
Igor Moura

Amazing video! And those handwritten drawing and explanations are just gorgeous to look at.

The only thing I've missed was the explanation for sorted linked lists, this may be a nice topic for another video. Another neat follow up would be explaining stacks and queues, since their implementations are actually very similar to the one of a linked list.

Collapse
 
chenge profile image
chenge • Edited

Your video is great, but where is code sample?

Here is a simple one, only add node.

# create a struct with :value and :next
Cell = Struct.new(:value, :next)

# create a head of our list
list = Cell.new("head. hi", nil)

# method which create one more cell and return the struct
def linked_list(value, cell)
  return Cell.new(value, cell)
end

3.times { |i| list = linked_list(i, list) } # O(1)
Collapse
 
kspeakman profile image
Kasey Speakman

Excellent explanation as always. I use linked lists all the time since most FP lists are implemented as linked lists.

A word of caution though, you have to be careful of using linked lists in hot code. Even though they have O(n) characteristics, they can be significantly slower than arrays. Because of the way CPUs work, when it reads something from memory into CPU cache for processing, it reads surrounding data as well (cache line). Since array elements are stored next to each other, the CPU may be able to process multiple array elements with a single memory fetch. Whereas with linked lists, there is a high chance that every element will require a fetch from memory, greatly increasing processing time when iterating the list.

This is why in many languages, variable-size lists are actually backed with arrays. For instance in C#, the generic list List<T> allocates an array, and keeps track of how much free space is on the end. When you add an element and there is no free space, it allocates a new array of twice the size and copies the elements to it. The copy is expensive but, amortized over the life the object, is still much faster than using a linked list for many kinds of workflows.

I mention this because I have actually run into this issue when using an LRU cache in hot code. I tried both a linked-list implementation and an array-backed circular buffer, and there was a world of difference in the performance, as in the linked list became the bottleneck instead of the disk IO.

Collapse
 
maestromac profile image
Mac Siri

Awesome stuff! Looking forward to the rest of the series 🙌🏼

Collapse
 
androminor profile image
Varun Singh

Hey Vaidehi I followed you after watching the fantastic speaking up by you in treehous live streaming festival. You have given me a lost reason, and inspiration to come back to CS: ALGORITHM . Now I really want to know how did you upload videos on all your posts here using. What video platform did you use ? Please share the insight period

Collapse
 
enrikacreates profile image
enrikacreates

Awe this is sooo refreshing. So glad I checked this out. I am excited about what else you guys are teaching!! Hopefully to learn a lot here!

Collapse
 
abooayoob profile image
Mohammad Ali Khan

This is really cool! I have been listening to the base.cs podcast, and want to watch the videoseries :) However, I am finding this a little bit hard to navigate: Is this the first video in the series? Is there a linked list for this videoseries somewhere? Does it follow the same sequence as the medium posts or base.cs podcasts?

Collapse
 
hullsean profile image
Sean Hull

This is a really great explanation Vaidehi. Very clear & easy to follow. I wish my teacher was as good as you, when I learned these introductory concepts.

Well done!

Collapse
 
alpersilistre profile image
Alper Silistre

Thank you for your effort in putting this topic on video. Hope to see more.

Collapse
 
leeiaah_ profile image
이아 | Nessa Okeke

I'm a visual learner so I loved the diagrams and different colours of markers, it made it easier to visualise the linked lists in my head, looking forward to watching the next series of videos 🕺🏿 🕺🏿

Collapse
 
_justirma profile image
Irma Mesa

You're awesome!!

Collapse
 
richsinn profile image
Richard Sinn 🍔

Amazing video! The content is explained and presented very well. Looking forward to more of these!

Collapse
 
buntine profile image
Andrew Buntine • Edited

Is anyone else experiencing issues playing the video? I am on Firefox (tried a few different networks).

Edit: Oh, videos do not work in Firefox!

Collapse
 
buntine profile image
Andrew Buntine

Actually. Edit edit: Firefox seems to buffer the entire video before playback starts.

Collapse
 
drozerah profile image
Drozerah

Hi ! It look like something went wrong cause the player says "error loading media : file could not be played"

Collapse
 
iamthelaw profile image
Anton Alekseev

same here!

Collapse
 
storrence88 profile image
Steven Torrence • Edited

Really enjoyed this video and you helped to clear up some gaps in my knowledge when it comes to linked lists! Can't wait to watch your other videos!

Collapse
 
sulejman profile image
Sulejman Sarajlija

Can't wait for the next topic in video!!

Collapse
 
engineeringweb profile image
Aravind

These series are Great 🥳 And Thanks for posting it as Video series 🙂

Collapse
 
harishankar87 profile image
Hari Shankar

Well explained. Looking forward to more such posts from you Vaidehi Joshi.