Advertisement
bwukki

Doubly Linked in py

Oct 16th, 2018
219
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 4.82 KB | None | 0 0
  1. #node class goes in Node.py
  2.  
  3. class Node:
  4.  
  5.     def __init__(self, a_data):
  6.         self.prev = None
  7.         self.next = None
  8.         self.data = a_data
  9.  
  10.     def __str__(self):
  11.         return str(self.data)
  12.  
  13. #unit tests go in their own file of any name
  14.  
  15. import unittest
  16. import Node
  17. import Doubly_Linked
  18.  
  19. class DoublyTest(unittest.TestCase):
  20.  
  21.     def test_Node(self):
  22.         test_case1 = Node.Node(5)
  23.         self.assertEqual(test_case1.next, None)
  24.         self.assertEqual(test_case1.prev, None)
  25.         self.assertEqual(test_case1.data, 5)
  26.  
  27.     def test_DoublyPushPrint(self):
  28.         test_case1 = Doubly_Linked.Doubly_Linked()
  29.         test_case1.push(5)
  30.         test_case1.push(4)
  31.         self.assertEqual(str(test_case1),"5 4")
  32.  
  33.     def test_Doublepop(self):
  34.         test_case3 = Doubly_Linked.Doubly_Linked()
  35.         test_case3.push(5)
  36.         test_case3.push(4)
  37.         self.assertEqual(test_case3.pop(), 4)
  38.         self.assertEqual(test_case3.pop(), 5)
  39.  
  40.     def test_DoublyEmpty(self):
  41.         test_case2 = Doubly_Linked.Doubly_Linked()
  42.         self.assertRaises(Exception, test_case2.pop)
  43.  
  44.     def test_DoubleyTraverse(self):
  45.         test_case4 = Doubly_Linked.Doubly_Linked()
  46.         self.assertRaises(Exception, test_case4.get, 4)
  47.         test_case4.push(1)
  48.         self.assertRaises(Exception, test_case4.get, 2)
  49.         test_case4.push(2)
  50.         test_case4.push(3)
  51.         test_case4.push(4)
  52.         self.assertEqual(test_case4.get(4),4)
  53.         self.assertRaises(Exception, test_case4.get, 0)
  54.         self.assertRaises(Exception, test_case4.get, -1)
  55.  
  56.     def test_DoubleyDelete(self):
  57.         test_case5 = Doubly_Linked.Doubly_Linked()
  58.         self.assertRaises(Exception, test_case5.remove,-1)
  59.         self.assertRaises(Exception, test_case5.remove, 1)
  60.         test_case5.push(1)
  61.         test_case5.push(2)
  62.         test_case5.push(3)
  63.         test_case5.remove(3)
  64.         self.assertEqual(test_case5.size,2)
  65.         self.assertEqual(test_case5.pop(),2)
  66.  
  67.  
  68. if __name__ == '__main__':
  69.     unittest.main()
  70.  
  71. #Doubly linked class goes in Doubly_linked.py
  72.  
  73. import Node
  74.  
  75. class Doubly_Linked:
  76.     def __init__(self):
  77.         self.head = None
  78.         self.tail = None
  79.         self.size = 0
  80.  
  81.     def get(self,location):
  82.         if location <= 0:
  83.             raise Exception("Out of bounds")
  84.         if self.size == 0:
  85.             raise Exception("List is empty")
  86.         elif location > self.size:
  87.             raise Exception("Out of bounds")
  88.  
  89.         if self.size == 1:
  90.             result = self.head.data
  91.  
  92.         else:
  93.             current_node = self.head
  94.             for i in range(location-1):
  95.                 current_node = current_node.next
  96.             result = current_node.data
  97.         return result
  98.  
  99.     def remove(self,location):
  100.         if location < 0:
  101.             raise Exception("Out of bounds")
  102.         if location > self.size:
  103.             raise Exception("Out of bounds")
  104.         if self.size == 0:
  105.             raise Exception("Empty list")
  106.         if self.size == 1:
  107.             self.size = 0
  108.             self.head = None
  109.         else:
  110.             current_node = self.head
  111.             for i in range(location-1):
  112.                 current_node = current_node.next
  113.             current_node.next.prev = current_node.prev
  114.             current_node.prev.next = current_node.next
  115.             if current_node == self.tail:
  116.                 self.tail = self.head.prev
  117.             if current_node == self.head:
  118.                 self.head = current_node.next
  119.             current_node = None
  120.             self.size -= 1
  121.  
  122.  
  123.     def pop(self):
  124.         if self.size == 0:
  125.             raise Exception("List is empty")
  126.         self.tail.prev.next = self.head
  127.         self.head.next = self.tail.prev
  128.         result = self.tail.data
  129.         self.tail = self.tail.prev
  130.         self.size -= 1
  131.         return result
  132.  
  133.     def push(self, a_data):
  134.         if self.size == 0: #case for an empty list getting its first data members
  135.             self.head = Node.Node(a_data)
  136.  
  137.         elif self.tail == None: #case for a list with a head but no tail
  138.             self.tail = Node.Node(a_data)
  139.             self.tail.next = self.head
  140.             self.tail.prev = self.head
  141.             self.head.next = self.tail
  142.             self.head.prev = self.tail
  143.  
  144.         else:
  145.             new_node = Node.Node(a_data) #all other cases
  146.             new_node.prev = self.tail
  147.             new_node.next = self.head
  148.             self.head.prev = new_node
  149.             self.tail.next = new_node
  150.             self.tail = new_node
  151.  
  152.         self.size += 1
  153.  
  154.     def __str__(self):
  155.         result = ""
  156.         current_node = self.head
  157.         while current_node != self.tail:
  158.             result += str(current_node) + " "
  159.             current_node = current_node.next
  160.         result += str(self.tail)
  161.         return result
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement