3 ms·
Lists don't have O(n) complexity of appending an element, if you keep track of the tail element.
by aidenn0 13y ago
Lists don't have O(n) complexity of appending an element, if you keep track of the tail element.
- verbin217 13y agoI assume you're talking about lists with mutable pointers. I don't think that's what they're talking about here. Functional (persistent) lists are immutable. You can add elements only by creating a new data structure, similar to a linked list node, that will hold immutable references to the existing list and the new element. By convention the element is considered to be in front of the list. Hence prepending is rather easy (constant time) while appending requires rebuilding the whole list (linear time).
- danieldk 13y agoI assume you're talking about lists with mutable pointers. I don't think that's what they're talking about here. Functional (persistent) lists are immutable. [...] Hence prepending is rather easy (constant time) while appending requires rebuilding the whole list (linear time). You can append in O(1) time using difference lists. They don't have all the niceties of Prolog difference lists, but they are still great if you only have to append: http://hackage.haskell.org/package/dlist http://hackage.haskell.org/package/dlist