[Tutor] Prepend to a list? (fwd)

[Danny Yoo]

> I ended up changing my approach so that it won't require appending to
> the list, but it's good to know anyway because I'm sure it will come up
> in the future.  I'm sort of surprised there isn't a prepend() method for
> lists, but I'm sure there's a reason.

Hi Jay,

The interface of a data structure can encourage certain ways of
programming, and discourage others.  Python lists don't support fast
prependings, so that's why its not a standard method in the API.


> Most of the data is small sets, but fairly frequently run, so I'm
> looking for more efficient code in terms of CPU cycles on the server. In
> such a case, is one of the approaches better, or are they fairly equal?

If your data set is small, it probably don't matter.  *grin*

But yeah, they do perform differently.  For your application, you probably
shouldn't worry about it unless you notice sluggishness, in which case you
should "profile" first to see where the time sink is.


But just to hint at what makes prepend expensive, let's imagine that
there's a list of people waiting in line for new Star Wars movie:

   ['luke', 'leia', 'han']

And let's say that there's an annoying twerp that pushes everyone off to
the side, just to get in front of everyone else.  The jerk shoves everyone
off balance.

That push forces everyone off to the side by one:

     [None, 'luke', 'leia', 'han']

And then, having room to squat, the malefactor plonks down.

     ['jarjar', 'luke', 'leia', 'han']


When push comes to shove, what's "costly" is the movement of the folks who
are already in line.  There were three people in line earlier, and
prepending 'jarjar' forces everyone in line to shift around by one.  And
in general, prepending on a Python list is more costly than appending
because it's more disruptive to the existing data in the list.

Does this make sense so far?


I have to point out that the expense of an operation depends on the
particular data structure we use to represent things.  Python lists
(a.k.a.  "arrays") can give us fast appends, fast random access, but slow
prepends.  There are other structures that have different compromises.

This stuff is the heart of studying computer algorithms, so if you're
really interested in this, you might be interested in a book like
"Introduction to Algorithms":

    http://theory.lcs.mit.edu/~clr/


If you have more questions, please feel free to ask!