Question

I need a python 3 help. Please help me with this question

Part 2. Linked Lists

You start working with the class LinkNode that represents a single node of a linked list. It has two instance attributes: value and next.

class LinkNode: def __init__(self,value,nxt=None): assert isinstance(nxt, LinkNode) or nxt is None self.value = value self.next = nxt

Before you start with the coding questions, answer the following questions about the constructor

Valid Constructor or Not?

1. LinkNode(1, 3)
2. LinkNode(1, None)
3. LinkNode(1, LinkNode(4, None))
4. LinkNode(1, None)
5. LinkNode()

Try to predict the output.

>>> r = LinkNode(1, LinkNode(2, LinkNode(3, None))) >>> r.value

>>> r.next >>> r.next.next >>> r.next.value

>>> r.next.next.value

Question 2.1. Empty Node

In some cases in it convenient to have a notion of an empty linked list. Usually it means that the linked list does not have any elements in it. In order to keep things simple (for now) we will assume that the list is empty, if it has a single node and its value is None.

Add a function is_empty to class LinkNode that checks whether a node is an empty node.

class LinkNode:

"""

>>> node = LinkNode(6, LinkNode(5, None))

>>> node.is_empty()

False

>>> node = LinkNode(None, None)

>>> node.is_empty()

True

"""

def __init__(self,value,nxt=None):

assert isinstance(nxt, LinkNode) or nxt is None

self.value = value

self.next = nxt

def is_empty(self):

# Your code is here

Question 2.2. Print Linked List

The representation of linked list that we used in class is not very convenient for people to comprehend. Therefore, the first function I'd like you to write

will take a linked list as an argument and will print it using box-and-pointer notation. (This function is not a part of the class)

You can assume that there is only one empty node and it will represent an empty linked list.

def print_list (lst):

  """ Prints linked list in a readable format

>>> print_list(LinkNode(3, None))

3 -> None

>>> print_list(LinkNode(3))

3 -> None

>>> print_list(LinkNode(3, LinkNode(2, LinkNode(1, None))))

3 -> 2 -> 1 -> None

>>> print_list (LinkNode(None, None))

empty list

"""

        # Your code is here

Question 2.3. Linked List Length

How many elements are in your linked list? Who knows...there are no function to use. Yeah..it means you have to write one. Please, write a function that returns

the length of a given linked list (number of elements in it).

You can solve this problem recursively.

def list_length(lst):

  """ Returns the number of elements in the linked list

>>> list_length(LinkNode(3, None))

1

>>> list_length(LinkNode(3))

1

>>> list_length(LinkNode(None, None))

0

>>> list_length(LinkNode(3, LinkNode(2, LinkNode(1, None))))

3

"""

  # Your code is here

Question 2.4. Find element at index

Linked List are not arrays. It means you have to start at the beginning of the linked list to get to a certain place, looping though one element at the time.

Write a function that loops though the list and returns a value at the given index. If index is out of bounds, it reports the error to the user. See doctests for more details.

def get_item(lst, index):

  """ Returns an element at the given index

>>> get_item(LinkNode(3, LinkNode(2, LinkNode(1, None))), 1)

2

>>> get_item(LinkNode(3, LinkNode(2, LinkNode(1, None))), 0)

3

>>> get_item(LinkNode(3, LinkNode(2, LinkNode(1, LinkNode(0, LinkNode(17))))), 4)

17

>>> get_item(LinkNode(3, LinkNode(2, LinkNode(1, None))), 4)

'index is out of bounds'

>>> get_item(LinkNode(3, LinkNode(2, LinkNode(1, None))), -4)

'index is out of bounds'

>>> get_item(LinkNode(None, None), 0)

'list is empty'

"""

        # Your code is here

Answer 1

About constructors.

2,3,4 constructors are valid.

Because,they are in a format we used to assign linked list.

constructor 1 is invalid. Because,it claims Assertion Error in the constructor second argument act like pointer .

But 3 is not a pointer thats why it claims Assertion Error.

Constructor 5 is invalid. Because,we have to pass one of the argument,or we can pass None as a argument if we want

to create an empty Linked List.  

code:

class LinkNode:

   def __init__(self,value,nxt=None):
  
       assert isinstance(nxt, LinkNode) or nxt is None

       self.value = value

       self.next = nxt

def print_list(lst):

   temp = lst
   if(is_empty(lst)):
       print("empty list")
   else:
       while temp:

           print(temp.value, end="->")

           temp = temp.next
       print ("None")
       print()

def is_empty(lst):
   if lst.value is None:
       return True
   else:
       return False
          
def list_length(lst):

   temp = lst
   k=0
  
   if(is_empty(lst)):
       return 0
   while temp:
       k=k+1
       temp = temp.next
          
   return k      
  
      
      
def get_item(self, data):
   current = self
   found = False
   if data<0:
       return "Index is out of Bounds"
   if (is_empty(self)):
       return "list is empty"
   for k in range(0,data):
       if current and found is False:
           if k == data:
               found = True
           else:
               current = current.next
       if current is None :
           return "Index is out of Bounds"
   return current.value
  
  
print()  
print("Predict the outputs")
r = LinkNode(1, LinkNode(2, LinkNode(3, None)))
print(r.value)
r.next
print(r.next.value)
r.next.next
print(r.next.next.value)

print()
print("Usage of is_empty function")

print(is_empty(LinkNode(6, LinkNode(5, None))))
print(is_empty(LinkNode(None,None)))
print()
print("Usage of Print_list function")

print_list(LinkNode(3, None))
print_list(LinkNode(3))
print_list(LinkNode(3, LinkNode(2, LinkNode(1, None))))
print_list (LinkNode(None, None))

print()
print("Usage of List_length function")

print(list_length(LinkNode(3, None)))
print(list_length(LinkNode(3)))
print(list_length(LinkNode(None, None)))
print(list_length(LinkNode(3, LinkNode(2, LinkNode(1, None)))))

print()
print("Usage of get_item function")

print(get_item(LinkNode(3,LinkNode(2,LinkNode(1,None))),1))

print(get_item(LinkNode(3,LinkNode(2,LinkNode(1,None))),0))

print(get_item(LinkNode(3,LinkNode(2,LinkNode(1,LinkNode(0,LinkNode(17))))),4))

print(get_item(LinkNode(3,LinkNode(2,LinkNode(1,None))),4))

print(get_item(LinkNode(3,LinkNode(2,LinkNode(1,None))),-4))

print(get_item(LinkNode(None,None),0))

output:

Predict the outputs sage of is_empty function False lrue sage of Print_list function 3-〉None З->None 3-2-1->None empty list Usage of List_length function sage of get item function 17 Index is out of Bounds Index is out of Bounds list is empty

If you have any queries, please comment below.

Please upvote , if you like this answer.