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

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

# coding:utf-8 # python实现有序单向链表数据结构，以及基本操作 class Node(object): ''' 链表节点数据结构 ''' def __init__(self,data): ''' 初始化节点:type data: 数据，整型（可以按照实际需求定义为其他类型） ''' self.data = https://www.it610.com/article/data self.next = Noneclass 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_nodedef 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 returnpre = 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! '''

代码已经更新至：我的GitHub