[Tutor] Self-referential objects and garbage collection

[Remco Gerlich]

On Tue, Mar 20, 2001 at 08:02:51AM -0700, VanL wrote:
> Thanks,  the advice you all gave solved it.
> 
> I had a question, tho:
> 
> One person said:
> > Given that lists are built into Python, and much more powerfull
> than this besides,  it is of cource a pointless class.
> 
> Another said:
> > I find I never use linked lists in Python by the way, always just
> Python
> > lists. And so many other standard hard algorithms and data
> structures become
> > trivial when you have dictionaries available :).
> 
> Yeah, the native Python lists support a log more operations.  But I
> was under the impression that linked lists
> and lists were completely different data structures.

Yes. But you can often use lists where you would need a linked list in other
languages. For instance, Python lists can grow, something that e.g. Pascal
arrays can't.
 
> Say, for instance, that you have a 10MB file.  Is readlines() smart
> enough to not load the whole thing into
> memory at once? 

No, it will read it in all at once. You can give an optional second argument
that is a sizehint, it won't read in much more than that. In a new version
(2.1 I think), files have an xreadlines() attribute that is smart enough.

What does this have to do with linked lists, by the way? In Python you make
something like xreadlines() by means of a class that behaves like a list,
but gets its values lazily, ie when it needs them. You can give it a
__getitem__ method and you can run a for loop over it; see the UserList from
the standard library.

> I know that readline() will only return one line,
> but it was my impression that it was a one-at a time dispatching
> from an in-memory list.

readline() doesn't read in the whole file at once.

> In a similar vein, how would you use Python's native data types to
> represent a linked list?

What would you use the linked list for? Sometimes I'd use a normal list,
sometimes a bunch of (value, next) tuples, sometimes a minimal class like:

class LinkedList:
   def __init__(self, value, prev=None, next=None):
      self.value = value
      self.prev = prev
      self.next = next

You don't need much more than that. But your mileage may vary, maybe your
problem needs something completely different, or exactly your linked list
implementation :)

We have had some fun on this list solving problems from an ACM Programming
Contest list of problems at http://acm.uva.es/problemset/ . Several people
have sent solutions to some problems to the Useless Python pages at
http://www.lowerstandard.com/python/pythonsource.html .

[ Note: Why is there no link to the ACM problems page from there?! ]

It's interesting to see that some solutions to problems that would be
extremely hard in C or Pascal come out trivial in the case of Python, mostly
because dictionaries and long integers are readily available.

Try out your Python skills by trying to solve some of the problems :)

-- 
Remco Gerlich