用Python实现常见数据结构（1）——有序单向链表

链表是一种常用的数据结构，而有序单向链表则是一种特殊的链表，可以在插入新的元素后仍保持元素有序，其思想类似于插入排序。下面用Python实现一个简单的有序单向列表数据结构：

# 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 <module>
        chain.delete(100)
      File "E:\code\algorithm\data-structure\linkedlist.py", line 87, in delete
        raise ValueError('element NOT exist!')
    ValueError: element NOT exist!
    '''

代码已经更新至：我的GitHub