[Tutor] Making Doubly Linked List with Less Lines of Code.

wolfrage8765 at gmail.com wolfrage8765 at gmail.com
Tue Dec 30 23:40:04 CET 2014

On Tue, Dec 30, 2014 at 2:37 PM, Danny Yoo <dyoo at hashcollision.org> wrote:
> If that's the case, then none of this requires linked list storage.
> Instead, we can represent this as a list of rows.  Each row element
> would be itself a list of tiles.  In short, a matrix.  See:
> https://docs.python.org/2/faq/programming.html#how-do-i-create-a-multidimensional-list

True, I could use a multidimensional list. And originally I was using
a 2D list. But I wanted the ability to quickly search across a row or
up and down a column and so the added benefit of the linked list was
that it simply requires me to access the next node reference.
> And finding neighboring tiles also wouldn't be too bad: Given a tile
> at (i, j), we can find its neighbors through arithmetic (i plus or
> minus one, j plus or minus one).

 From a coding perspective the linked list seemed simplier, because my
other 2D list implementation required me to have a function that could
map from any position to North, South, East, & West, plus it needed to
perform bounds checking. Of course having the list now be doubly
linked has added complexity.
> If the game grid were a lot more dynamic and non-squarish, then that
> might make it appropriate.  Linked lists give us a flexible way to
> represent such a game board.  But at the moment, I think it's overkill
> for the scenario you're showing us.

That may be True.
I would like to know, if you know, would this doubly linked list be
more or less memory efficient than the 2D list method and which one
would provide faster look-ups? I do know that the doubly linked list
has an initial speed cost in constructing it, which is obviously more
than the 2D list. The overall application to which this code will be
applied is a Kivy App that will be deployed to mobile devices, that is
why I have these questions, although I realize this is pre-optimizing
which is the root of evil...

More information about the Tutor mailing list