Python实现单向链表的增删改查反转等操作

单向链表结构

链表由一连串的节点组成，单向链表中节点包含一个用来存储下一个节点引用的成员，如图所示：

因为单向链表只有一个指针/引用成员，所以操作起来不是很方便，很多地方都需要从头节点开始遍历。

实现代码

完整代码如下：

class Node:
    ''' 节点的结构体 '''
    def __init__(self,value=None):
        self.value=value
        self.next=None

class SingleLinkedList:
    ''' 单链表类 '''
    def __init__(self):
        self.__head=None

    def isEmpty(self):
        ''' 判空 '''
        return self.__head==None

    def __len__(self):
        ''' Node个数 '''
        count=0
        cursor=self.__head
        while cursor!=None:
            count+=1
            cursor=cursor.next
        return count

    def __str__(self):
        ''' 输出元素列表 '''
        value_list=[]
        cursor=self.__head
        while cursor!=None:
            value_list.append(cursor.value)
            cursor=cursor.next
        return str(value_list)

    def pushBack(self,value):
        ''' 尾部添加一个节点 '''
        new_node=Node(value)
        if self.isEmpty():
            self.__head=new_node
        else:
            cursor=self.__head
            while cursor.next!=None:
                cursor=cursor.next
            cursor.next=new_node

    def popBack(self):
        ''' 尾部删除一个节点 ''' 
        pop_node=None
        #三种情况，无节点，单个节点，多个节点
        if self.__head==None:
            pass
        elif self.__head.next==None:
            pop_node=self.__head
            self.__head=None
        else:
            cursor=self.__head
            pop_node=self.__head.next
            while pop_node.next!=None:
                cursor=cursor.next
                pop_node=cursor.next
            cursor.next=None
        if pop_node!=None:
            return pop_node.value
        return None

    def pushFront(self,value):
        ''' 从头部插入节点 '''
        new_node=Node(value)
        new_node.next=self.__head
        self.__head=new_node

    def popFront(self):
        ''' 从头部删除节点 '''
        pop_node=self.__head
        if self.__head!=None:
            self.__head=self.__head.next
        if pop_node!=None:
            return pop_node.value
        return None

    def find(self,value):
        ''' 查找某个值第一次出现的pos '''
        find_pos=None
        count=0
        cursor=self.__head
        while cursor!=None:
            if cursor.value==value:
                find_pos=count
                break
            count+=1
            cursor=cursor.next
        return find_pos

    def insert(self,pos,value):
        ''' 任意位置插入 '''
        # 对于无效的位置，可以抛出异常，或者用布尔返回值
        length=len(self)
        if pos>=0 and pos<=length:
            # 0则头部插入，len则尾部插入
            if pos==0:
                self.pushFront(value)
            elif pos==length:
                self.pushBack(value)
            else:
                cursor=self.__head
                count=0
                while count