[Tutor] Re: Linked Lists

[Michael P. Reilly]

> Say, for instance, that you have a 10MB file.  Is readlines() smart
> enough to not load the whole thing into
> memory at once?  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.

By default, the readlines method would read the whole file into
memory.  But there is an optional argument that says what the maximum
space to use when reading the file, the lines within that buffer
would be returned and the file pointer is maintained for the next
call to readline(), readlines(), etc.

>>> large_file = open('very_large_file.txt', 'r')
>>> for set_of_lines in large_file.readlines(8192):
...   for line in set_of_lines:
...     pass # do the other processing
...

These all use C's stardard I/O library, which has buffering.  It reads
a block or blocks from disk, then takes the information it needs from
there, keeping the rest for the next call.

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

It depends on the implimentation of a linked list and how abstract
you wish it to be.  List, dictionaries, classes, take your pick.

def new_node_list(data, rest):
    """Create a node out of a two-element list where the first is the
datum and the second is the rest of the list.  Each is modifiable, if
this was a tuple, we couldn't change as we might like."""
    return [data, rest]

def new_node_dict(data, rest):
    """Create a node out of a dictionary with keys of "datum" and
"next"."""
    return {'datum': data, 'next': rest}

class new_node_class:
    """Create a node out of a class instance with attributes for
"datum" and "next"."""
    def __init__(self, data, rest):
        self.datum = data
        self.next = rest

You could get more arcane (using new modules instead of the above,
etc.).  But really it depends on what you need it for and how you wish
to use it.

Frankly, I wouldn't use a "linked list" in Python.  The existing list
data type is MUCH more flexible than a linked list.  The insertion
and searching routines are more than adequate for a "linked list"-type
data type.  If I was going to have something like this, I would probably
create a "container" class implemented as a Python list.

  -Arcege

-- 
------------------------------------------------------------------------
| Michael P. Reilly, Release Manager  | Email: arcege@shore.net        |
| Salem, Mass. USA  01970             |                                |
------------------------------------------------------------------------