CODEWITHSUNDEEP
python
cnxwelcomes
cnxwelcomes

Reputation: 23

Python Singly Linked Lists with Tails

I have a linked list that I would like to implement as a queue. I have figured out that it works but I have a question about why this specific part works. Here is the code:

class LinkedQueue:
    class _Node:
        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def enqueue(self, e):
        newest = self._Node(e, None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size += 1

If the queue is empty and I enqueue, the first conditional in enqueue is true and is triggered and newest is assigned to self._head. But, when I add another element, the else block is triggered, and self._tail._next is assigned newest. This, apparently, changes the _next variable for _head. However, when assigning a third element, the _next variable for _head is not changed. Why is this so? Also, shouldn't _tail be changed by newest, and as such the _next variable is overridden by the newly assigned None?

The code works completely, and I understand the linked list logic, but I don't understand why this specific code works.

Upvotes: 2

Views: 450

Answers (2)

agaust
agaust

Reputation: 97

Maybe you can check this reference... http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementingaQueueinPython.html

you can use The Queue Abstract Data Type.. http://interactivepython.org/runestone/static/pythonds/BasicDS/TheQueueAbstractDataType.html

Upvotes: 0

Alex Martelli
Alex Martelli

Reputation: 882391

You ask:

self._tail._next is assigned newest. This, apparently, changes the _next variable for _head.

Yes, because at that time _tail and _head are two names for the same object.

So of course assigning to _tail._next has exactly the same effect as assigning to _head._next would have -- how could it not, since _tail and _head refer to the very same object?

Let's see how comes that they refer to the same object! When the if branch executes, you do self._head = newest; then inconditionally after the if/else you do self._tail = newest. Assignment, in Python, is always by reference -- assignment (to a name [*]) itself never implicitly makes a copy.

(Assignment to a slice of a list is a very different operation, whence this pedantic parentheses -- but let's forget it for now, since you're not dealing in assignments to slices:-).

However, when assigning a third element, the _next variable for _head is not changed. Why is this so?

Because at that time it is not any more true that _tail and _head are two names for the same object: they are then names of different objects.

That's because the second time around you had assigned something different (newest) to self._tail - but had assigned nothing new to self._head, which therefore still refers to the previous object... which _tail doesn't refer to any longer.

Also, shouldn't _tail be changed by newest, and as such the _next variable is overridden by the newly assigned None?

self._tail is indeed re-bound ("changed" is a very vague term!-) to refer to the same object as newest, so if you printed self._tail._next at that time (at the very end of the enqueue method) you would indeed see it as None. But the immediately-previous assignment to self._tail._next affects the _next attribute of what self._tail referred to at that time (before the self._tail=newest!) -- the node that with the new assignment to self._tail immediately becomes the penultimate one in the list.

Upvotes: 2

Related Questions