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

[Alex Kleider]

On 2014-12-30 14:40, wolfrage8765 at gmail.com wrote:

> 
> True, I could use a multidimensional list. And originally I was using
>  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.

This problem interested me right from when it was first posted a few 
days ago so I tried to code up a solution to what I perceived it (the 
problem) to be.

In the process of doing so I discovered that list multiplication does 
not at all behave the way I expected (as demonstrated by the 
'bad_flip_2_D' function.)

Code follows; comments appreciated. (Since the issue now is list 
multiplication,
should this fork into a new subject?)

# script begins here:

#!/usr/bin/env python3
# file: 'two_D_list.py'
"""
OP:
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.
My interpretation/comments:
Required are methods to access/search along column or row.
Assume 2D list already exists.
Can we further assume that all rows are the same length?
Using a class might be the preferable way to go but leave that
for later refactoring.
Assume everyone assumes 0 based numbering.
"""

two_D = [
     [0, 1, 2, 3],
     [4, 5, 6, 7],
     [8, 9, 10, 11]
         ]  # For testing purposes.

def get_n_rows(array):
     """Returns length of the array == number of rows."""
     return len(array)

def get_n_columns(two_D_array):
     """Returns the length of the first (zero'th) row.
     We assume all rows are the same length."""
     return len(two_D_array[0])

def search_row(two_D_array, row_num, item):
     """Returns None if not there, else it returns the indices
     of the first instance of item found in the row specified.
     Not tested."""
     try:
         col_num = two_D_array[row_num].index(item)
         return (row_num, col_num)
     except ValueError:
         return None

def show_array(array):
     for row in range(len(array)):
         for col in range(len(array[row])):
             entry = array[row][col]
             if not entry:
                 entry = 0
             print("{:>3}".format(entry), end='')
         print()
     print()

def flip_2_D(two_D_array):
     """Flips a two dimensional array so columns become rows
     and the rows become columns."""
     ret = []
     for i in range(get_n_columns(two_D_array)):
         ret.append([])
         for j in range(get_n_rows(two_D_array)):
             ret[i].append([])
     for i in range(get_n_rows(two_D_array)):
         for j in range(get_n_columns(two_D_array)):
             temp = two_D_array[i][j]
#           print("putting {} into ({}, {})."
#                   .format(temp, j, i))
             ret[j][i] = temp
#           show_array(ret)  # For debugging purposes.
     return ret

def bad_flip_2_D(two_D_array):
     """Flips a two dimensional array so columns become rows
     and the rows become columns.
     Demonstrates unexpected (by me) results of array multiplication."""
     ret = [[[0]] * get_n_rows(two_D_array)] * get_n_columns(two_D_array)
     for i in range(get_n_rows(two_D_array)):
         for j in range(get_n_columns(two_D_array)):
             temp = two_D_array[i][j]
             print("putting {} into ({}, {})."
                     .format(temp, j, i))
             ret[j][i] = temp
             show_array(ret)  # For debugging purposes.
     return ret

def search_col(two_D_array, col_num, item):
     """Returns None if not there, else it returns the indices of
     the first instance of item found in the column specified.
     Simply reconstruct the array and then use search_row."""
     flipped = flip_2_D(two_D_array)
     return search_row(flipped, col_num, item)

if __name__ == "__main__":
     print("Running Python3 script: 'two_D_list.py'.......")

     print(get_n_rows(two_D), get_n_columns(two_D))
     print
     show_array(two_D)
     show_array(flip_2_D(two_D))

# end of script

Other possibly required info:
alex at x301:~/Python/Tutor$ uname -a
Linux x301 3.13.0-43-generic #72-Ubuntu SMP Mon Dec 8 19:35:44 UTC 2014 
i686 i686 i686 GNU/Linux

cheers,
Alex