[Tutor] lists

[Danny Yoo]

On Tue, 23 Apr 2002, Josh Gregorio wrote:

> What are linked lists and do you need them in Python?

Hi Josh,

The "How To Think Like a Computer Scientist" tutorial has a nice section
on linked lists here:

    http://www.ibiblio.org/obp/thinkCSpy/chap17.htm


A linked list is a data structure that allows us to string together bits
of data into a long chain.

But let's first compare this with what you know already, a regular Python
list.  A Python list is a blocky container:

-----------------
|   |   |   |   |
|   |   |   |   |
-----------------

and we can use it to store multiple values in one place.


A linked list does the same sort of thing --- they're used to keep objects
--- but instead of all the blocks being arranged right next to each other,
we string them together with "references":

-----            -----
|   |----------->|   |-------+
|   |            |   |       |
-----            -----       |
                             V
                            -----
                            |   |
                            |   |
                            -----
                              |
                              |         -----
                              +-------->|   |
                                        |   |
                                        -----

One advantage of stringing the blocks is that it's efficient to insert a
new block right in the middle of the chain: all we need to do is reroute a
link or two, and that's it.  In contrast, in a regular Python list,
insertion usually involves bumping off all the neighbors to the right so
that we have the room to do the insertion.


As you're browsing through that chapter, please feel free to bring your
questions here; we'll be happy to talk about linked lists.

Good luck!