SHARE
TWEET

Untitled

a guest Mar 22nd, 2019 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Node:
  2.     """
  3.     Node for Linked List
  4.     """
  5.     def __init__(self, data: int):
  6.         self.data = data
  7.         self.next = None
  8.  
  9. def insert(node, data: int):
  10.     """
  11.     Insertion at the beginning to avoid
  12.     traversing the list
  13.     """
  14.     tmp = Node(data)
  15.     tmp.next = node
  16.     node = tmp
  17.     return node
  18.  
  19. def print_list(node):
  20.     """
  21.     Recursively traverse the list and
  22.     print data
  23.     """
  24.     if node is None:
  25.         return
  26.     print(node.data, end=' ')
  27.     print_list(node.next)
  28.  
  29. # Recursive find
  30. def find_recursive(node, data):
  31.     """
  32.     Recursively traverse the list and
  33.     return a node when its data mathes a provided data
  34.     """
  35.     if node is None:
  36.         return
  37.     if node.data == data:
  38.         return node
  39.     return find_recursive(node.next, data)
  40.  
  41. def find_predecessor(node, data):
  42.     """
  43.     Find a predecessor of a node of which data matches a provided data
  44.     """
  45.     if node is None or node.next is None:
  46.         return
  47.     if node.next.data == data:
  48.         return node
  49.     else:
  50.         return find_predecessor(node.next, data)
  51.    
  52.  
  53. def find(head, data):
  54.     """
  55.     Find a node iteratively for a provided data
  56.     """
  57.     tmp = head
  58.     while tmp:
  59.         if tmp.data == data:
  60.             break
  61.         tmp = tmp.next
  62.     return tmp
  63.  
  64. def delete(head, data):
  65.     """
  66.     Deleting a node requires a pointer to a predecessor
  67.     """
  68.     cur = find_recursive(head, data)
  69.     if cur:
  70.         pred = find_predecessor(head, data)
  71.         if pred is None:
  72.              head = cur.next
  73.         else:
  74.             pred.next = cur.next
  75.     return head
  76.  
  77.  
  78. def test_simple():
  79.     head = Node(1)
  80.     assert head.data == 1
  81.  
  82.     head = insert(head, 2)
  83.     assert head.data == 2
  84.     assert head.next.data == 1
  85.  
  86.     head = insert(head, 3)
  87.     print_list(head)
  88.  
  89.     assert find(head, 7) == None
  90.     assert find(head, 3) == head
  91.     assert find(head, 2) == head.next
  92.  
  93.     assert find_predecessor(head, 3) == None
  94.     assert find_predecessor(head, 2) == head
  95.     assert find_predecessor(head, 1) == head.next
  96.  
  97.     head = delete(head, 2)
  98.     assert head.data == 3
  99.     assert head.next.data == 1
  100.  
  101. if __name__ == '__main__':
  102.     test_simple()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top