CODEWITHSUNDEEP
pythonobjectpointerslinked-listnodes
able-leopard
able-leopard

Reputation: 115

Explanation about pointers vs manipulating objects in a linked list

I am having trouble wrapping my head around the concept of switching pointers vs actual manipulation of objects in a linked list.

Here is the code for building the linked list from scratch

class ListNode:

    def __init__(self, val:int, nextNode=None):
        self.val = val
        self.next = nextNode

class LinkedList:

    def __init__(self, val=None):

        self.head = None
        self.tail = None

    def addValue(self, val:int):
        if self.head == None:
            self.head = self.tail = ListNode(val)

        else:
            self.tail.next = ListNode(val)
            self.tail = self.tail.next
        return self.tail

    def addMultiple(self, values:list):

        for i in values:
            self.addValue(i)


    def add_to_beginning(self, val):
        if self.head == None:
            self.head = self.tail = ListNode(val)
        else:
            self.head = ListNode(val, self.head)

    def display(self):

        elems = []

        curr = self.head
        while curr:
            elems.append(curr.val)
            curr = curr.next

        print(elems)

creating a linked list here:

l1 = LinkedList()
l1.addMultiple([1,2,3,4,5])

For example if I wanted to move the nth element to the head, so I created this function

class Solution:

    def move_n_to_head(self, head, n):

        if head == None:
            return None
        if head.next == None:
            return head

        temp = None
        count = 0
        dummy = fast = slow = ListNode(0)

        fast.next = head
        while fast:

            if count == n:
                temp = fast.next
                fast.next = fast.next.next #why does this line manipuate the head?
                break

            fast = fast.next #why does this line NOT manipulate the head?
            count += 1

        slow.next = temp
        slow.next.next = head
        return dummy.next

Everything works fine and I got the solution I wanted, but specifically I don't understand why this line does manipulate the head?

fast.next = fast.next.next

After using this above line in the 3rd iteration, the head now becomes [1,2,3,5]

However while this line does not manipulates the head as I am traversing through the list? The head remains [1,2,3,4,5] after every iteration?

fast = fast.next

I read this other stackoverflow explanation on dummy node pointers which was helpful but I still don't understand it.

Explanation about dummy nodes and pointers in linked lists

Thanks in advance!

Upvotes: 1

Views: 141

Answers (1)

sɪʒɪhɪŋ βɪstɦa kxɐll
sɪʒɪhɪŋ βɪstɦa kxɐll

Reputation: 229

First of all, it is good to see such a clear and easy to read code. Now, the reason why the following line doesn't work

fast.next = head #fast is an object.

is because you are declaring fast as an object

dummy = fast = slow = ListNode(0) #just here

What happens?

In python you are working with objects rather than pointers (and pointers really aren't that, they are references.

Sometimes some variables passed or created are interpreted as objects and sometimes as pointers (references).

Well, you will see:

Python doesn't need pointers in order to achieve this as every variable is a reference to an object. These references are slightly different from C++ references, in that they can be assigned to - much like pointers in C++. (obmarg)

It is quite hard to tell you how to make the lenaguage interpret variables as object references.

If I think about it well, it may be done in this case with the following modification

class Solution:

    def move_n_to_head(self, head, n):

        if head == None:
            return None
        if head.next == None:
            return head

        temp = None
        count = 0
        dummy = slow = ListNode(0)

        fast = head #fast now "points" to head 
        # (it depends if it is taken as a copy of head or a reference to it)
        while fast:

            if count == n:
                temp = fast.next
                fast.next = fast.next.next #It should be solved
                break

            fast = fast.next
            count += 1

        slow.next = temp
        slow.next.next = head
        return dummy.next

Note:

This post discusses how to implement pointers in python, and may give you more information about how to handle them.

I really hope it helps you, thanks for reading this answer.

Upvotes: 1

Related Questions