News for hackers. Stuff that matters.
Re:Turn O(n^2) reverse into O(n) by aidenn0 on Sunday December 15, 2013 @11:30PM (#6912891)
Lists don't have O(n) complexity of appending an element, if you keep track of the tail element.
Re:Turn O(n^2) reverse into O(n) by verbin217 on Sunday December 15, 2013 @11:54PM (#6912984)
I 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).
Re:Turn O(n^2) reverse into O(n) by danieldk on Monday December 16, 2013 @01:47AM (#6913264)
I 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