- # NodeModule.py
- #!/usr/bin/python
- """ A model containing Node class """
-
- __author__ = "Lin Chen"
- __version__ = "0.1"
-
- class Node:
- """Single node in a data structure"""
-
- def __init__(self, data):
- """Initialize a Node
-
- Args:
- data : data saved in the node
- """
- self._data = data
- self._next = None
-
- @property
- def data(self):
- return self._data
-
- @data.setter
- def data(self, d):
- self._data = d
-
- @data.deleter
- def data(self):
- del self._data
-
- @property
- def next(self):
- return self._next
-
- @next.setter
- def next(self, n):
- self._next = n
-
- @next.deleter
- def next(self):
- del self._next
-
- def __str__(self):
- return str(self._data)
-
- #!/usr/bin/python
- """ A modeule containing List class"""
-
- from NodeModule import Node
-
- class List:
- """Linked List class with a pre-defined Node class"""
-
- def __init__(self):
- """Initialize a List
- """
- self._head = None
- self._count = 0
-
- def getSize(self):
- """Return the size of the list
-
- Returns:
- int : size of the list
- """
- return self._count
-
- def contains(self, v):
- """Check if a specific value is included in the list
-
- Args:
- v : a data which can be saved in a node
-
- Returns:
- boolean: True, if the value is contained in a node of the list; False, otherwise
- """
- current = self._head
-
- while current is not None:
- if current.data == v:
- return True
- else:
- current = current.next
-
- return False
-
- def insert(self, v):
- """Insert a valude to make the list maintain ascending order
-
- Args:
- v : data which can be saved in a node
-
- Returns:
- boolean: True, if the value is inserted succefully; False, otherwise
- """
- n = Node(v) # create a node
-
- if self.getSize() == 0:
- self._head = n
- self._count += 1
- return True
-
- if n.data < self._head.data:
- n.next = self._head
- self._head = n
- self._count += 1
- return True
-
- current = self._head
- while current is not None:
- if current.next is None or n.data <= current.next.data:
- n.next = current.next
- current.next = n
- self._count += 1
- return True
- current = current.next
-
- return False
-
- def delete(self, index):
- """Delete a valude located at a specific location in the list
-
- Args:
- index (int): location of deletion, 0 is the location before the first element, 1 is the location after the first element
-
- Returns:
- boolean: True, if the value is deleted succefully; False, otherwise
- """
- if index < 0 or index > self._count-1:
- return False
-
- if index == 0:
- self._head = self._head.next
- self._count -= 1
- return True
-
- current = self._head
- for i in range(index-1):
- current = current.next
-
- current.next = current.next.next
- self._count -= 1
- return True
-
- def __str__(self):
- """Convert the list to a string
-
- Returns:
- string : a string represents the list
- """
- if self.getSize() == 0:
- return "Empty"
-
- current = self._head
- output = []
-
- while current is not None:
- output.append(str(current))
- current = current.next
-
- return " -> ".join(output)
-
- # Test.py
- #!/usr/bin/python
-
- from ListModule import List
-
- def main():
- l = List()
-
- l.insert(20)
- l.insert(10)
- l.insert(5)
- l.insert(40)
- l.insert(30)
- print(l) # 5 -> 10 -> 20 -> 30 -> 40
-
- l.delete(2)
- print(l) # 5 -> 10 -> 30 -> 40
-
- if l.contains(20):
- print("Contains 20 ...")
- else:
- print("Not contains 20 ...")
-
- if __name__ == '__main__':
- main()
-