CODEWITHSUNDEEP
pythonalgorithmlinked-list
Christian Benincasa
Christian Benincasa

Reputation: 1215

Concatenate Python Linked List

I am attempting to concatenate a Python linked list without copying the data contained within the nodes of the list. I have a function that will concatenate the list using copies of the nodes passed in, but I can't seem to get the function that doesn't use copies to work.

These functions are for testing and timing purposes; I know that Python's built-in list is awesome!

Here is the class I have been working with and the concatenate function.

class Cell:
    def __init__( self, data, next = None ):
        self.data = data
        self.next = next

def print_list(self):
    node = self
    while node != None:
        print node.data
        node = node.next

The concatenation function is not meant to be a member function of the Cell class.

def list_concat(A, B):
    while A.next != None:
        A = A.next
    A.next = B      
    return A

This function overwrites the first element of a list if the parameter A has more than one node. I understand why that is happening, but am not sure how to go about fixing it.

Here is the testing code I've been using for this function.

e = Cell(5)
test = Cell(3, Cell(4))
test2 = list_concat(test2, e)   
test2.print_list()

Any insight or help would be greatly appreciated.

*edited to fix code formatting

Upvotes: 4

Views: 6837

Answers (2)

Chris
Chris

Reputation: 1643

I'm not sure on about if extend performs a copy or not, but in case it doesn't, just use

A.extend(B)

Upvotes: 0

Óscar López
Óscar López

Reputation: 236044

Try this instead:

def list_concat(A, B):
    current = A
    while current.next != None:
        current = current.next
    current.next = B
    return A

Assigning new values to a function's parameters is a bad programming practice, and the code in your question shows why: You used A for iterating over the original list, and by doing so, you lost the reference to its first element.

Upvotes: 6

Related Questions