SHARE
TWEET

Doubly linked list (Cu3se1.2En_sor)

general_ghest Nov 18th, 2019 (edited) 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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
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