Arrays vs Linked Lists - Computerphile

Which is faster? The results *may* just surprise you. Dr 'Heartbleed' Bagley gives us an in depth shoot-out - Arrays vs Linked Lists...

This video was filmed and edited by Sean Riley.

[nickwasd]

"We're not gonna run this on the iMac, we're not gonna run it on the Pi, we're gonna run it on the Atari behind me" I love this guy so much.

[Nerdnumberone]

The more important difference is the difference is how the performance scales for different operations and what you actually plan to use the data structure for. Both of these were O(n) operations, but selecting an arbitrary element in an array is O(1) in an array and O(n) in a linked list. However, trying to dynamically increase the size of an array would be O(n) (since you have to make a new array and copy the data) while a linked list can add another item to the front in O(1). Adding or removing arbitrary items next to a node you're currently looking at is O(1) for linked lists and O(n) for arrays (though this would be O(n) for linked lists if you had walk to the element you want to change).

They are different tools for different things. If you're only using operations where the two structures are comparable (like the summation mentioned in the video) and speed is particularly important, then such a test makes sense, but what you use the data structure for is likely to be far more important.

[flavioalarcon]

I learned java programming from an institute, in there I basically learned the basics on how to program, develop websites and things like that, but they never even began to explain how things actually worked, it still worries me how little I actually know about computers, since all I know is basically what years of progress in the computer world have achieved, and I'm just using the tools they gave me without questioning, videos like this are very important for someone like me, I appreciate it.

[AlexandriaRohn]

05:22 We're going to visit every single element (125k) in an array & linked list and add up all their values.
11:18 Running linked list version on Atari computer takes ~166 clock ticks.
13:07 Running array version on Atari computer takes ~179 clock ticks.
17:55 On the Atari computer. Traversing the array backwards is ~114 clock ticks.
18:20 Why? What's happening is that the instructions the Atari machine can execute favors walking backwards.
21:00 Summary of results for Atari, Raspberry Pi, and iMac.
On the Raspberry Pi and the iMac, the array is much faster than the linked list.
22:15 What's happening? Caching. The Atari doesn't have a cache. Every bit of data has to be fetched from memory each time. But the CPU isn't much faster than the memory. But for the iMac and the Pi, the CPU is much faster and has to wait for things to be fetched from memory.

[Nathan]

This stuff is worth Gold. Not many modern Computer Science degrees teach this because modern day CPUs have cache and compliers have optimization which means that there is virtually no difference in the speed. So people have started assuming that everything runs as quick. Scale the CPU down and you understand the true answer.

Very well put video! Worth the 30 minute

[DeusExAstra]

Between caches and prefetchers, in modern hardware arrays are almost always better than linked lists, or other data structures much of the time. Especially in things like game engine architecture, putting items in arrays versus linked lists of randomly allocated elements (i.e. items all over in memory) can yield very significant speed benefits.

[gormster]

"Confusing variable names, but hey, I'm a C programmer" 😂

[stephenelliott]

Steve is by far the clearest when it comes to explaining anything Computerphile. Clear, Concise, C programmer - all the C's! :)

[TheJaguar]

First impression. Depends on the operation. I tend to use arrays when I need contiguous memory, or I have a known length, and if I need random access. I use linked lists when building lists with unknown length and where random access is not required.

[JulianColeman]

videos like this make me really appreciate C as a language

[soraaoixxthebluesky]

“...which means I need a very high tech piece of equipment”

*showed us a floppy disk*

[philippbeer]

A fantastic video. It’s set up great. And the fact you do “myth busting” and teaching people how to test a question like is simply awesome.

[MasterNeiXD]

Second term computer science students, rejoice. Computerphile has come to save you.

[DanRosCoder]

I stumbled across this video this evening, some 5 years after it was published. Brilliant work, mate! I'll be searching to watch more of your videos right now!

[MorRobots]

This will completely be a function of use case and implementation. I love to see what you all setup for this test.

[WeatherWonders]

He's talking about complex computer stuff and I'm just intrigued by the little ASCII spinner at 9:37.

Edit: Haha, they talk about it later on. :D

[vavassor]

Also, depending on the fragmentation of the allocator from which the linked list nodes are taken from, on a cached CPU it can be much much slower than an array which always has its elements on the same cache lines relative to one another. And then there's a funny case where supposing you have an allocator which allocates things linearly and you allocate the whole linked list at once, it basically gives you an array with a bunch of (useless) pointers to next nodes between each element. This will basically perform not quite as fast as the array, because it won't be able to fit as many elements per cache line due to the space wasted by the pointers, BUT it'll be much closer to the array than prior. Overall, the speed of operating on a full linked list on a cached CPU will vary depending on where the nodes were put in memory relative to one another.

Another thing to note is how in my work anyhow, you're very unlikely to see a list as big as 125k elements. So, the effects of the cache on full array loops is increased even moreso.

[SHUBHAMGI]

a + b = b + a
you can watch Numberphile for that 😂😂 LoL

[RakeshPGopal]

Ironically I see this video next on the auto-play list "Bjarne Stroustrup: Why you should avoid Linked Lists"

[subsystemd]

Wow. That has to be one the best video on the topic of computer hardware differences and how we as programmers should not make any assumption on how a machine is supposed to function when executing code. I love the "I'm writting in a high level language" when actually it's C and it's one of the least abstract language you can use without resorting to assembly. Just shows you how much this man knows his stuff.