3 ms·

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

by jholman 14y ago

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 14y ago
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 14y ago
  > 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 14y ago
    > > 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?

by jholman 14y ago

metaphorm 14y ago

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 14y ago
> 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 14y ago
  > > 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?