CODEWITHSUNDEEP
pythondata-structureslinked-list
MertTheGreat
MertTheGreat

Reputation: 598

Python Linked List Implementation and Object Modeling

I am trying to implement Single Linked List on Python and the Code below works fine but I can not understand how:

class Node(object):
    def __init__(self, data=None, ):
        self.value = data
        self.next = None

class LinkedList1(object):
    def __init__(self, data=None):
        self.head = Node(data)
        self.tail = self.head
        self.length = 1

    def append(self, data):
        self.tail.next = Node(data)
        self.tail = self.tail.next
        self.length += 1
        return self

    def show_list(self):
        head_copy = self.head
        while head_copy is not None:
            print(head_copy.value)
            head_copy = head_copy.next

When we test it:

linkin = LinkedList1(10)
linkin.append(20)
linkin.append(30)
linkin.append(40)
linkin.show_list()

output :

10
20
30
40

What I don't understand is append function. I know self.tail referencing self.head but how come sefl.tail.next adds the new Node(data) to the at the last next, in my logic without a loop it should add to first next.

Plus if we write the function this way:

def append(self, data):
        self.head.next = Node(data)
        self.tail = self.head.next
        self.length += 1
        return self

This doesn't work even if self.tail reference to self.head.

I know I am missing something here. Can you help me understand?

Thank you.

Upvotes: 4

Views: 115

Answers (2)

Geoduck
Geoduck

Reputation: 9003

self.tail is only set to self.head when there is a single node. tail is always changed to point to the LAST node, which is the same as the head node only before the second node is added.

Every time append is called, tail is changed to point to the node that was just added.

It doesn't make much sense to append to the first node, does it? That would get rid of the rest of the list.

Let's take it line by line:

def append(self, data):
        self.tail.next = Node(data)

Before this is executed, self.tail.next is None, which indicates the list ends there. Now that we've set it to a new Node, that new node has a "next" value that is None.

         self.tail = self.tail.next

Since self.tail needs to point to the LAST item in the list, we need to change it. So, the above line changes it to point to the NEW last item.

         self.length += 1
         return self

These just keep track of length and return. As long as it is done correctly, you won't need to run through the list just to know how many nodes are in it.

Upvotes: 2

Gowtham Venkat
Gowtham Venkat

Reputation: 31

If you refer to the class Node, it has two objects: value and next Node.

In the Linked list implementation, it is implemented in such a way that the tail Node information is stored as well. In the append function, self.tail.next = Node(data) basically adds a new node after the tail node and self.tail = self.tail.next reassigns the Linked list's tail node to the newly created Node (which is now the last node of the list)

For example, let's take the following code:

linkin = LinkedList1(10)
linkin.append(20)
linkin.append(30)
linkin.append(40)
linkin.show_list()
  1. A Linked list is created with self.head -> Node(10) and self.tail -> Node(10)
  2. Appending 20 changes the list: self.head -> Node(10), self.tail.next -> Node(20) [which is same as self.head.next] 10 -> 20 where 10 is head and 20 is tail
  3. Appending 30 changes the list: self.tail.next -> Node(30) [self.tail here is Node(20)] and Node(30) is now made as tail 10 -> 20 -> 30 where 10 is head and 30 is tail

Hope this helps.

Upvotes: 2

Related Questions