

from typing import Any



class       __snake_case  :

  def __init__(					self						,		_A):
      SCREAMING_SNAKE_CASE_									=						data
      SCREAMING_SNAKE_CASE_									=						None


  def __repr__(					self):
      return f"""Node({self.data})"""






class       __snake_case  :

  def __init__(					self):
      SCREAMING_SNAKE_CASE_									=						None

  def __iter__(					self):
      SCREAMING_SNAKE_CASE_									=						self.head
      while node:
          yield node.data
          SCREAMING_SNAKE_CASE_									=						node.next

  def __len__(					self):
      return sum(1 for _ in self)

  def __repr__(					self):
      return "->".join([str(_A) for item in self])

  def __getitem__(					self						,		_A):
      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						,		_A						,		_A):
      if not 0 <= index < len(self):
          raise ValueError('list index out of range.')
      SCREAMING_SNAKE_CASE_									=						self.head
      for _ in range(_A):
          SCREAMING_SNAKE_CASE_									=						current.next
      SCREAMING_SNAKE_CASE_									=						data

  def 						lowerCAmelCase__     (					self						,		_A):
      self.insert_nth(len(self)						,		_A)

  def 						lowerCAmelCase__     (					self						,		_A):
      self.insert_nth(0						,		_A)

  def 						lowerCAmelCase__     (					self						,		_A						,		_A):
      if not 0 <= index <= len(self):
          raise IndexError('list index out of range')
      SCREAMING_SNAKE_CASE_									=						Node(_A)
      if self.head is None:
          SCREAMING_SNAKE_CASE_									=						new_node
      elif index == 0:
          SCREAMING_SNAKE_CASE_									=						self.head  # link new_node to head
          SCREAMING_SNAKE_CASE_									=						new_node
      else:
          SCREAMING_SNAKE_CASE_									=						self.head
          for _ in range(index - 1):
              SCREAMING_SNAKE_CASE_									=						temp.next
          SCREAMING_SNAKE_CASE_									=						temp.next
          SCREAMING_SNAKE_CASE_									=						new_node

  def 						lowerCAmelCase__     (					self):  # print every node data
      print(self)

  def 						lowerCAmelCase__     (					self):
      return self.delete_nth(0)

  def 						lowerCAmelCase__     (					self):  # delete from tail
      return self.delete_nth(len(self) - 1)

  def 						lowerCAmelCase__     (					self						,		_A = 0):
      if not 0 <= index <= len(self) - 1:  # test if index is valid
          raise IndexError('List index out of range.')
      SCREAMING_SNAKE_CASE_									=						self.head  # default first node
      if index == 0:
          SCREAMING_SNAKE_CASE_									=						self.head.next
      else:
          SCREAMING_SNAKE_CASE_									=						self.head
          for _ in range(index - 1):
              SCREAMING_SNAKE_CASE_									=						temp.next
          SCREAMING_SNAKE_CASE_									=						temp.next
          SCREAMING_SNAKE_CASE_									=						temp.next.next
      return delete_node.data

  def 						lowerCAmelCase__     (					self):
      return self.head is None


  def 						lowerCAmelCase__     (					self):
      SCREAMING_SNAKE_CASE_									=						None
      SCREAMING_SNAKE_CASE_									=						self.head

      while current:
          # Store the current node's next node.
          SCREAMING_SNAKE_CASE_									=						current.next
          # Make the current node's next point backwards
          SCREAMING_SNAKE_CASE_									=						prev
          # Make the previous node be the current node
          SCREAMING_SNAKE_CASE_									=						current
          # Make the current node the next node (to progress iteration)
          SCREAMING_SNAKE_CASE_									=						next_node
      # Return prev in order to put the head at the end
      SCREAMING_SNAKE_CASE_									=						prev






def 					_UpperCAmelCase       (  ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_									=						LinkedList()
    assert linked_list.is_empty() is True
    assert str(_SCREAMING_SNAKE_CASE       ) == ""

    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(_SCREAMING_SNAKE_CASE       ) == i
        linked_list.insert_nth(_SCREAMING_SNAKE_CASE ,   i + 1       )
    assert str(_SCREAMING_SNAKE_CASE       ) == "->".join(str(_SCREAMING_SNAKE_CASE       ) for i in range(1 ,   11       )       )

    linked_list.insert_head(0       )
    linked_list.insert_tail(11       )
    assert str(_SCREAMING_SNAKE_CASE       ) == "->".join(str(_SCREAMING_SNAKE_CASE       ) 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(_SCREAMING_SNAKE_CASE       ) == 9
    assert str(_SCREAMING_SNAKE_CASE       ) == "->".join(str(_SCREAMING_SNAKE_CASE       ) 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       ):
        SCREAMING_SNAKE_CASE_									=						-i
    assert all(linked_list[i] == -i for i in range(0 ,   9       )       ) is True

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


def 					_UpperCAmelCase       (  ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_									=						[
        -9,
        100,
        Node(77_345_112       ),
        'dlrow olleH',
        7,
        5_555,
        0,
        -192.55555,
        'Hello, world!',
        77.9,
        Node(10       ),
        None,
        None,
        12.20,
    ]
    SCREAMING_SNAKE_CASE_									=						LinkedList()

    for i in test_input:
        linked_list.insert_tail(_SCREAMING_SNAKE_CASE       )

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

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

    # Delete the tail
    SCREAMING_SNAKE_CASE_									=						linked_list.delete_tail()
    assert result == 12.2
    assert (
        str(_SCREAMING_SNAKE_CASE       ) == "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
    SCREAMING_SNAKE_CASE_									=						linked_list.delete_nth(10       )
    assert result is None
    assert (
        str(_SCREAMING_SNAKE_CASE       ) == "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(_SCREAMING_SNAKE_CASE       )
        == "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(_SCREAMING_SNAKE_CASE       )
    assert (
        str(_SCREAMING_SNAKE_CASE       )
        == "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(_SCREAMING_SNAKE_CASE       )
        == "None->None->Node(10)->77.9->Hello, world!->-192.55555->0->5555->"
        "7->dlrow olleH->Node(77345112)->100->Node(Hello again, world!)"
    )


def 					_UpperCAmelCase       (  ):





    """simple docstring"""


    from doctest import testmod

    testmod()

    SCREAMING_SNAKE_CASE_									=						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(_SCREAMING_SNAKE_CASE       )
    print('\nReading/changing Node data using indexing:'       )
    print(f"""Element at Position 1: {linked_list[1]}"""       )
    SCREAMING_SNAKE_CASE_									=						input('Enter New Value: '       ).strip()
    print('New list:'       )
    print(_SCREAMING_SNAKE_CASE       )
    print(f"""length of linked_list is : {len(_SCREAMING_SNAKE_CASE       )}"""       )


if __name__ == "__main__":
       main()








def 					_UpperCAmelCase       (  _SCREAMING_SNAKE_CASE					:		list ,   _SCREAMING_SNAKE_CASE					:		list ,   _SCREAMING_SNAKE_CASE					:		int ,   _SCREAMING_SNAKE_CASE					:		int ,   _SCREAMING_SNAKE_CASE					:		int       ):





    """simple docstring"""


    if index == number_of_items:
        return 0
    SCREAMING_SNAKE_CASE_									=						0
    SCREAMING_SNAKE_CASE_									=						0
    SCREAMING_SNAKE_CASE_									=						knapsack(_SCREAMING_SNAKE_CASE ,   _SCREAMING_SNAKE_CASE ,   _SCREAMING_SNAKE_CASE ,   _SCREAMING_SNAKE_CASE ,   index + 1       )
    if weights[index] <= max_weight:
        SCREAMING_SNAKE_CASE_									=						values[index] + knapsack(
            _SCREAMING_SNAKE_CASE ,   _SCREAMING_SNAKE_CASE ,   _SCREAMING_SNAKE_CASE ,   max_weight - weights[index] ,   index + 1       )
    return max(_SCREAMING_SNAKE_CASE ,   _SCREAMING_SNAKE_CASE       )


if __name__ == "__main__":
       import doctest

       doctest.testmod()


