[jholman]

I think you're both right and wrong.

mixmastamyk's comment implies that (s)he believes that Python lists are, under the hood, linked lists. This is wrong. Python lists are ultimately backed by C arrays. This is why get() and set() are O(1), and insert() is O(n).

However, dynamically resizing an array to support append operations, if you're not stupid, takes amortized constant time. Individual operations may be O(n). Python implementers, happily, are not stupid.

However, insert() operations do require "defragmenting".

So, the primary question mixmastamyk asked about the cost of

    def squares(n):
        sq = []
        for i in xrange(n):
            sq.append(i*i)
        return sq

is totally correct, but a lot of the sub-reasoning is wrong.

[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?