CODEWITHSUNDEEP
pythonlistdata-structurestailhead
geekt
geekt

Reputation: 2646

How tail works within a linked structures?

I am new into programming and I am learning more complex Data Structures using Python and I find difficult to understand the concept of adding an element to a linked list using a head and a tail.

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


 def add(self, item):
        newNode = _BagListNode(item)
        if self._head is None:
            self._head = newNode
        else:
            self._tail.next = newNode
        self._tail = newNode
        self._size += 1

class _BagListNode(object):
    def __init__(self, item):
        self.item = item
        self.next = None
    def __repr__(self):
        return f"{self.item}"

The point is when I add the first element, everything clear. As the head is None at first, it'll add the newNode to both tail and head. The problem starts when I add the second element: I do not understand why the second element is added to the element that has been added before, at the same time with the self._tail when this line of code self._tail.next = newNode is executed. After this line of code, the self._tail becomes the second element and this seems pretty logical as I have to keep tracking the tail as I keep on adding elements and self._head now have two elements but in code there is no line of code where to self._head is added a new element.

For example:

bag = Bag()
    bag.add(1)
    bag.add(2)
    bag.add(3)
print(bag._head.item, bag._head.next.item, bag._head.next.next.item)

and the result is:

1 2 3

I hope my question is clear enough. I appreciate your time so much. Thank you!

Upvotes: 1

Views: 124

Answers (1)

rudiejd
rudiejd

Reputation: 392

After this line of code, the self._tail becomes the second element and this seems pretty logical as I have to keep tracking the tail as I keep on adding elements and self._head now have two elements but in code there is no line of code where to self._head is added a new element.

I think what you might be missing here is that self._head is not a Bag in and of itself, but rather a pointer to a _BagListNode object.

When new items are added on to the bag, they are affixed as the next node on the previous tail, becoming the new tail. This does not affect the head at all in your implementation. An alternative, perhaps clearer, implementation could simply make an item the new head of the list, as pictured here:

Linked List adding procedure (general case)

One tip my data structures professor gave me was to draw a picture of what is happening to improve your intuitive understanding. You might consider drawing a picture of what happens when the third item is inserted into the bag.

Upvotes: 1

Related Questions