IN PYTHON

Linked_list.py:

# DO NOT MODIFY FILE

from __future__ import annotations # allow self-reference from typing import TypeVar, Generic, List # function type

T = TypeVar("T")

class DLLNode: def __init__(self, val: Generic[T], nxt: DLLNode = None, prev: DLLNode = None): """ DO NOT MODIFY Initialize of double linked list node :param val: value of this node :param nxt: pointer to the next node :param prev: pointer to the previous node """ self.val = val # Value of this node self.nxt = nxt # Pointer to next node self.prev = prev

def __str__(self): """ DO NOT MODIFY Represent Doubly Linked List node as string :return: string represented Doubly linked list node """ return str(self.val)

def __repr__(self): """ DO NOT MODIFY Represent Doubly Linked List node as string :return: string represented Doubly linked list node """ return self.__str__()

class LinkedList: def __init__(self, container: List[T] = None): """ DO NOT MODIFY Initialize of Linked list with double linked list node :param container: container that contain the elements in linked list """ self.head = DLLNode(None) # Head of linked list self.tail = self.head # Tail of linked list

# If container presented, creating the rest of linked lish if container: cur = self.head for item in container: cur.nxt = DLLNode(item, prev=cur) cur = cur.nxt self.tail = cur

def linked_list_to_list(self): """ DO NOT MODIFY Converting the linked list to list :return: list that contain the same elements as linked list """ actual_list = [] node = self.head.nxt while node is not None: actual_list.append(node.val) node = node.nxt return actual_list

def __str__(self): """ DO NOT MODIFY Represent Linked List as string :return: string represented linked list """ return str(self.linked_list_to_list())

def __repr__(self): """ DO NOT MODIFY Represent Linked List as string :return: string represented linked list """ return self.__str__()

solution.py:

from typing import List, Tuple from linked_list import DLLNode, LinkedList

def pokemon_machine(pokemon: LinkedList, orders: List[Tuple]) -> LinkedList: """ """

def add_pokemon(cur_node: DLLNode, added_pokemon: str) -> None: """ """ pass

def remove_pokemon(cur_node: DLLNode) -> None: """ """ pass

def swap_pokemon(first_node: DLLNode, second_node: DLLNode) -> None: """ """ pass

return LinkedList()

Assignment Specifications Class DLLNode: DO NOT MODIFY the following attributes/functions This is doubly linked list node for providing you the linked list Attributes o val: T: Value held by this node. Note that this may be any type, such as a str, int, float, dict, or a more complex object. o nxt: DLLNode: Reference to the node that come after this node (may be None) o prev: DLLNode: Reference to the node that come before this node (may be None) __init__(self, value: T, next: Node = None, prev: Node = None) -> None o Initialize doubly linked list node o val: T: Value held by this node. Note that this may be any type, such as a str, int, float, dict, or a more complex object. o nxt : DLLNode: Reference to the node that come after this node (may be None) o prev: DLLNode: Reference to the node that come before this node (may be None) o return: None _str__(self) -> str and __repr__(self) -> str o Represents the Doubly Linked List Node as string o This function might help you debug in Pycharm since it automatically calls this function to show the class for you o return: string representing the node Class LinkedList: DO NOT MODIFY the following attributes/functions This is doubly linked list class will help you create the pokemon PC Attributes o head: DLLNode: The head of doubly linked list o tail: DLLNode: The tail of doubly linked list ___init__(self, container: List[T] = None) -> None o Initialize doubly linked list o container: List[T]: Container that contain the elements that will store in linked list o To reduce bug and error of linked list head, this function constructs the None node to be the header node. The rest of linked list data will push after this node. Note that this node cannot be removed. o If container is not None, this class will automatically generate the linked list that contains every element in the container. o return: None _str__(self) -> str and __repr__(self) -> str o Represent Doubly Linked List Node as string o This function might help you debug in Pycharm since it automatically calls this function to show the class for you o return: string represented entire linked list Warning: Do not convert the LinkedList to a built-in Python list until the very end of your function when you return. Solutions which simply convert the LinkedList to a Python list and use built-in operations to solve the problem will lose ALL credit. pokemon_machine (pokemon: Linkedlist, orders: List[Tuple]) -> LinkedList: o pokemon: LinkedList: The first input is a linked list of strings representing pokemon's name that are initially stored in the PC o orders: List[Tuple): The second input is a python list of three possible commands used to modify the PC The first command is for adding pokemon. This command is a tuple of length 3, where Index O is a string, "add" Index 1 is an integer representing the position to put the new pokemon Index 2 is string represented the name of new pokemon Must call add_pokemon The second command is for removing pokemon. This command is a tuple of length 2, where Index 0 is a string, remove" Index 1 an integer representing the position to remove pokemon from PC Must call remove_pokemon The last possible command is for swapping pokemons. This command is a tuple of length 3, where Index 0 is a string, swap" Index 1 an integer representing the position of the first pokemon to swap Index 2 an integer representing the position of the second pokemon to swap Must call swap_pokemon o Return: A linked list of strings represents the current pokemons within the PC in the right order. o Time Complexity: Olop). Where o is the length of the orders list and p is the length of the pokemon list add_pokemon(cur_node: DLLnode, add_pokemon: str) -> None o This is the inner function inside pokemon_machine. o This function will add pokemon after the current node o cur_node: str: Current node to add the next pokemon after this node o add_pokemon: str: Name of pokemon to add o Return: None o Time Complexity: O(1) remove_pokemon(cur_node: DLLnode) -> None o This is the inner function inside pokemon_machine. o This function will remove pokemon at the current node o cur_node: Current node to add the next pokemon after this node o Return: None o Time Complexity: 0(1) swap_pokemon(first_node: DLLnode, second_node: DLLnode) -> None o This is the inner function inside pokemon_machine. o This function will swap pokemon between the first node and the second node o first_node: DLLnode: The first node to swap o second_node: DLLnode: The second node to swap o return: None o Time Complexity: O(1) Assignment Specifications Class DLLNode: DO NOT MODIFY the following attributes/functions This is doubly linked list node for providing you the linked list Attributes o val: T: Value held by this node. Note that this may be any type, such as a str, int, float, dict, or a more complex object. o nxt: DLLNode: Reference to the node that come after this node (may be None) o prev: DLLNode: Reference to the node that come before this node (may be None) __init__(self, value: T, next: Node = None, prev: Node = None) -> None o Initialize doubly linked list node o val: T: Value held by this node. Note that this may be any type, such as a str, int, float, dict, or a more complex object. o nxt : DLLNode: Reference to the node that come after this node (may be None) o prev: DLLNode: Reference to the node that come before this node (may be None) o return: None _str__(self) -> str and __repr__(self) -> str o Represents the Doubly Linked List Node as string o This function might help you debug in Pycharm since it automatically calls this function to show the class for you o return: string representing the node Class LinkedList: DO NOT MODIFY the following attributes/functions This is doubly linked list class will help you create the pokemon PC Attributes o head: DLLNode: The head of doubly linked list o tail: DLLNode: The tail of doubly linked list ___init__(self, container: List[T] = None) -> None o Initialize doubly linked list o container: List[T]: Container that contain the elements that will store in linked list o To reduce bug and error of linked list head, this function constructs the None node to be the header node. The rest of linked list data will push after this node. Note that this node cannot be removed. o If container is not None, this class will automatically generate the linked list that contains every element in the container. o return: None _str__(self) -> str and __repr__(self) -> str o Represent Doubly Linked List Node as string o This function might help you debug in Pycharm since it automatically calls this function to show the class for you o return: string represented entire linked list Warning: Do not convert the LinkedList to a built-in Python list until the very end of your function when you return. Solutions which simply convert the LinkedList to a Python list and use built-in operations to solve the problem will lose ALL credit. pokemon_machine (pokemon: Linkedlist, orders: List[Tuple]) -> LinkedList: o pokemon: LinkedList: The first input is a linked list of strings representing pokemon's name that are initially stored in the PC o orders: List[Tuple): The second input is a python list of three possible commands used to modify the PC The first command is for adding pokemon. This command is a tuple of length 3, where Index O is a string, "add" Index 1 is an integer representing the position to put the new pokemon Index 2 is string represented the name of new pokemon Must call add_pokemon The second command is for removing pokemon. This command is a tuple of length 2, where Index 0 is a string, remove" Index 1 an integer representing the position to remove pokemon from PC Must call remove_pokemon The last possible command is for swapping pokemons. This command is a tuple of length 3, where Index 0 is a string, swap" Index 1 an integer representing the position of the first pokemon to swap Index 2 an integer representing the position of the second pokemon to swap Must call swap_pokemon o Return: A linked list of strings represents the current pokemons within the PC in the right order. o Time Complexity: Olop). Where o is the length of the orders list and p is the length of the pokemon list add_pokemon(cur_node: DLLnode, add_pokemon: str) -> None o This is the inner function inside pokemon_machine. o This function will add pokemon after the current node o cur_node: str: Current node to add the next pokemon after this node o add_pokemon: str: Name of pokemon to add o Return: None o Time Complexity: O(1) remove_pokemon(cur_node: DLLnode) -> None o This is the inner function inside pokemon_machine. o This function will remove pokemon at the current node o cur_node: Current node to add the next pokemon after this node o Return: None o Time Complexity: 0(1) swap_pokemon(first_node: DLLnode, second_node: DLLnode) -> None o This is the inner function inside pokemon_machine. o This function will swap pokemon between the first node and the second node o first_node: DLLnode: The first node to swap o second_node: DLLnode: The second node to swap o return: None o Time Complexity: O(1)