Python copy and concatenate linked lists, preserve order

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?

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.

The lists print out backwards because as you are packing the OUTER elements into the new list FIRST. As you continue to unwrap A, you add a wrapping to C.

The cleanest way to duplicate these lists might be to do a deepcopy of A and B (we'll call them C and D), and then set the deepest element in C (found by traversing until C.next==None) to reference D.

I feel it's a bit difficult to answer this question without seeing the definition of Cell -- but I think I see the mistake. Think of the list as a set of layers. The loop is starting with the innermost value of C. Every time you call Cell in the loop, it "wraps" that value with another Cell with the next value. The outermost Cell has the last value.

In other words,

C = Cell(8)
D = Cell(9, C)
E = Cell(10, D)

is equivalent to

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

Is that clear?

EDIT:

For the sake of completeness, here's another way to do it:

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

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


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

Try this:

def list_concat(x,y):
    if x.next is None:
        return Cell(x.data,y)
    else:
        return Cell(x.data,list_concat(x.next,y))