standard05.md

STD 05 - Implement an Insert Method for a Linked List

Intro

In a linked list, each node contains a value and a pointer to the next node in the list. When inserting a new node, we need to update the pointers of the previous and next nodes to connect the new node in the correct place.

Task

You will need to have studied the lecture Data Structures 2, on Aula, Week 5, Slides 52 to 83.

Use the python code. Add an insert method to correctly add the day of the week that is missing (NB the week runs from Monday to Sunday). The code currently outputs the following:

Mon
Tue
Thur
Fri
Sat
Sun

So we need to add ‘Weds’. To do this, create an insert method. There is Insert Function to get you started. You’ll need to add code after the else case.

You will need to add a new command to insert the missing value, and this should appear before the existing command to print the list.

The result should be:

Mon
Tue
Weds
Thur
Fri
Sat
Sun

Python code 1

def Insert(self,val_before,newdata):
    if val_before is None:
        print("No node to insert after")
        return
    else:
        # your code here

Python code 2

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

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

    def listprint(self):
        printval = self.headval
        while printval is not None:
            print (printval.dataval)
            printval = printval.nextval
            
    def AtBeginning(self,newdata):
        NewNode = Node(newdata)

    def AtEnd(self, newdata):
        NewNode = Node(newdata)
        if self.headval is None:
            self.headval = NewNode
            return
        last = self.headval
        while(last.nextval):
            last = last.nextval
        last.nextval = NewNode
        

list = SLinkedList()
list.headval = Node("Mon")

e2 = Node("Tue")
e3 = Node("Thur")
e4 = Node("Fri")
e5 = Node("Sat")
list.headval.nextval = e2
e2.nextval = e3
e3.nextval = e4
e4.nextval = e5


list.AtEnd("Sun")

list.listprint()