in place-ness of list.append

[Alexander Schmolck]

skip at pobox.com writes:

> >>>>> "Bart" == Bart Van Loon <bbbart at inGen.be> writes:
> 
>     >> Such an operation will be O(N**2), 
> 
>     Bart> why is that?
> 
> The a[:] operation makes a copy of a (as will the x = a + [n] idiom).

I'm pretty confident append itself (and a+[n]) are linear in N=len(a) since
the copying is linear and appending a single item in-place is constant time
(OTOH calling append N times to construct a list or tree of length N from
scratch is quadratic; I assume that is what you meant and also what the OP
seems to want to use it for, so not doing it this way is sound advice).
 
>     Bart> I am building a binary tree where each node is a list. the two
>     Bart> children are the parent list + 1 and the parent list + 2.
> 
> You might consider creating each node as
> 
>     left = [parent, 1]
>     right = [parent, 2]

Or, if you don't need to mutate the tree ``left = (parent, 1)``. Tuples ought
to have a little less memory overhead.
 
'as