Implementing a linked positional list
import core
class Node(core.Position): """ Node ---- Contains the elements that are placed into the Positional Linked List.
This is a small helper class. You do *NOT* need to modify this class. """
def __init__(self, element): self.element = element self.prev = None self.next = None
def get_element(self): return self.element
class LinkedPositionalList(core.PositionalList): """ Linked Positional List ----------------------
Keeps information in a linked list, each element is a position. It allows for insertion and removal anywhere in the list. It supports an 'undo' for the "insert" and "remove" that can be called multiple times.
Implement the PositionalList interface using the Node class """
def __init__(self): # The header sentinel self._header = Node(None) # The trailer sentinel self._trailer = Node(None)
# Setting the correct previousext self._header.next = self._trailer self._trailer.prev = self._header self._size = 0
def print_list(self): """ Prints the current state of the list; Starting at the header and moving forwards. """ current = self._header.next list_str = "" while True: if current == self._trailer: break list_str += "{} ".format(current.get_element()) current = current.next
return list_str
def size(self): return self._size
def is_empty(self): return self._size == 0
def _get_position(self, position): if position == self._header or position == self._trailer: return None return position
def first(self): return self._get_position(self._header.next)
def last(self): return self._get_position(self._trailer.prev)
def before(self, position): return self._get_position(position.prev)
def after(self, position): return self._get_position(position.next) def _add_between(self, prev, next, element): self._size += 1 n = Node(element) n.next = next n.prev = prev prev.next = n next.prev = n return n
def insert_first(self, element): return self._add_between(self._header, self._header.next, element)
def insert_last(self, element): return self._add_between(self._trailer.prev, self._trailer, element)
def insert_before(self, position, element): return self._add_between(position.prev, position, element)
def remove(self, position): # TODO: Implement this (remember to return the ELEMENT at `position`). # Remove the element at the position specified remembering to update # the other node information! self._size -= 1 position.prev.next = position.next position.next.prev = position.prev return position.element
def undo(self): # TODO: Implement this: # Undo the latest action. return None
def main(): # This function is here for you to optionally use for your own # testing / running. This function will NOT be tested. pass
if __name__ == "__main__": main()
The code looks like this, and i've implemented other functions except undo() i have no idea
undo() requires undo the latest action
like this 
1 import core 2 4 class Node (core.Position): 8 9 10 Node Contains the elements that are placed into the Positional Linked List. This is a small helper class You do *NOT* need to modify this class. 12 13 14 15 16 17 18 19 20 21 def init(self, element): self.e Lement-e Lement self.prev None self.next None - def get_element (self): return self.element 23 class LinkedPositionalList(core.PositionalList): 24 25 26 27 28 29 30 31 32 Linked Positional List Keeps information in a linked list, each element is a position. It allows for insertion and removal anywhere in the list. It supports an undo for the "insert" and "remove" that can be called multiple times Implement the PositionaLList interface using the Node class 34 35 36 37 38 39 40 41 42 43 def init(self): # The header sentinel self. header Node (None) # The trailer sentinel self. trailer Node (None) # Setting the correct previousext self. header.next self. trailer self._trailer.prev self._header self. size -0 45 46 def print_list(self): 48 49 50 51 52 53 54 Prints the current state of the list; Starting at the header and moving forwards. current self. header.next list str = "" while True: if current self._trailer: break list_str +" ".format (current.get_element()) current current.next 56 57 58 59 60 61 62 63 64 65 return list str def size(self): return self. size def is_empty(self): return self. size 0 def _get_ position(self, position): 67 68 69 70 if positionself._header or positionself._trailer: return None return position def first(self): 72 73 return self._get_position(self._header.next) return self._get_position(self._trailer.prev) return self._get_position(position.prev) return self._get_position(position.next) def last (self): 75 def before(self, position): 78 79 80 def after(self, position): 82 def _add_between (self, prev, next, element): 83 84 85 86 87 self. size +: 1 n Node(element) n.next next n.prev prev prev.next - n next.prevn return n 89 90 91 92 93 def insert_first(self, element): return self._add_between (self._header, self._header.next, element) 95 96 97 98 def insert_last(self, element): def insert_before(self, position, element): def remove(self, position): return self._add_between(self._trailer.prev, self._trailer, element) return self._add_between(position.prev, position, element) 100 101 102 103 104 105 106 107 108 109 110 # TODO: Implement this (remember to return the ELEMENT at 'position.) # Remove the element at the position specified remembering to update # the other node information! self. size - 1 position.prev.next position.next position.next.prev -position.prev return position.element def undo (self): 112 113 114 115 116 # TODO: Implement this: # Undo the latest action return None 117 def main(): 118 119 120 121 122 # This function is here for you to optionally use for your own # testing / running. This function will NOT be tested. pass 123 if_name --" main..: -- 124 main() 1 import core 2 4 class Node (core.Position): 8 9 10 Node Contains the elements that are placed into the Positional Linked List. This is a small helper class You do *NOT* need to modify this class. 12 13 14 15 16 17 18 19 20 21 def init(self, element): self.e Lement-e Lement self.prev None self.next None - def get_element (self): return self.element 23 class LinkedPositionalList(core.PositionalList): 24 25 26 27 28 29 30 31 32 Linked Positional List Keeps information in a linked list, each element is a position. It allows for insertion and removal anywhere in the list. It supports an undo for the "insert" and "remove" that can be called multiple times Implement the PositionaLList interface using the Node class 34 35 36 37 38 39 40 41 42 43 def init(self): # The header sentinel self. header Node (None) # The trailer sentinel self. trailer Node (None) # Setting the correct previousext self. header.next self. trailer self._trailer.prev self._header self. size -0 45 46 def print_list(self): 48 49 50 51 52 53 54 Prints the current state of the list; Starting at the header and moving forwards. current self. header.next list str = "" while True: if current self._trailer: break list_str +" ".format (current.get_element()) current current.next 56 57 58 59 60 61 62 63 64 65 return list str def size(self): return self. size def is_empty(self): return self. size 0 def _get_ position(self, position): 67 68 69 70 if positionself._header or positionself._trailer: return None return position def first(self): 72 73 return self._get_position(self._header.next) return self._get_position(self._trailer.prev) return self._get_position(position.prev) return self._get_position(position.next) def last (self): 75 def before(self, position): 78 79 80 def after(self, position): 82 def _add_between (self, prev, next, element): 83 84 85 86 87 self. size +: 1 n Node(element) n.next next n.prev prev prev.next - n next.prevn return n 89 90 91 92 93 def insert_first(self, element): return self._add_between (self._header, self._header.next, element) 95 96 97 98 def insert_last(self, element): def insert_before(self, position, element): def remove(self, position): return self._add_between(self._trailer.prev, self._trailer, element) return self._add_between(position.prev, position, element) 100 101 102 103 104 105 106 107 108 109 110 # TODO: Implement this (remember to return the ELEMENT at 'position.) # Remove the element at the position specified remembering to update # the other node information! self. size - 1 position.prev.next position.next position.next.prev -position.prev return position.element def undo (self): 112 113 114 115 116 # TODO: Implement this: # Undo the latest action return None 117 def main(): 118 119 120 121 122 # This function is here for you to optionally use for your own # testing / running. This function will NOT be tested. pass 123 if_name --" main..: -- 124 main()
