Python Linked List Implementation and Object Modeling

Question

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 :

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.

Gowtham Venkat · Accepted Answer · 2019-11-06 12:22:15Z

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()

A Linked list is created with self.head -> Node(10) and self.tail -> Node(10)
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
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.

music_junkie · Accepted Answer · 2019-11-06 12:52:11Z

2

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.

edited Nov 6, 2019 at 12:52

music_junkie

1892 silver badges17 bronze badges

answered Nov 6, 2019 at 12:14

Geoduck

9,0212 gold badges29 silver badges27 bronze badges

2 Comments

MertTheGreat Over a year ago

Good explanation, do you mean this way tail reference holds all the nexts?

Geoduck Over a year ago

it doesn't hold all the nexts. Each node in the list holds just one "next", which is to the next item in the list. The tail always has NO next, since it is the last node and nothing comes after it.

Collectives™ on Stack Overflow

Python Linked List Implementation and Object Modeling

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related