5 ms·

The advice is not against lists, it's against linked lists which are a particular implementation. You can have dynamic-sized lists that are backed by arrays, ye

by opinali 13y ago

The advice is not against lists, it's against linked lists which are a particular implementation. You can have dynamic-sized lists that are backed by arrays, yet have O(1) amortized time for operations that require the list to grow or allow it to return freed space (add/remove at either end). Linked lists will only win when you need to add or remove elements in random positions (AND don't need random access, so this is usually very niche scenarios where you iterate the list end-to-end but make some updates, e.g. to insert new elements in order). Trees made up of list nodes are another obvious exception, but then we're not arguing about trees, just pure lists. (And even then... denser kinds of trees such as heaps or b-trees can often wipe the floor with traditional trees made of tiny, linked nodes.)

rayiner 13y ago
> You can have dynamic-sized lists that are backed by arrays Lists backed by arrays have the same problem as arrays: pointers to elements are not stable. To take the example in my post, say you want to save the environment of every AST node so you can generate debug info mapping from variable names to register numbers at each line. When the list nodes are stable, it's trivial to just save a pointer to the head of the list. When addition/removal operations on the list can cause reallocation, that becomes much harder. > Linked lists will only win when you need to add or remove elements in random positions (AND don't need random access, so this is usually very niche scenarios where you iterate the list end-to-end but make some updates, e.g. to insert new elements in order). This is not a niche use. There are a huge number of operations where you don't traverse the list but need to add/remove from the middle. Consider something like the task scheduler in a kernel. When a process makes a call that blocks, the scheduler gets a pointer to the task structure and needs to remove the process from the run queue until the data it is waiting for arrives. If you store the runque as an array, you need to search it and remove the relevant task. If you store it as a doubly linked list, you can remove it with just a couple of pointer modifications. Indeed, inside a kernel or memory allocator, if you're iterating over any potentially large sequences, you've already lost the battle.
- opinali 13y ago
  > pointers to elements are not stable This is only a problem if the list is constituted exclusively by its backing store; which is a common implementation for linked lists in some langs/libraries, but rarely for lists backed by arrays. In the latter case, the "list object" typically has a pointer to the backing array, and also other fields like indexes of first/last element in use. This means one extra level of indirection for any use of the list, but in practice compiler optimizations easily hoist or constant-propagate this overhead away in any code where it matters. > There are a huge number of operations where you don't traverse the list but need to add/remove from the middle Admittedly, my use of "niche" is context-dependent. In languages like Java where List is a kind of catch-all data structure -- it's the collection that people use when they don't have a very good reason for any other option -- the huge majority of uses do not involve updates in non-tail position (or even any updates after the initial population; most of the time a fixed-size array would work just right... except that it's against modern Java religi, er, style, to ever use its primitive arrays).
bad_user 13y ago
Actually lists of arrays are still linked-lists, with the definition being: a data-structure where nodes are grouped together, with each node being made of a datum and a reference to the next item, where you can push() and pop() from one or both ends in O(1) and that can only be accessed sequentially in O(n). It really doesn't matter what the reference actually is, all that matters is that the information for accessing the next node is contained within the current node. Having optimizations like XOR-ing the back/forth pointers for encoding a doubly-linked list with a single word per node, instead of two, or linking together arrays of fixed size, that's just an implementation detail.
- opinali 13y ago
  What I meant is a list where all elements are stored in a single, dense array, which grows automatically if necessary for adding new elements. See C++'s std::vector, and Java's java.util.ArrayList.

by opinali 13y ago

rayiner 13y ago

> You can have dynamic-sized lists that are backed by arrays Lists backed by arrays have the same problem as arrays: pointers to elements are not stable. To take the example in my post, say you want to save the environment of every AST node so you can generate debug info mapping from variable names to register numbers at each line. When the list nodes are stable, it's trivial to just save a pointer to the head of the list. When addition/removal operations on the list can cause reallocation, that becomes much harder. > Linked lists will only win when you need to add or remove elements in random positions (AND don't need random access, so this is usually very niche scenarios where you iterate the list end-to-end but make some updates, e.g. to insert new elements in order). This is not a niche use. There are a huge number of operations where you don't traverse the list but need to add/remove from the middle. Consider something like the task scheduler in a kernel. When a process makes a call that blocks, the scheduler gets a pointer to the task structure and needs to remove the process from the run queue until the data it is waiting for arrives. If you store the runque as an array, you need to search it and remove the relevant task. If you store it as a doubly linked list, you can remove it with just a couple of pointer modifications. Indeed, inside a kernel or memory allocator, if you're iterating over any potentially large sequences, you've already lost the battle.

opinali 13y ago
> pointers to elements are not stable This is only a problem if the list is constituted exclusively by its backing store; which is a common implementation for linked lists in some langs/libraries, but rarely for lists backed by arrays. In the latter case, the "list object" typically has a pointer to the backing array, and also other fields like indexes of first/last element in use. This means one extra level of indirection for any use of the list, but in practice compiler optimizations easily hoist or constant-propagate this overhead away in any code where it matters. > There are a huge number of operations where you don't traverse the list but need to add/remove from the middle Admittedly, my use of "niche" is context-dependent. In languages like Java where List is a kind of catch-all data structure -- it's the collection that people use when they don't have a very good reason for any other option -- the huge majority of uses do not involve updates in non-tail position (or even any updates after the initial population; most of the time a fixed-size array would work just right... except that it's against modern Java religi, er, style, to ever use its primitive arrays).

bad_user 13y ago

Actually lists of arrays are still linked-lists, with the definition being: a data-structure where nodes are grouped together, with each node being made of a datum and a reference to the next item, where you can push() and pop() from one or both ends in O(1) and that can only be accessed sequentially in O(n). It really doesn't matter what the reference actually is, all that matters is that the information for accessing the next node is contained within the current node. Having optimizations like XOR-ing the back/forth pointers for encoding a doubly-linked list with a single word per node, instead of two, or linking together arrays of fixed size, that's just an implementation detail.

opinali 13y ago
What I meant is a list where all elements are stored in a single, dense array, which grows automatically if necessary for adding new elements. See C++'s std::vector, and Java's java.util.ArrayList.