Question

In Python, I've created a Node class for implementing a singly linked list.

My Code:

class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext

class SinglyLinkedList:

def __init__(self):
self.head = None

def add(self,key):
addkey = Node(key)
addkey.setNext(self.head)
self.head = addkey

Now the question is: Create an append method that is O(1) by modifying the constructor of the SinglyLinkedList class by adding another instance variable. You will need to make a modification to the add method as well.

Answer 1

SOURCE CODE:

*Please follow the comments to better understand the code.

**Please look at the Screenshot below and use this code to copy-paste.

***The code in the below screenshot is neatly indented for better understanding.

Please see the BOLD code for updated code.

class Node:
def __init__(self,initdata):
self.data = initdata
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setData(self,newdata):
self.data = newdata
def setNext(self,newnext):
self.next = newnext
  
class SinglyLinkedList:
  
def __init__(self):
self.head = None
# Add a tail instance variable for the linked list
# So that we can know the end of the linked list.
self.tail = self.head
  
def add(self,key):
addkey = Node(key)
# We have to set the head's next to the addKey Node.
self.head.setNext(addKey)
# Make the tail point to newly created node.
self.tail = addKey
  
# Append at the last
def append(self,key):
# create a node
appendKey=Node(key)
  
# append it to the tail of the SinglyLinkedList
self.tail.next=appendKey
  
# make this appendKey node as the new tail
self.tail=appendKey
  
  

=======