3 ms·
no, how do they manage to O(1) by making them immutable? the only way to add to a list would be to create a new one with the extra value added? I'd be very sur
by autokad 10y ago
no, how do they manage to O(1) by making them immutable? the only way to add to a list would be to create a new one with the extra value added? I'd be very surprised if they had the same performance as a mutable list
- colanderman 10y agoSingly-linked lists are a fundamental computational structure. A singly-linked list is simply an item and a pointer to another singly-linked list. To add an item, simply create a new singly-linked list with that item and a pointer to the old list. Since you are not copying data, this is O(1). Read more here: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_lists https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list... If this interests you, read also about tree structures such as red-black trees. These kinds of structures support all operations that mutable structures support in O(log n) time. Of course mutable structures can always be faster, but immutable structures are far better than linear time.
- jholman 10y agoSingly-linked lists are a fundamental computational structure, and I'm not disagreeing with anything in the spirit of your comment, but I want to point out that linked lists are pretty much never the right implementation choice for an application programmer unless you're working in a language with no decent stdlib and you also care hugely about every byte of RAM/storage/etc. Which does happen, but is not very common, in practice. For the benefit of the GP, what might be non-obvious about the way colanderman describes this, is that if you want lists that are cell-immutable but are resizeable with O(1) push() and pop(), you do your pushing and popping off the front of the list. So the pointer to the old list is still a valid pointer to its previous state. And at this point, yeah, go off and read the WP link. :)