Sorted List

  1. # NodeModule.py
  2. #!/usr/bin/python
  3. """ A model containing Node class """
  4.  
  5. __author__ = "Lin Chen"
  6. __version__ = "0.1"
  7.  
  8. class Node:
  9. """Single node in a data structure"""
  10.  
  11. def __init__(self, data):
  12. """Initialize a Node
  13. Args:
  14. data : data saved in the node
  15. """
  16. self._data = data
  17. self._next = None
  18.  
  19. @property
  20. def data(self):
  21. return self._data
  22.  
  23. @data.setter
  24. def data(self, d):
  25. self._data = d
  26.  
  27. @data.deleter
  28. def data(self):
  29. del self._data
  30.  
  31. @property
  32. def next(self):
  33. return self._next
  34.  
  35. @next.setter
  36. def next(self, n):
  37. self._next = n
  38.  
  39. @next.deleter
  40. def next(self):
  41. del self._next
  42.  
  43. def __str__(self):
  44. return str(self._data)
  1. #!/usr/bin/python
  2. """ A modeule containing List class"""
  3.  
  4. from NodeModule import Node
  5.  
  6. class List:
  7. """Linked List class with a pre-defined Node class"""
  8.  
  9. def __init__(self):
  10. """Initialize a List
  11. """
  12. self._head = None
  13. self._count = 0
  14.  
  15. def getSize(self):
  16. """Return the size of the list
  17. Returns:
  18. int : size of the list
  19. """
  20. return self._count
  21.  
  22. def contains(self, v):
  23. """Check if a specific value is included in the list
  24.  
  25. Args:
  26. v : a data which can be saved in a node
  27.  
  28. Returns:
  29. boolean: True, if the value is contained in a node of the list; False, otherwise
  30. """
  31. current = self._head
  32.  
  33. while current is not None:
  34. if current.data == v:
  35. return True
  36. else:
  37. current = current.next
  38.  
  39. return False
  40.  
  41. def insert(self, v):
  42. """Insert a valude to make the list maintain ascending order
  43.  
  44. Args:
  45. v : data which can be saved in a node
  46.  
  47. Returns:
  48. boolean: True, if the value is inserted succefully; False, otherwise
  49. """
  50. n = Node(v) # create a node
  51.  
  52. if self.getSize() == 0:
  53. self._head = n
  54. self._count += 1
  55. return True
  56.  
  57. if n.data < self._head.data:
  58. n.next = self._head
  59. self._head = n
  60. self._count += 1
  61. return True
  62.  
  63. current = self._head
  64. while current is not None:
  65. if current.next is None or n.data <= current.next.data:
  66. n.next = current.next
  67. current.next = n
  68. self._count += 1
  69. return True
  70. current = current.next
  71.  
  72. return False
  73.  
  74. def delete(self, index):
  75. """Delete a valude located at a specific location in the list
  76.  
  77. Args:
  78. index (int): location of deletion, 0 is the location before the first element, 1 is the location after the first element
  79.  
  80. Returns:
  81. boolean: True, if the value is deleted succefully; False, otherwise
  82. """
  83. if index < 0 or index > self._count-1:
  84. return False
  85.  
  86. if index == 0:
  87. self._head = self._head.next
  88. self._count -= 1
  89. return True
  90.  
  91. current = self._head
  92. for i in range(index-1):
  93. current = current.next
  94.  
  95. current.next = current.next.next
  96. self._count -= 1
  97. return True
  98.  
  99. def __str__(self):
  100. """Convert the list to a string
  101.  
  102. Returns:
  103. string : a string represents the list
  104. """
  105. if self.getSize() == 0:
  106. return "Empty"
  107.  
  108. current = self._head
  109. output = []
  110.  
  111. while current is not None:
  112. output.append(str(current))
  113. current = current.next
  114.  
  115. return " -> ".join(output)
  1. # Test.py
  2. #!/usr/bin/python
  3.  
  4. from ListModule import List
  5.  
  6. def main():
  7. l = List()
  8.  
  9. l.insert(20)
  10. l.insert(10)
  11. l.insert(5)
  12. l.insert(40)
  13. l.insert(30)
  14. print(l) # 5 -> 10 -> 20 -> 30 -> 40
  15.  
  16. l.delete(2)
  17. print(l) # 5 -> 10 -> 30 -> 40
  18.  
  19. if l.contains(20):
  20. print("Contains 20 ...")
  21. else:
  22. print("Not contains 20 ...")
  23.  
  24. if __name__ == '__main__':
  25. main()