CODEWITHSUNDEEP
pythonalgorithmobjectscopelinked-list
Florence
Florence

Reputation: 21

Why isn't this Python object property permanently overwritten?

I'm working on a Linked List partitioning problem using Python. The goal is to partition a linked list into 2 segments, the first where values are less than x, and the second where values are equal to or greater than x.

I'm confused right at the first line of the partition function:

current = ll.tail = ll.head

Why doesn't this line permanently overwrite the value of ll.tail? I thought Python was a language where objects pass by reference. ll, ll.head and ll.tail are all objects, so my expectation is that this line would cause use to lose the value stored at ll.tail.

ll.tail stores a value that's necessary for the function's output, and it's still present in the function's output (and the output is correct), but I don't understand how.

Partition.py:

from LinkedList import LinkedList


def partition(ll, x):
    current = ll.tail = ll.head

    while current:
        nextNode = current.next
        current.next = None
        if current.value < x:
            current.next = ll.head
            ll.head = current
        else:
            ll.tail.next = current
            ll.tail = current
        current = nextNode

    # Error check in case all nodes are less than x
    if ll.tail.next is not None:
        ll.tail.next = None


ll = LinkedList()
ll.generate(10, 0, 99)
print(ll)
partition(ll, ll.head.value)
print(ll)

LinkedList.py:

from random import randint


class LinkedListNode:

    def __init__(self, value, nextNode=None, prevNode=None):
        self.value = value
        self.next = nextNode
        self.prev = prevNode

    def __str__(self):
        return str(self.value)


class LinkedList:

    def __init__(self, values=None):
        self.head = None
        self.tail = None
        if values is not None:
            self.add_multiple(values)

    def __iter__(self):
        current = self.head
        while current:
            yield current
            current = current.next

    def __str__(self):
        values = [str(x) for x in self]
        return ' -> '.join(values)

    def __len__(self):
        result = 0
        node = self.head
        while node:
            result += 1
            node = node.next
        return result

    def add(self, value):
        if self.head is None:
            self.tail = self.head = LinkedListNode(value)
        else:
            self.tail.next = LinkedListNode(value)
            self.tail = self.tail.next
        return self.tail

    def add_to_beginning(self, value):
        if self.head is None:
            self.tail = self.head = LinkedListNode(value)
        else:
            self.head = LinkedListNode(value, self.head)
        return self.head

    def add_multiple(self, values):
        for v in values:
            self.add(v)

    def generate(self, n, min_value, max_value):
        self.head = self.tail = None
        for i in range(n):
            self.add(randint(min_value, max_value))
        return self

Upvotes: 1

Views: 134

Answers (1)

Gavin Achtemeier
Gavin Achtemeier

Reputation: 325

The line you think has a problem is not your problem. This code shows why:

def checker(ll):
    current = ll.tail = ll.head
    print(current)
    print(ll.tail)
    print(ll.head)
    return
ll = LinkedList()
ll.generate(10,0,99)
print(ll)
checker(ll)
print(ll.tail) 
print(ll.head)
print("Some other interesting behavior:")
ll.head.value = -1
print(ll.head)
print(ll.tail)
ll.head = -2
print(ll.head)
print(ll.tail)

Using your own code for the LL gives:

73 -> 39 -> 14 -> 5 -> 47 -> 29 -> 14 -> 66 -> 70 -> 9
73
73
73
73
73
Some other interesting behavior:
-1
-1
-2
-1

so the linked list which you pass does change when modified within a function. Also note the behavior at the end: ll.tail is now pointing to where ll.head was pointing to, not ll.head itself. This is different from C's pointer references.

This implies that your algorithm is not doing what you expect. particularly I would focus on when the loop ends and the order of swapping it performs (generally that's where most errors with LL activities seem to occur).

General debugging techniques like unit-testing a potential function (or anticipated error cause) are really important programming skills. If you think something doesn't (or does) work then test it. It'll narrow the scope of your error search and help others answer your question more quickly if you can't figure it out yourself.

Upvotes: 1

Related Questions