class _ListNode: def __init__(self, data): self.data = data self.next = None
Since any node can only be accessed by its predecessor, traversing the list to search for a node takes O(n) time. If we keep tracking the current tail of the node, adding a new node only requires us to append the new node to the tail of the list, thus takes O(1) time. Deleting a node, on the other hand, requires traversing the list to find the node to delete, thus takes O(n) time.
Here is the source code.
class _ListNode: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self._head = _ListNode(-1) #sentinel node self._curr = self._head self._size = 0 def __len__(self): return self._size def __add__(self, data): """ append a new node """ self._curr.next = _ListNode(data) self._curr = self._curr.next self._size += 1 def __contains__(self, item): """ check if a given item is in the list :param item: :return: """ curNode = self._head.next while curNode is not None and curNode.data != item: curNode = curNode.next return curNode is not None def __delattr__(self, item): """ delete a node if exists in the list :param item: :return: """ curNode = self._head.next while curNode is not None \ and curNode.next is not None \ and curNode.next.data != item: curNode = curNode.next if curNode.next is None: print('No such item in the linked list!') return False else: curNode.next = curNode.next.next self._size -= 1 return True def __iter__(self): curNode = self._head.next assert curNode is not None, 'Empty list!' while curNode is not None: data = curNode.data #print(curNode.data) curNode = curNode.next yield data
One more thing I learned today about Python is the iterator of an object. When we write a data structure using Python, we sometimes write __iter__() function. This function will return an iterator of the object. So next time when you write:
for item in object:
The compiler will call __iter__() and return the items in the object based on your __iter__() function.
Another useful places for this function is that you can initialize a list. For example, if I want to create a list based on the items in the above linked list, I can simply do:
tolist = list(linkedlist)
No comments:
Post a Comment