Are lists at least as efficient as dictionaries?

[Aahz]

In article <781faf41.0308281604.51e48f45 at posting.google.com>,
Narendra C. Tulpule <naren at trillium.com> wrote:
>
>  if you know the Python internals, here is a newbie question for you.
>If I have a list with 100 elements, each element being a long string,
>is it more efficient to maintain it as a dictionary (with a key = a
>string from the list and value = None) for the purpose of insertion
>and removal?
>  Basically, if Python really implements lists as linked lists but
>dictionaries as hash tables, it may well be that hashing a key takes
>negligible time as compared to comparing it against every list
>element.

Lists are implemented as vectors/arrays, not linked lists.  That's why
accessing a list element is O(1), but the constant is smaller than for
dicts because it's linear addressing rather than a computational hash.
In addition, lists are more space efficient than dicts -- each dict
element requires two pointers (key and value), but each list element
requires only one pointer (value).
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

This is Python.  We don't care much about theory, except where it intersects 
with useful practice.  --Aahz