[Tutor] python list, right! but concretely?

[Steven D'Aprano]

On Sun, 2 May 2010 03:49:02 pm spir ☣ wrote:
> Hello,
>
> Is there anywhere some introduction material to the implementation of
> python lists (or to fully dynamic and flexible sequences, in
> general)? More precisely, I'd like to know what kind of base
> data-structure is used (linked list, dynamic array, something else --
> and in case of array, how is resizing computed). Also, how is
> "generics" (element are of free type, and even heterogeneous)
> managed?

I'm not sure if this is documented anywhere (other than the source code, 
of course) but in CPython lists are implemented as arrays of pointers 
to objects.

Because re-sizing arrays is expensive, the array is over-allocated: the 
array is (very approximately) created twice the size needed, to give 
room to grow. Then when the array is full, or nearly full, it is 
doubled in size again. This gives amortised O(1) appends, at the cost 
of being 50% larger than needed on average. This means that append is 
nearly always very, very fast, with an occasional, and rare, slow 
append when the list resizes.

Because the list is an array, iteration is very fast and lookups are 
O(1). However, deleting from the start or middle of the list is O(N), 
as are insertions. If speed is important, and you need fast insertions 
and deletions at both the start and end of the list, then you should 
use collections.deque; however item lookup for deques is O(N).

Of course all of this is an implementation detail. Other implementations 
are free to make other memory/time tradeoffs, although if their lists 
performed very differently, people would complain.


> Denis
>
> PS: The reason is I'm trying to understand better the underlying
> layers of magic facilities we use everyday. Starting from about no
> computer science knowledge. I have a working implementation of linked
> lists in primitive langguages ;-) (namely C & Pascal), but rather
> complicated to my taste; and I'm probably overlooking commonly known
> and used tricks that could make the algorithm simpler or more
> efficient.

The simplest implementation of a linked list in Pascal is something like 
this:

type:
  ptr = ^node;
  node = record
    data: integer;
    next: ptr
    end;

Here's a procedure to traverse the list, printing each item:

{untested}
procedure walk(alist: ptr):
  begin
    while alist <> nil:
      begin
        writeln(alist^.data);
        alist := alist^.next
      end;
  end;

Everything else, I leave as an exercise :)



-- 
Steven D'Aprano