Python 으로 일반적인 데이터 구조 구현 (1) - 질서 있 는 단 방향 링크

# coding:utf-8
# python            ，      
class Node(object):
    '''
            
    '''
    def __init__(self,data):
        '''
             
        
        :type data:   ，  （               ）
        '''
        self.data = data
        self.next = None
        
class OrderedLinkedList(object):
    '''
              
    '''
    def __init__(self,datas = []):
        '''
             
        :type datas:     ，    
        '''
        #      ，    None
        self.head = None
        for data in datas:
            self.insert(data)
        
    def insert(self,data):
        '''
               ，      ，        
        
        :type data:       ，  
        '''
        new_node = Node(data)
        
        #   head    ，    head       
        if not self.head:
            self.head = new_node
            return
        
        #   data  head    ，        head    
        if data < self.head.data:
            new_node.next = self.head
            self.head = new_node
            return
            
        #     
        pre = self.head
        cur = self.head.next
        while cur:
            #   data    cur.data，        
            if data >= cur.data:
                pre = cur
                cur = cur.next
            #       
            else:
                break
        #        pre cur  
        new_node.next = cur
        pre.next = new_node
        
    def delete(self,data):
        '''
                    ，     ，    ；           ，            
        
        :type data:          ，  
        '''
        if not self.head:
            raise ValueError('element NOT exist!')
            
        #   head    data，   head  
        if data == self.head.data:
            self.head = self.head.next
            return
        
        pre = self.head
        cur = self.head.next
        while cur:
            if data == cur.data:
                pre.next = cur.next
                return
            pre = cur
            cur = cur.next
        raise ValueError('element NOT exist!')
        
    def search(self,data):
        '''
                          （ 0  ）
                   ，                 ；      ，    
        
        :type data:          ，  
        '''
        cur = self.head
        if not cur:
            raise ValueError('element NOT exist!')
            
        idx = 0
        while cur:
            if data == cur.data:
                return idx
                break
            idx += 1
            cur = cur.next
        raise ValueError('element NOT exist!')
        
    def output(self):
        '''
                    ，  ：'1->3->4->5'
        '''
        cur = self.head
        datas = []
        while cur:
            datas.append(str(cur.data))
            cur = cur.next
        print '->'.join(datas)
        
if __name__ == '__main__':
    #      
    chain = OrderedLinkedList(range(5)[::-1])
    chain.output()
    
    #       
    chain.insert(2)
    chain.output()
    chain.insert(-1)
    chain.output()
    chain.insert(99)
    chain.output()
    
    #       
    print chain.search(99)
    print chain.search(2)
    # print chain.search(100)
    
    #       
    chain.delete(-1)
    chain.output()
    chain.delete(3)
    chain.output()
    chain.delete(99)
    chain.output()
    chain.delete(100)
    chain.output()
    
    #   ：
    '''
    0->1->2->3->4
    0->1->2->2->3->4
    -1->0->1->2->2->3->4
    -1->0->1->2->2->3->4->99
    7
    3
    0->1->2->2->3->4->99
    0->1->2->2->4->99
    0->1->2->2->4
    Traceback (most recent call last):
      File "E:\code\algorithm\data-structure\linkedlist.py", line 145, in 
        chain.delete(100)
      File "E:\code\algorithm\data-structure\linkedlist.py", line 87, in delete
        raise ValueError('element NOT exist!')
    ValueError: element NOT exist!
    '''