Sunday, March 8, 2015

week8 : Linked List

Linked List is a type of degenerated tree if you consider it a tree whose nodes has one child except for its leaf. And we can add a lot of useful methods on linked list, such as append, prepend, even built-in methods like __getitem__, __setitem__. Among those operations, most of them we just need a current_node to keep track of nodes in the linked list and traverse it node by node until its next is None.
Such as for __getitem__,

def __getitem__(self, index):
        ''' (LinkedList, int|slice) -> object

        Return the value at position index.
        # don't fuss about slices yet. 
if index > self.size - 1:
            raise Exception('out of range')
        else:
            current_node = self.front
            for i in range(0, index):
                current_node = current_node.nxt
            return current_node.value

But there are also some operations quiet complicate which require more than one flag pointers to keep track of the process, such as 
def insert_before(lnk, v1, v2):
    ''' (LinkedList, object) -> NoneType

    Insert a new node with value v1 before the first occurrence
    of a node with value v2.  Do nothing if no node has value
    v2.'''
    if v2 == lnk.front.value:
        new_node = LLNode(v1)
        new_node.nxt = lnk.front
        lnk.front = new_node
        lnk.size += 1
    else:
        pre = lnk.front
        cur = lnk.front.nxt
        while cur and cur.value != v2:
                pre = cur
                cur = cur.nxt
        if cur:
            new_node = LLNode(v1)
            new_node.nxt = cur
            pre.nxt = new_node
            lnk.size += 1
The additional node 'pre' is added because in one directional oriented linked list, there is no way for us to know the pre-node of current node. In that case, we need a node to keep track of the pre-node of current node, when current node meets the requirement, we can operate on the pre-node which is pointed by pre.











No comments:

Post a Comment