Re: Cheaper to prepend or append an item to a sequence

> 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@xxxxxxxxxxxx> 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
>
>



--