Explanation about pointers vs manipulating objects in a linked list

Question

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!

Community · Accepted Answer · 2020-06-20 09:12:55Z

1

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.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Apr 10, 2020 at 23:19

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

2293 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

able-leopard Over a year ago

Thanks for taking the time to answer this! I still don't understand why fast = fast.next DOES NOT manipulate the head while fast.next = fast.next.next DOES manipulate the head. I have edit my question above with an example. Thanks!

Collectives™ on Stack Overflow

Explanation about pointers vs manipulating objects in a linked list

1 Answer 1

What happens?

Note:

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

What happens?

Note:

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related