Python copy and concatenate linked lists, preserve order

Question

I have a basic linked-list implementation in python. Each Cell has some data associated with it and a next object, used to include the rest of the linked list (and null if only the first param of data is given in the constructor).

I want to copy and concatenate two lists together, so that the final product preserves the order and is independent of the two original lists.

Here is what I have:

def list_concat_copy(A, B):
        C = Cell(A)
        while A.next != None:
                A = A.next
                C = Cell(A,C)
        C = Cell(B,C)
        while B.next != None:
                B = B.next
                C = Cell(B,C)
        return C

The issue that I am having is that this reverses the order:

A = Cell(8,Cell(9,Cell(10)))
B = Cell(11,Cell(12,Cell(13)))
C = list_concat_copy(A,B)

Now if I walk_and_print(C) I get 13 12 11 10 9 8

Any thoughts?

Answer 1

You do some weird stuff:

A = Cell(8,Cell(9,Cell(10)))

suggests that your Cell is something like

class Cell(object):
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

but doing

C = Cell(A)

never copies anything, it just creates a new Cell with the same A as a value.

So, lets start with a Cell that can actually copy itself:

class Cell(object):
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

    def copy(self):
        if self.next is None:
            return Cell(self.value)
        else:
            return Cell(self.value, self.next.copy())

Now your concat is easy:

def concat_copy(a, b):
        new = a.copy()

        # find the end of the copy
        last = new
        while last.next is not None:
            last = last.next
        # append a copy of the other list
        last.next = b.copy()

For completeness, here is what your tried to do:

def copy( cells ):
    new = Cell(cells.value)
    current = new
    old = cells

    while old.next is not None:
        # copy the current cell
        ccopy = Cell(old.value)

        # add it
        current.next = ccopy

        # prepare for the next round
        current = ccopy
        old = old.next

    return new

I think this helps to understand how you accidentally reversed your cells: You walked the list forwards but the C = Cell(A,C) puts a new Cell before the old C, so that builds the new list from the end.