Even with a forward-chained list, you can implement append without copying
if you choose, at least for the first append operation to a given list
(which 9 times out of 10 will be the only append operation).
What people want is to be able to append one list to another in O(N)
time, not in O(N^2).
This is why people chose to pre-pend the elements of the second list
(starting from the last) to the first list.
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
Facts do not cease to exist because they are ignored.
On Tue, Feb 22, 2011 at 6:32 AM, Michael Kay <mike(_at_)saxonica(_dot_)com>
wrote:
On 22/02/2011 13:58, Dimitre Novatchev wrote:
The accepted term in most functional programming languages is "a list".
A list is a functional data structure (immutable). Appending to a list
causes the whole list to be copied and is O(N). Prepending a list is
making just the "next pointer" of an item point to the list -- an O(1)
operation.
Even with a forward-chained list, you can implement append without copying
if you choose, at least for the first append operation to a given list
(which 9 times out of 10 will be the only append operation).
Michael Kay
Saxonica
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--