2001 Enchancement Wishlist

[Martin von Loewis]

Raymond Hettinger <othello at javanet.com> writes:

> 1.  List.append(elem) and List.pop() are great.  Let's add two more
>      methods, List.prepend(elem) and List.leftpop().  The goal is to
>      make queues,deques, and reverse stacks easier, faster, and clearer
>      to implement.

Others already commented that it wouldn't be faster; I believe it
wouldn't make deques easier to implement, either. If I had to
implement a deque, I'd use the C++ STL approach (i.e. a variable-sized
list of same-sized lists, with two indices indicating the first entry
in the first list and the last entry in the last list, out-of-range
entries being None). That way, adding and deleting to the deque is
constant-sized for reasonable access patterns, and linear with a low
factor in the worst case. 

prepend and leftpop would require linear time, as they would be
implemented as slice assignments.

Regards,
Martin