CODEWITHSUNDEEP
pythoncopylinked-listconcatenation
Jordan
Jordan

Reputation: 5058

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?

Upvotes: 3

Views: 3171

Answers (4)

Haoze Tang
Haoze Tang

Reputation: 1

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))

Upvotes: 0

senderle
senderle

Reputation: 151057

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)

Upvotes: 1

Jochen Ritzel
Jochen Ritzel

Reputation: 107666

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.

Upvotes: 7

miki
miki

Reputation: 71

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.

Upvotes: 3

Related Questions