## Data structure help, linked lists?

This is the place for queries that don't fit in any of the other categories.

### Data structure help, linked lists?

When you search for "python linked list" you'll find comments about how you shouldn't use them and just use the plain list type instead so maybe I'm over-complicating things but ...

I have an m*n nested list of nodes like this:
Code: Select all
`B = Begin node, O = Middle node, E = End node[[B, O, O, O, E], [B, O, O, O, E], [B, O, O, O, E], [B, O, O, O, E]]`

The begin and end nodes are more or less defined and fixed, middle nodes are derived from surrounding nodes.
Eventually I need to have the following access patterns from the "current" node:
Code: Select all
`P = previous, C = current, N = nextNo = north, S = southFirst rowP--C--N  / /PSMiddle rowsPNo No \  |  \ |   \| P--C--N   /|  / | /  |PS  SLast rowPNo No \  |  \ |   \| P--C--N`

For now I'm working along each individual row only and I found something[1] that works nicely.
Code: Select all
`class Node(object):    def __init__(self, a, b, c):        self.a = a        self.b = b        self.c = c    def calculate_c(self, previous, next):        self.c = (next.a - previous.a) / (next.b - previous.b)def previous_and_next(some_iterable):    prevs, items, nexts = tee(some_iterable, 3)    prevs = chain([None], prevs)    nexts = chain(islice(nexts, 1, None), [None])    return izip(prevs, items, nexts)for row in MyNestedListOfNodes:    previous, current, next = previous_and_next(row)    current.calculate_c(previous, next)`

but I don't know how to extend that to the required access patterns listed above.

I could do something like this:
Code: Select all
`for i, row in enumerate(MyList):    for j, node in enumerate(row):        # all kinds of index magic here        # hoping it wont go out of range`

but past experiments have shown that this will likely turn into an unreadable mess, especially when you read it back after a few months.

Do you have some advise on what data structure or method to use for this?

[1] http://stackoverflow.com/questions/1011 ... ide-a-loop
hrs

Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm

### Re: Data structure help, linked lists?

I came up with this
Code: Select all
`class Node(object):    def __init__(self, val):        self.prev = self        self.next = self        self.up   = self        self.down = self              self.val = valclass Grid(object):    def __init__(self, data):        self.data = data        self.max_x = len(self.data[:][0]) - 1        self.max_y = len(self.data) - 1                self.linkGrid()    def addNode(self, x, y):        self.data[y][x] = Node(self.data[y][x])    def linkGrid(self):        for y, row in enumerate(self.data):            for x, item in enumerate(row):                self.addNode(x,y)                if x == 0:                    self.data[y][x].prev = None                elif x == self.max_x:                    self.data[y][x].prev = self.data[y][x - 1]                    self.data[y][x].prev.next = self.data[y][x]                    self.data[y][x].next = None                else:                    self.data[y][x].prev = self.data[y][x - 1]                    self.data[y][x].prev.next = self.data[y][x]                                if y == 0:                    self.data[y][x].up = None                elif y == self.max_y:                    self.data[y][x].up = self.data[y - 1][x]                    self.data[y][x].up.down = self.data[y][x]                    self.data[y][x].down = None                else:                    self.data[y][x].up = self.data[y - 1][x]                    self.data[y][x].up.down = self.data[y][x]    def traverse(self, func):        for y, row in enumerate(self.data):            for x, node in enumerate(row):                print func(node),            print    def horizontalAverage(self, node):        if node.prev != None and node.next != None:            node.h_avg = (node.prev.val + node.next.val) / 2            return node.h_avg    def verticalAverage(self, node):        if node.up != None and node.down != None:            node.v_avg = (node.up.val + node.down.val) / 2            return node.v_avg    def ldiagonalAverage(self, node):        if node.prev != None and node.up != None and node.next != None and node.down !=None:            node.ldiag_avg = (node.prev.up.val + node.next.down.val) / 2            return node.ldiag_avg    def rdiagonalAverage(self, node):        if node.prev != None and node.down != None and node.next != None and node.up !=None:            node.rdiag_avg = (node.prev.down.val + node.next.up.val) / 2            return node.rdiag_avggrid_data = [[00., 03., 05., 07., 09., 11.],             [12., 10., 08., 06., 04., 02.],             [21., 31., 41., 51., 61., 71.],             [111., 222., 333., 444., 555., 666.]]MyGrid = Grid(grid_data)print "\nhorizontal average"MyGrid.traverse(MyGrid.horizontalAverage),print "\nvertical average"MyGrid.traverse(MyGrid.verticalAverage),print "\nldiagonal averge"MyGrid.traverse(MyGrid.ldiagonalAverage),print "\nrdiagonal average"MyGrid.traverse(MyGrid.rdiagonalAverage),`

Looking at it now, it seems more logical to put the average methods in the Node class rather than the Grid class but then I don't know how to pass those methods to Grid.traverse(). Any ideas? Other comments on how this code could be better?
hrs

Posts: 86
Joined: Thu Feb 07, 2013 9:26 pm