Linked Lists — BaseCS Video Series

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

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 :)

so helpful, Thank you

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?

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 🙃

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?

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

XOXO

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.

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)

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.