


from typing import Any







class 			_lowercase :


       """simple docstring"""




       def __init__(   self							:			List[Any]					,      __lowerCamelCase							:			Any       ):


             '''simple docstring'''



             lowerCamelCase__		:				Tuple    =  data
             lowerCamelCase__		:				Tuple    =  None





       def __repr__(   self							:			Optional[int]       ):


             '''simple docstring'''



             return f"Node({self.data})"







class 			_lowercase :


       """simple docstring"""




       def __init__(   self							:			Dict       ):


             '''simple docstring'''



             lowerCamelCase__		:				Tuple    =  None





       def __iter__(   self							:			Union[str, Any]       ):


             '''simple docstring'''



             lowerCamelCase__		:				Dict    =  self.head
             while node:
                   yield node.data
                   lowerCamelCase__		:				Optional[int]    =  node.next





       def __len__(   self							:			Union[str, Any]       ):


             '''simple docstring'''



             return sum(1 for _ in self       )





       def __repr__(   self							:			int       ):


             '''simple docstring'''



             return "->".join([str(__lowerCamelCase       ) for item in self]       )





       def __getitem__(   self							:			str					,      __lowerCamelCase							:			int       ):


             '''simple docstring'''



             if not 0 <= index < len(self       ):
                   raise ValueError("list index out of range."       )
             for i, node in enumerate(self       ):
                   if i == index:
                         return node
             return None





       def __setitem__(   self							:			Optional[int]					,      __lowerCamelCase							:			int					,      __lowerCamelCase							:			Any       ):


             '''simple docstring'''



             if not 0 <= index < len(self       ):
                   raise ValueError("list index out of range."       )
             lowerCamelCase__		:				int    =  self.head
             for _ in range(__lowerCamelCase       ):
                   lowerCamelCase__		:				Dict    =  current.next
             lowerCamelCase__		:				Any    =  data





       def 						lowerCAmelCase     (   self							:			Union[str, Any]					,      __lowerCamelCase							:			Any       ):


             '''simple docstring'''



             self.insert_nth(len(self       )					,      __lowerCamelCase       )





       def 						lowerCAmelCase     (   self							:			Optional[int]					,      __lowerCamelCase							:			Any       ):


             '''simple docstring'''



             self.insert_nth(0					,      __lowerCamelCase       )





       def 						lowerCAmelCase     (   self							:			str					,      __lowerCamelCase							:			int					,      __lowerCamelCase							:			Any       ):


             '''simple docstring'''



             if not 0 <= index <= len(self       ):
                   raise IndexError("list index out of range"       )
             lowerCamelCase__		:				str    =  Node(__lowerCamelCase       )
             if self.head is None:
                   lowerCamelCase__		:				List[Any]    =  new_node
             elif index == 0:
                   lowerCamelCase__		:				List[Any]    =  self.head  # link new_node to head
                   lowerCamelCase__		:				Union[str, Any]    =  new_node
             else:
                   lowerCamelCase__		:				str    =  self.head
                   for _ in range(index - 1       ):
                         lowerCamelCase__		:				str    =  temp.next
                   lowerCamelCase__		:				Dict    =  temp.next
                   lowerCamelCase__		:				List[str]    =  new_node





       def 						lowerCAmelCase     (   self							:			List[str]       ):  # print every node data


             '''simple docstring'''



             print(self       )





       def 						lowerCAmelCase     (   self							:			int       ):


             '''simple docstring'''



             return self.delete_nth(0       )





       def 						lowerCAmelCase     (   self							:			Any       ):  # delete from tail


             '''simple docstring'''



             return self.delete_nth(len(self       ) - 1       )





       def 						lowerCAmelCase     (   self							:			Dict					,      __lowerCamelCase							:			int = 0       ):


             '''simple docstring'''



             if not 0 <= index <= len(self       ) - 1:  # test if index is valid
                   raise IndexError("List index out of range."       )
             lowerCamelCase__		:				List[Any]    =  self.head  # default first node
             if index == 0:
                   lowerCamelCase__		:				Optional[Any]    =  self.head.next
             else:
                   lowerCamelCase__		:				Dict    =  self.head
                   for _ in range(index - 1       ):
                         lowerCamelCase__		:				Union[str, Any]    =  temp.next
                   lowerCamelCase__		:				str    =  temp.next
                   lowerCamelCase__		:				Tuple    =  temp.next.next
             return delete_node.data





       def 						lowerCAmelCase     (   self							:			Union[str, Any]       ):


             '''simple docstring'''



             return self.head is None





       def 						lowerCAmelCase     (   self							:			Dict       ):


             '''simple docstring'''



             lowerCamelCase__		:				Union[str, Any]    =  None
             lowerCamelCase__		:				Any    =  self.head

             while current:
                   # Store the current node's next node.
                   lowerCamelCase__		:				Union[str, Any]    =  current.next
                   # Make the current node's next point backwards
                   lowerCamelCase__		:				Any    =  prev
                   # Make the previous node be the current node
                   lowerCamelCase__		:				List[Any]    =  current
                   # Make the current node the next node (to progress iteration)
                   lowerCamelCase__		:				List[Any]    =  next_node
             # Return prev in order to put the head at the end
             lowerCamelCase__		:				Optional[int]    =  prev



def       lowercase_		(		):

      """simple docstring"""




      lowerCamelCase__		:				Union[str, Any]    =  LinkedList()
      assert linked_list.is_empty() is True
      assert str(_A						) == ""

      try:
            linked_list.delete_head()
            raise AssertionError  # This should not happen.
      except IndexError:
            assert True  # This should happen.

      try:
            linked_list.delete_tail()
            raise AssertionError  # This should not happen.
      except IndexError:
            assert True  # This should happen.

      for i in range(10						):
            assert len(_A						) == i
            linked_list.insert_nth(_A    ,					i + 1						)
      assert str(_A						) == "->".join(str(_A						) for i in range(1    ,					11						)						)

      linked_list.insert_head(0						)
      linked_list.insert_tail(11						)
      assert str(_A						) == "->".join(str(_A						) for i in range(0    ,					12						)						)

      assert linked_list.delete_head() == 0
      assert linked_list.delete_nth(9						) == 10
      assert linked_list.delete_tail() == 11
      assert len(_A						) == 9
      assert str(_A						) == "->".join(str(_A						) for i in range(1    ,					10						)						)

      assert all(linked_list[i] == i + 1 for i in range(0    ,					9						)						) is True

      for i in range(0    ,					9						):
            lowerCamelCase__		:				int    =  -i
      assert all(linked_list[i] == -i for i in range(0    ,					9						)						) is True

      linked_list.reverse()
      assert str(_A						) == "->".join(str(_A						) for i in range(-8    ,					1						)						)

def       lowercase_		(		):

      """simple docstring"""




      lowerCamelCase__		:				Optional[int]    =  [
          -9,
          100,
          Node(77345112						),
          "dlrow olleH",
          7,
          5555,
          0,
          -192.55_555,
          "Hello, world!",
          77.9,
          Node(10						),
          None,
          None,
          12.20,
      ]
      lowerCamelCase__		:				Optional[int]    =  LinkedList()

      for i in test_input:
            linked_list.insert_tail(_A						)

      # Check if it's empty or not
      assert linked_list.is_empty() is False
      assert (
          str(_A						) == "-9->100->Node(77345112)->dlrow olleH->7->5555->0->"
          "-192.55555->Hello, world!->77.9->Node(10)->None->None->12.2"
      )

      # Delete the head
      lowerCamelCase__		:				List[str]    =  linked_list.delete_head()
      assert result == -9
      assert (
          str(_A						) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None->None->12.2"
      )

      # Delete the tail
      lowerCamelCase__		:				str    =  linked_list.delete_tail()
      assert result == 12.2
      assert (
          str(_A						) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None->None"
      )

      # Delete a node in specific location in linked list
      lowerCamelCase__		:				str    =  linked_list.delete_nth(10						)
      assert result is None
      assert (
          str(_A						) == "100->Node(77345112)->dlrow olleH->7->5555->0->-192.55555->"
          "Hello, world!->77.9->Node(10)->None"
      )

      # Add a Node instance to its head
      linked_list.insert_head(Node("Hello again, world!"						)						)
      assert (
          str(_A						)
          == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
          "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None"
      )

      # Add None to its tail
      linked_list.insert_tail(_A						)
      assert (
          str(_A						)
          == "Node(Hello again, world!)->100->Node(77345112)->dlrow olleH->"
          "7->5555->0->-192.55555->Hello, world!->77.9->Node(10)->None->None"
      )

      # Reverse the linked list
      linked_list.reverse()
      assert (
          str(_A						)
          == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
          "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
      )

def       lowercase_		(		):

      """simple docstring"""




      from doctest import testmod

      testmod()

      lowerCamelCase__		:				List[str]    =  LinkedList()
      linked_list.insert_head(input("Inserting 1st at head "						).strip()						)
      linked_list.insert_head(input("Inserting 2nd at head "						).strip()						)
      print("\nPrint list:"						)
      linked_list.print_list()
      linked_list.insert_tail(input("\nInserting 1st at tail "						).strip()						)
      linked_list.insert_tail(input("Inserting 2nd at tail "						).strip()						)
      print("\nPrint list:"						)
      linked_list.print_list()
      print("\nDelete head"						)
      linked_list.delete_head()
      print("Delete tail"						)
      linked_list.delete_tail()
      print("\nPrint list:"						)
      linked_list.print_list()
      print("\nReverse linked list"						)
      linked_list.reverse()
      print("\nPrint list:"						)
      linked_list.print_list()
      print("\nString representation of linked list:"						)
      print(_A						)
      print("\nReading/changing Node data using indexing:"						)
      print(F"Element at Position 1: {linked_list[1]}"						)
      lowerCamelCase__		:				Optional[Any]    =  input("Enter New Value: "						).strip()
      print("New list:"						)
      print(_A						)
      print(F"length of linked_list is : {len(_A						)}"						)


if __name__ == "__main__":
    main()






class 			_lowercase :


       """simple docstring"""




       def __init__(   self							:			Any					,      __lowerCamelCase							:			int       ):


             '''simple docstring'''



             lowerCamelCase__		:				List[str]    =  n
             lowerCamelCase__		:				Union[str, Any]    =  [None] * self.n
             lowerCamelCase__		:				List[str]    =  0  # index of the first element
             lowerCamelCase__		:				Any    =  0
             lowerCamelCase__		:				Any    =  0





       def __len__(   self							:			Tuple       ):


             '''simple docstring'''



             return self.size





       def 						lowerCAmelCase     (   self							:			Optional[int]       ):


             '''simple docstring'''



             return self.size == 0





       def 						lowerCAmelCase     (   self							:			Union[str, Any]       ):


             '''simple docstring'''



             return False if self.is_empty() else self.array[self.front]





       def 						lowerCAmelCase     (   self							:			str					,      __lowerCamelCase							:			List[str]       ):


             '''simple docstring'''



             if self.size >= self.n:
                   raise Exception("QUEUE IS FULL"       )

             lowerCamelCase__		:				Optional[Any]    =  data
             lowerCamelCase__		:				Tuple    =  (self.rear + 1) % self.n
             self.size += 1
             return self





       def 						lowerCAmelCase     (   self							:			Tuple       ):


             '''simple docstring'''



             if self.size == 0:
                   raise Exception("UNDERFLOW"       )

             lowerCamelCase__		:				Any    =  self.array[self.front]
             lowerCamelCase__		:				List[Any]    =  None
             lowerCamelCase__		:				str    =  (self.front + 1) % self.n
             self.size -= 1
             return temp


