[Tutor] Making Doubly Linked List with Less Lines of Code.
steve at pearwood.info
Thu Jan 1 00:57:36 CET 2015
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.
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:
gives you access to the cell [i, j] effectively instantly, two
array accesses, which is much, much faster than having to traverse a
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:
__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.
More information about the Tutor