Home > Net >  After shifting values in linked list. Changing values in the head alters 2 nodes at once
After shifting values in linked list. Changing values in the head alters 2 nodes at once

Time:12-22

Description

So I decided to make a snake game in Python using PyGame. For fun I decided to represent the snake using a linked list. Originally I had thought that to move the snake I would have to shift every value toward the head node's new destination location and then subsequently update the head node with it's new destination. I quickly realized this method was overcomplicated and unnecessary. However, in my attempt to implement it by shifting all values in a linked list toward the head and subsequently updating the head with it's new value I ended up breaking my linked list.

Here is what happens after I run the code to shift values and update the head. The head is the top row of the table.

Original printout of data in linked list

x y
100 50
90 50
80 50
70 50

Data Printout after shifting values

x y
100 50
100 50
90 50
80 50

This is what we want. Each row has shifted properly. All that needs to be done is to update the head. In this case the snake is going up and the interval is 10 so we would update y in the head by 10. When done this is what happens.

x y
100 60
100 60
90 50
80 50

When updating the data in the head the next node is now also updated simultaneously. The same thing happens if I try to update the second node in the same manner after shifting the data. If I try to do this before I shift values everything works fine so there seems to be something that is happening when I shift values. I checked the memory addresses of each node and by print(node) and they were all different.

Also, if I update the data property of the 3rd or 4th node it works fine and others are left unchanged. So this is just characteristic of the first and second node after shifting.

Here is the code I wrote to shift the values in my list

    def Move(self, direction):
        if(direction == 'UP'):
            
            oldvalue = self.linkedlist.head.data

            tempnode = self.linkedlist.head
            tempv = None
            while(tempnode.nextnode is not None):
                tempnode = tempnode.nextnode
                tempv = tempnode.data
                tempnode.data = oldvalue
                oldvalue = tempv

            self.linkedlist.printList()
            
        self.linkedlist.head.data[1]  = 10

If that is hard to understand I simply use 2 temporary variables to both store the data in the current node and the data in the previous node. Update the next node with the previous nodes data and then store the current nodes data again in tempv.

Just in case I will provide the code for my linked list implementation below.

from Node import Node

class LinkedList:
    def __init__(self):
        self.head = None

    def printList(self):
        
        printnode = self.head

        while(printnode is not None):
            print(f'{printnode.data}')
            printnode = printnode.nextnode
        print('')
class Node:
    def __init__(self, data = None):
        self.data = data
        self.nextnode = None

Thank you for any help and I apologize if the solution is simple. I stared for hours and also tried to find a similar post to no avail.

CodePudding user response:

I am not completely sure if I understand what is going on. But I suspect there is something going wrong when copying the data. Please note that in Python, if you set a variable to another object (class), it is passed by reference and not by value.

For example:

class ExampleClass:
    def __init__(self, value):
        self.value = value

A = ExampleClass(5)
B = A
B.value = 3
print(A.value) # prints 3

Not only classes are passed by reference, but lists as well. It seems like you are passing/setting the data (which I think is a list?) of the previous node to the next node. You are not copying the contents of the data, but passing a reference to this data list. This might cause the behavior you are seeing. You could mitigate this by using copy() or by slicing a list. For example:

b = a.copy()

new_l = l[:]

Also, see the Python FAQ on copying an object.

CodePudding user response:

Since you copy ("shift") the data from the head node to its successor node, they both have a reference to the same data. So any manipulation to that data will be visible in both nodes.

This does not happen with other nodes, because the source node -- from which the data is copied -- itself gets the value from its predecessor, so in that case there are no two nodes sharing the same data. But the head node did not get data from its predecessor, because ... it has no predecessor.

So you'll need to create a new data list from the data you read from the head node. This you can do by replacing:

 oldvalue = self.linkedlist.head.data

with:

 oldvalue = self.linkedlist.head.data[:]

Then it will work.

  • Related