[mixmastamyk]

Yes, I've always just assumed that internally a resizable Python list was a linked-list I learned about in C... fits perfectly.

I suppose using an array must improve performance in typical cases, while the resizing (a linked-list advantage) happens less often.

[jholman]

Resizing is not a linked-list advantage, though. Resizing is an ammortized-constant-time operation.

The only advantage I'm aware of for linked lists is insert and delete (but not append and pop), which are constant time in a linked list but O(n) in an array.

The thing is, though, that doing insert() on a linked-list usually requires a seek first. Which is O(n) on a linked-list (and may be O(n), O(logn), or O(1) on an array, depending on what you mean by "seek"). So in _practice_, usually inserts and deletes are O(n) in a linked-list as well. (But not always, because you could already have a pointer to the relevant thing, for example if you have multiple different pointed-based data structures with pointers into each other.)

Basically, as far as I can tell, linked-lists are almost useless, unless you're forced to write all your data structures from scratch and you have too little time to write yourself a proper library. The main exception is for really hairy shit where you have multiple linked-list views traversing the same data in different orders.

[metaphorm]

linked lists are the default data structure underlying almost every implementation of Stacks and Queues and the variants of those. they're far from useless.

they're also such a flexible data structure that it is literally the ONLY data structure necessary to implement any of the LISPs.

[jholman]

> linked lists are the default data structure underlying almost every implementation of Stacks and Queues

Citation needed. I doubt this.

Certainly if I had only ten minutes to implement a stack or a queue, without access to anything more than stdlib.h (or equivalent), a linked list is easy to get right in a hurry, and only takes a few dozen lines. But the auto-resizing array is only a little harder, and has better performance for nearly every operation, as I explained in the previous post.

> they're also such a flexible data structure that it is literally the ONLY data structure necessary to implement any of the LISPs.

Of course. So what? That's not a reason to use them anywhere other than a school assignment that requires you to use them.

[lutusp]

> > linked lists are the default data structure underlying almost every implementation of Stacks and Queues

> Citation needed. I doubt this.

As do I. Since you're not going to reorder a stack or (in most cases) a queue, and since they contain fixed-size elements, what's the point of a linked list?