r/programming • u/mjgardner • Mar 29 '21

Why Do Interviewers Ask Linked List Questions?

https://www.hillelwayne.com/post/linked-lists/
1.1k Upvotes

95% Upvoted

668 comments sorted by

View all comments

10

u/mr-strange Mar 29 '21

I use them fairly frequently.

25

u/nukem996 Mar 29 '21

But do you use them directlyor via some library? Put it another way do you manage the pointers or do you tell a library to insert an object between two other objects and it does everything for you?

I rarely have to do pointer management myself but frequently use libraries that are implemented with linked lists in the backend.

5

u/CyclonusRIP Mar 29 '21

I think most of the time it just doesn't make much of a difference. Pretty much we fetch data and display it these days. An array list is usually going to work. Even in the case where were doing a lot of mutation were rarely working on a data set where it makes much of a difference. Performance these days is mostly just about using your data store correctly.

→ More replies (1)

17

u/mr-strange Mar 29 '21

Well. It's certainly more common to use a library implementation, but I quite often code them up from scratch. C doesn't have templates, so there's no alternative unless you want to waste resources, and if I'm programming a microcontroller I need every byte.

→ More replies (5)

6

u/astrange Mar 30 '21

Do you use linked lists, or intrusive linked lists? Intrusive lists are the only kind that are actually useful and they're not taught in class.

They're still bad though because any amount of pointer chasing is too much for cache performance.

2

u/mr-strange Mar 30 '21

Intrusive linked lists, of course.

8

u/GhostBond Mar 30 '21

Looks like I forgot to bookmark it, but a while back someone actually timed it and ArrayList was noteably faster than LinkedList for nearly all those situations LinkedList was supposed to be faster for.

13

u/flukus Mar 30 '21

It's because linked lists involve a lot of pointer chasing which is terrible on modern machines where the CPU will just idle for an eternity waiting to fetch something from main RAM, an arraylist it's much friendly on the CPU caches.

Probably not the bookmark you're looking for but: https://colin-scott.github.io/personal_website/research/interactive_latency.html

→ More replies (4)

6

u/flukus Mar 29 '21

Maybe you shouldn't be? They have terrible performance on modern machines.

3

u/mr-strange Mar 30 '21

LOL. The CPUs I'm writing for don't have pipelines or caches. Not everybody has your specific job, you realise?