Skip to content
Hallway
0:00 / 0:00

#arrays#linkedlists#cpucache

Arrays vs Linked Lists - Computerphile

Computerphile

2.6M subscribers • 70 videos on Hallway

YouTube
  • Recommended by 2 people: 2 in engineering communities.
  • A classic. People kept recommending it from 2020 to 2023.
  • Presented by Dr. Steve Bagley

Intermediate. Assumes working knowledge.

505K views9 years ago2 recommendations

Computer scienceSystems programmingData structuresPerformance and optimization

Dr. Bagley compares the performance of arrays and linked lists on modern versus retro hardware, explaining the impact of CPU caches.

Which is faster? The results *may* just surprise you. Dr 'Heartbleed' Bagley gives us an in depth shoot-out - Arrays vs Linked Lists... Link to code can be found in Dr Bagley's tweet: t.co/4kg3AZDA57 Sun Server: youtu.be/c5qH-LW3tq8 Megaprocessor: youtu.be/lNa9bQRPMB8 facebook.com/computerphile twitter.com/computer_phile This video was filmed and edited by Sean Riley. Computer Science at the University of Nottingham: bit.ly/nottscomputer Computerphile is a sister project to Brady Haran's Numberphile. More at bradyharan.com

Why it's here

2 people recommend this

What people say. Recommended for understanding how CPU cache bottlenecks make arrays faster than linked lists on modern hardware.

u/DeeBoFour20in r/C_Programming • Recommends

On “In Defense Of Linked Lists”

Well, if you're making a game that needs to run at 60+FPS, these things matter. Also, linked lists actually sometimes performed better on old hardware than arrays. Old CPUs didn't have caches and were bottlenecked by the speed of the CPU. On newer CPUs, we're bottlenecked by memory so the situation is reversed. See this video where he benchmarked this on a modern iMac vs an old Atari system: link to this video
10View on Reddit

u/cincuentaanosin r/C_Programming • Recommends

On “Which one is consumes less time, traversing an array ot traversing a linked list ?”

As always, it depends. Watch this for some insights: [video
2View on Reddit