Question

Python linked lists

● Insert: this method takes a value as a parameter, and adds a node which
contains the value to the end of the linked list

● Delete: this method deletes a node from the linked list. If an index is
passed as a parameter, then the method should delete the node at this
index. If no index is passed, then delete the first item in the list

● Find: this method takes a value as a parameter, and returns the index of
the first node which contains this value. If no nodes are found to contain
this value, return False

● Reverse: this method reverses the Linked List

Python Code:

class Node:

    def __init__(self, dataval=None):

        self.dataval = dataval

        self.nextval = None

class LinkedList:

    def __init__(self):

        self.headval = None

    def __str__(self):

        node = self.headval

        output = "[ "

        while(node != None):

            output = output + str(node.dataval) + ", "

            node = node.nextval

        if(len(output) > 2):

            output = output[:-2]

        return output + " ]"

# DO NOT EDIT ANY CODE ABOVE THIS LINE

    def insert(self, val):

        # Fill in this method, which takes a value and adds a node which holds the value at the end of the linked list

    def delete(self, index=0):

        # Fill in this method, which takes an index(with a default value of 0), and deletes the node at the index specified

    def find(self, val):

        # Fill in this method, which takes in a value and returns the index of the first node which contains that value. If no node containing that value is found, return False

    def reverse(self):

        # Fill in this method, which reverses the list

#DO NOT EDIT ANY CODE PAST THIS LINE

# Tests

# Insertion

a = LinkedList()

a.insert(1)

a.insert(2)

a.insert('a')

a.insert(3)

print(str(a) == "[ 1, 2, a, 3 ]")

# Deletion

a.delete()

print(str(a) == "[ 2, a, 3 ]")

a.delete(2)

print(str(a) == "[ 2, a ]")

# Find

a.insert('b')

a.insert('c')

a.insert('b')

print(a.find('b') == 2)

print(a.find('c') == 3)

print(a.find('d') == False)

# Reverse

a.reverse()

print(str(a) == "[ b, c, b, a, 2 ]")

Answer 1

Complete code in python3:-

class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None

class LinkedList:
def __init__(self):
self.headval = None

def __str__(self):
node = self.headval
output = "[ "
while(node != None):
output = output + str(node.dataval) + ", "
node = node.nextval
if(len(output) > 2):
output = output[:-2]
return output + " ]"
# DO NOT EDIT ANY CODE ABOVE THIS LINE

def insert(self, val):
# Fill in this method, which takes a value and adds a node which holds the value at the end of the linked list
node = self.headval
# If list is empty, simply assign new node to self.headval and return
if node == None:
self.headval = Node(val)
return

# Else traverse whole list and insert new node at the end.
while node.nextval != None:
node = node.nextval
node.nextval = Node(val)

def delete(self, index=0):
# Fill in this method, which takes an index(with a default value of 0), and deletes the node at the index specified
node = self.headval
# If list is empty, simply return.
if node == None:
return
# If head node needs to be deleted.
if index == 0:
self.headval = node.nextval
del node
return
# else traverse list upto the correct position.
while index > 1 and node.nextval != None:
node = node.nextval
index -= 1
# If correct position present in list then delete it.
if index == 1 and node.nextval != None:
temp = node.nextval
node.nextval = temp.nextval
del temp

def find(self, val):
# Fill in this method, which takes in a value and returns the index of the first node which contains that value. If no node containing that value is found, return False
index = 0
node = self.headval
while node != None:
if node.dataval == val:
return index
index += 1
node = node.nextval
return False

def reverse(self):
# Fill in this method, which reverses the list
if self.headval == None:
return
# I'm using 3 pointer approach to reverse the list
prev = None
curr = self.headval
Next = curr.nextval
while Next != None:
curr.nextval = prev
prev = curr
curr = Next
Next = curr.nextval
curr.nextval = prev
self.headval = curr

#DO NOT EDIT ANY CODE PAST THIS LINE
# Tests
# Insertion
a = LinkedList()
a.insert(1)
a.insert(2)
a.insert('a')
a.insert(3)
print(str(a) == "[ 1, 2, a, 3 ]")
# Deletion
a.delete()
print(str(a) == "[ 2, a, 3 ]")
a.delete(2)
print(str(a) == "[ 2, a ]")
# Find
a.insert('b')
a.insert('c')
a.insert('b')
print(a.find('b') == 2)
print(a.find('c') == 3)
print(a.find('d') == False)
# Reverse
a.reverse()
print(str(a) == "[ b, c, b, a, 2 ]")

Screenshot of output:-