Friday, May 22, 2015

Singly linked list using Python, iterator in a Python object

The singly linked list is nothing fancy, basically it is a list of nodes appended one after another. Each node has a pointer points to its successor.

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