2

I'm a pretty new programmer to python and am having trouble iterating over a linked list. This is a linked list that is given to me as the output of some other software I am using (which I do not have the ability to modify), and contains parameters I need to access (just called my_parameter here for reference). For reference here, I have named the linked list sim_table. The snippet of code I am using to attempt to iterate is: 

sim_table_rows = []
def iterate_linked_list(node):
    while node is not None:
        sim_table_rows.append(node.my_parameter)
        node = node.next

iterate_linked_list(sim_table)

This works fine in ipython, which is where I test everything, but when I try to run the script outside of ipython I keep getting a segmentation fault: 11. To diagnose the problem, I tried printing the output instead of appending it: 

def iterate_linked_list(node):
    while node is not None:
        print node.my_parameter
        node = node.next

iterate_linked_list(sim_table)

The output I get is an infinite loop of the my_parameter from the last node in the list, but I'm not sure why. I also made a test sim_table that has only two nodes to see what happens if I try to iterate to a non-existent node in ipython: 

In [10]: test_sim_table.next.next.my_parameter
AttributeError: 'NoneType' object has no attribute 'my_parameter'

So I get an attribute error instead of None, which is what I was expecting. Am I missing something simple? I am pretty new to all of this, so probably. Thanks for any and all help!

Improve this question
2
  • 1
    If node isn't None, then you're going into an infinite loop of appending the first element... No where do you advance through the linked list Commented Oct 17, 2013 at 0:06
  • 2
    You really should be getting a MemoryError here rather than a segfault. But if the linked list you're being handed is from a C extension module, it's pretty common for such modules to have bugs that make them crash in out-of-memory cases. Commented Oct 17, 2013 at 0:20

4 Answers 4

Reset to default
3

No where do you ever advance through the linked list, maybe you want:

sim_table_rows = []
def iterate_linked_list(node):
    while node is not None:
        sim_table_rows.append(node.my_parameter)
        node = node.NEXT_NODE # Change node to next one...

Assuming that NEXT_NODE is the attribute that contains a reference to the next node.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

2

I think it is because the first node you input is not None. and it will never be None because you are constantly testing the same node in the while loop.

It is similar to this infinite loop:

while True:
    # do something

It also seems like you are parsing through the linked list recursively.

Perhaps :

sim_table_rows = []
def iterate_linked_list(node):
    if node.next is None:                           # reached end of linked list 
        sim_table_rows.append(node.my_parameter)    # add last value of liist #to the list
        return sim_table_tows                       # returns full linked list
    else:
        sim_table_rows.append(node.my_parameter)  # append to linked list
        return iterate_linked_list(node.next)     # run again with the next node as input
Improve this answer

4 Comments

I'm not so sure about recursing there – if recursion is desired, perhaps if should replace while?
Ok, so I've tried it, and it's somewhat bizarre. For one of my sample linked lists, which has only two nodes, this works just fine and returns the python list I wanted. But when I try it on a full linked list (with hundreds or thousands of nodes), I get: RuntimeError: maximum recursion depth exceeded.
as I learned python as well, I was told recursion in python has a limit. I will try ot get you a better solution
@user2888465 try it out and lemme know if there is anything wrong
0

It could be that your linked list is terminated by a node that refers to itself.

def iterate_linked_list(node):
    if node is not None:  # non-empty list?
        while True:
            print node.my_parameter
            if node.next is node:  # end of list?
                break
            node = node.next
Improve this answer

1 Comment

hmm... tried this as well and get a segmentation: 11 fault. From what I understand, this is a seg fault related to memory?
0

Ok, I never got a complete reason, but evidently the source of this seg fault is related to the fact that the linked list I'm trying to access is generated using SWIG bindings. I guess this problem has been seen before by much saavier-than-me colleagues, and it's related specifically to a software distribution that we use to generate our data. What I've managed to do, to get around this, is the following: 

sim_table_rows = []
while True: 
    sim_table_rows.append( [ node.parameter1, node.parameter2 ] )
    if node.next is None: break
    node = node.next

parameter1_types = [sim_table_rows[jj][0] for jj in range( len( sim_table_rows ) )]
parameter2_types = [sim_table_rows[jj][1] for jj in range( len( sim_table_rows ) )]

Here, node is the linked list and I've defined it earlier in the script using my external software. I still get the seg fault if I attempt to do much more than this, so I'm just using this as is (will work for my purposes, though it's perhaps clunkier than needs to be).

Thanks for all the helpful comments and suggestions!

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.