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

[Steven D'Aprano]

On Tue, Dec 30, 2014 at 05:40:04PM -0500, wolfrage8765 at gmail.com wrote:
> 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.

[emphasis added]

Trust me on this, there is no linked list code you can write in 
Python that will be faster than using a list of lists.

Even in C, traversing a linked list is slower than array access, and 
Python is not C.


> > 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.


Bounds checking is easy: cell [i, j] is in bounds if this is true:

    (0 <= i < NUM_ROWS) and (0 <= j < NUM_COLS)

Fast access to any cell is possible:

    array[i][j]

gives you access to the cell [i, j] effectively instantly, two 
array accesses, which is much, much faster than having to traverse a 
linked list:

    cell = array
    for x in range(i):
        cell = cell.next_row
    for x in range(j):
        cell = cell.next_col

(or whatever scheme you use for linking to the next row/column).


As far as memory consumption goes, I don't think there is any 
comparison. Here is a doubly-linked list of strings:

class Cell:
    __slots__ = ['data', 'next', 'prev']
    def __init__(self, data):
        self.data = data
        self.next = self.prev = None


x = y = Cell('alpha0')
for i in range(1, 10):
    y.next = Cell('alpha' + str(i))
    y.next.prev = y
    y = y.next



Now let's see how much memory it uses:

from sys import getsizeof
size = 0
y = x
while y is not None:
    size += getsizeof(y) + getsizeof(y.data)
    y = y.next


On my system, that gives size of 630 bytes.

Let's do the same for a list. This only takes two lines of code:

x = ['alpha' + str(i) for i in range(0, 10)]
size = getsizeof(x) + sum(getsizeof(s) for s in x)

On my system, that gives a size of 406 bytes, considerably smaller.


-- 
Steven