Okay, So I have been doing linked lists for some time now and I have stumbled upon something, consider the following python code:
def EndInsertion(head,key):
curr = head
if head == None:
new_head = Node(key)
return new_head
else:
new_node = Node(key)
while curr.next != None:
curr = curr.next
curr.next = new_node
return head
def printList(head):
if head == None:
print(None)
curr = head
while curr != None:
print(curr.key, end = " ")
curr = curr.next
class Node:
def __init__(self,key):
self.key = key
self.next = None
head = None
printList(head)
head = EndInsertion(head,26)
head = EndInsertion(head,35)
head = EndInsertion(head,33)
printList(head)
I don't particularly understand the reason of returning the head of a Linked List here, except for when we are inserting the first node in the linked list ? Now see this code:-
class Node:
def __init__(self,key):
self.key = key
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def insert(self,key):
new_node = Node(key)
if self.head == None:
self.head = new_node
else:
curr = self.head
while curr.next != None:
curr = curr.next
curr.next = new_node
Here, we do not return the head of the linked list ? how does the linked list I created know about the head being updated everytime I insert the element in it ?
You have presented implementations that take a different approach. The first one only defines a Node class and leaves it to the user of the linked list to manage their own head reference. The second implementation takes this responsibility out of the hands of the user and manages it with the container class LinkedList.
Now to your questions:
I don't particularly understand the reason of returning the head of a Linked List here, except for when we are inserting the first node in the linked list ?
Indeed, it is only needed for when inserting the first node. But what if the logic in the main program is much more unpredictable, for instance when you have a user menu where the user is allowed to choose to insert or delete an element from the linked list. Then you would need to check whether you are in the special case where the list is empty to make sure you use the return value to assign it to head... So it makes sense to always assign to head even when you know it wasn't really necessary if the list was not empty: it saves you from doing the extra empty-test.
Here, we do not return the head of the linked list ?
With the second implementation, the user of the linked list is not supposed to be bothered with managing the head of the list. This is now done by the LinkedList class logic.
how does the linked list I created know about the head being updated every time I insert the element in it ?
First of all, it doesn't have to be updated every time. This is also true with the first implementation as you correctly noticed.
In this implementation (the one with LinkedList), the chosen logic was to perform the check on whether the list is empty or not, and only update the self.head attribute when the list is empty.
It could also have been implemented differently, where the assignment to self.head always happens. But it is important to realise that this assignment changes nothing when the list was not empty, i.e. in that case the assigned reference is the same as what self.head already was before the assignment.
Just to illustrate that the second implementation could also have chosen to always assign to self.head, I provide here such an alternative implementation:
class LinkedList:
def __init__(self):
self.head = None
def insert(self, key):
head = self.head
if head is None:
head = Node(key)
else:
new_node = Node(key)
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
self.head = head # Always assigned