Advertisement
general_ghest

Doubly linked list (Cu3se1.2En_sor)

Nov 18th, 2019
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.80 KB | None | 0 0
  1. # We define: the basic class for a node where it is stored
  2. #            the data of the same node
  3. #            the index of the next node
  4. #            the index of the previous node
  5. class Node:
  6.     def __init__(self, data):
  7.         self.data = data
  8.         self.next = None
  9.         self.prev = None
  10.  
  11. # The doubly linked list class is created
  12. class DoublyLinkedList:
  13.     # Builder
  14.     def __init__(self):
  15.         self.first = None
  16.         self.last = None
  17.  
  18.     # Enter the index of the node you want to obtain
  19.     def get_node(self, index):
  20.         # the current node is the first in the list
  21.         current = self.first
  22.         # the list is scrolled to the indicated index
  23.         for i in range(index):
  24.         # if the current node is none it is because the list is empty
  25.             if current is None:
  26.             # none is returned as there are no nodes
  27.                 return None
  28.             # if the current node is none, the following is obtained
  29.             # to continue browsing the list until you reach the requested index
  30.             current = current.next
  31.             return current
  32.  
  33.     # enter the node after a reference node
  34.     # the reference node index is entered
  35.     def insert_after(self, ref_node, new_node):
  36.         new_node.prev = ref_node
  37.         if ref_node.next is None:
  38.             self.last = new_node
  39.         else:
  40.             new_node.next = ref_node.next
  41.             new_node.next.prev = new_node
  42.         ref_node.next = new_node
  43.  
  44.     def insert_before(self, ref_node, new_node):
  45.         new_node.next = ref_node
  46.         if ref_node.prev is None:
  47.             self.first = new_node
  48.         else:
  49.             new_node.prev = ref_node.prev
  50.             new_node.prev.next = new_node
  51.         ref_node.prev = new_node
  52.  
  53.     def insert_at_beg(self, new_node):
  54.         if self.first is None:
  55.             self.first = new_node
  56.             self.last = new_node
  57.         else:
  58.             self.insert_before(self.first, new_node)
  59.  
  60.     def insert_at_end(self, new_node):
  61.         if self.last is None:
  62.             self.last = new_node
  63.             self.first = new_node
  64.         else:
  65.             self.insert_after(self.last, new_node)
  66.  
  67.     def remove(self, node):
  68.         if node.prev is None:
  69.             self.first = node.next
  70.         else:
  71.             node.prev.next = node.next
  72.  
  73.         if node.next is None:
  74.             self.last = node.prev
  75.         else:
  76.             node.next.prev = node.prev
  77.  
  78.     def items(self):
  79.         x = self.first
  80.         while x:
  81.             yield x
  82.             x = x.next
  83.  
  84.     def values(self):
  85.         x = self.first
  86.         while x:
  87.             yield x.data
  88.             x = x.next
  89.    
  90.     def display(self):
  91.         return ', '.join([str(x) for x in self.values()])
  92.  
  93.  
  94.     def sort(self, ref_node, new_node):
  95.         new_node.prev = ref_node
  96.         if ref_node.next is None:
  97.             print ('Начало if')
  98.             j = self.last
  99.             self.last = new_node.prev
  100.             new_node.prev = j #self.last(old)
  101.             self.display(self)
  102.         else:
  103.             new_node.next = ref_node.next
  104.             new_node.next.prev = new_node
  105.         ref_node.next = new_node
  106.  
  107. a_dllist = DoublyLinkedList()
  108.  
  109. print('Menu')
  110. print('insert <data> after <index>')
  111. print('insert <data> before <index>')
  112. print('insert <data> at beg')
  113. print('insert <data> at end')
  114. print('remove <index>')
  115. print('find <data>')
  116. print('sort')
  117. print('quit')
  118.  
  119. while True:
  120.     print('The list: ', end='')
  121.     a_dllist.display()
  122.     print()
  123.     do = input('What would you like to do? ').split()
  124.  
  125.     operation = do[0].strip().lower()
  126.  
  127.     if operation == 'insert':
  128.         data = int(do[1])
  129.         position = do[3].strip().lower()
  130.         new_node = Node(data)
  131.         suboperation = do[2].strip().lower()
  132.         if suboperation == 'at':
  133.             if position == 'beg':
  134.                 a_dllist.insert_at_beg(new_node)
  135.             elif position == 'end':
  136.                 a_dllist.insert_at_end(new_node)
  137.         else:
  138.             index = int(position)
  139.             ref_node = a_dllist.get_node(index)
  140.             if ref_node is None:
  141.                 print('No such index.')
  142.                 continue
  143.             if suboperation == 'after':
  144.                 a_dllist.insert_after(ref_node, new_node)
  145.             elif suboperation == 'before':
  146.                 a_dllist.insert_before(ref_node, new_node)
  147.             elif operation =='sort':
  148.                 a_dllist.sort(ref_node, new_node)
  149.  
  150.     elif operation == 'remove':
  151.         index = int(do[1])
  152.         node = a_dllist.get_node(index)
  153.         if node is None:
  154.             print('No such index.')
  155.             continue
  156.         a_dllist.remove(node)
  157.    
  158.     elif operation =='find':
  159.         a_dllist.find()
  160.  
  161.     elif operation == 'quit':
  162.         break
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement