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 AtBegin(self, newdata):

         NewNode = Node(newdata)

         NewNode.nextval = self.headval

         self.headval = NewNode

     # 在链表最后追加

     def AtEnd(self, newdata):

         NewNode = Node(newdata)

         if self.headval is None:

             self.headval = NewNode

             return

         laste = self.headval

         while laste.nextval:

             laste = laste.nextval

         laste.nextval = NewNode

     # 某个节点后插入节点

     def Atbetween(self, middle_node, newdata):

         if middle_node is None:

             print("The mentioned node is absent")

             return

         NewNode = Node(newdata)

         NewNode.nextval = middle_node.nextval

         middle_node.nextval = NewNode

     # 删除节点

     def RemoveNode(self, RemoveKey):

         Headval = self.headval

         if Headval is None:

             if Headval.dataval == RemoveKey:

                 self.headval = Headval.nextval

                 Headval = None

                 return

         while Headval:

             if Headval.dataval == RemoveKey:

                 break

             prev = Headval

             Headval = Headval.nextval

         if Headval is None:

             return

         prev.nextval = Headval.nextval

         Headval = None

 list1 = SLinkedList()

 list1.headval = Node('Mon')

 e2 = Node("Tue")

 list1.headval.nextval = e2

 e3 = Node("Wed")

 e2.nextval = e3

 list1.listprint()

 print('--------1----------')

 list1.AtBegin('sun')

 list1.listprint()

 print('---------2------------')

 list1.AtEnd('stu')

 list1.listprint()

 print('----------3-----------')

 list1.Atbetween(list1.headval.nextval, 'fri')

 list1.listprint()

 print('-----------4-----------')

 list1.RemoveNode('Wed')

 list1.listprint()