[数据结构与算法]Python 触“类”旁通3｜单链表基本操作之找查、删除和倒序

本篇准备学习单链表的找查、删除和倒序操作，所有操作会用到以下前文《触“类”旁通2｜数据结构入门之单链表的创建和遍历》中的代码，除__init__是必须的外，其它方法和属性基本只是为了方便赋值和检验结果正确与否而设，在解决问题时尽可能地不使用；更不能使用上篇中特别指出的“万能偷懒大法”来解决问题。节点类的基本属性和方法，如下：

class Node():
    def __init__(self, value=None, Next=None):
        self.val = value
        self.next = Next
        if type(self.next)==Node and self.next.val==None:
            self.next=None

    def __repr__(self):
        return f'Node({self.val}->{self.next})'
    
    def __str__(self):
        return f'{self.val}->{self.next}'

    def __len__(self):
        if self.val is None:
            return 0
        length,ptr = 0,self
        while ptr is not None:
            length += 1
            ptr = ptr.next
        return length 

    def __eq__(self, other):
        ptr1,ptr2 = self,other
        if len(ptr1)!=len(ptr2):
            return False
        while ptr1 is not None:
            if ptr1.val!=ptr2.val:
                return False
            ptr1 = ptr1.next
            ptr2 = ptr2.next
        else:
            return True

    def size():
        return self.__len__()

    @property
    def length(self):
        return self.size()

    @property
    def value(self):
        return self.val

    @property
    def values(self):
        ret,ptr = [],self
        while ptr is not None:
            ret.append(ptr.val)
            ptr = ptr.next
        return ret

    def pprint(self):
        print('->'.join([str(i) for i in self.values]))

    def isNode(node):
        return isinstance(node,Node) and isinstance(node.next,(Node,type(None)))

    def build(*data, split=True):
        '''把数据转换成节点链表'''
        lst,ret = [],Node()
        for val in data:
            if type(val) is str:
                if not split:
                    lst.append(val)
                    continue
                if str=='':
                    continue
                try:
                    num = int(val)
                    lst.extend([int(_) for _ in val])
                except:
                    lst.extend([_ for _ in val])
            elif hasattr(val,'__iter__'):
                lst.extend([_ for _ in val])
            elif type(val) is Node:
                if not val.isNone:
                    lst.extend(val.values)
            else:
                lst.append(val)
        ret = Node()
        for i in lst[::-1]:
            ret = Node(i, ret)
        return ret

    def copy(node):
        ret = Node()
        ptr1,ptr2 = node,ret
        while ptr1 is not None:
            ptr2.next = Node(ptr1.val)
            ptr1,ptr2 = ptr1.next,ptr2.next
        return ret.next

查找操作

1. 查找首个元素

返回等于目标值num的第一个元素的索引号，头节点为0；找不到则返回 -1。

    def find(self, num):
        ptr,ret = self,-1
        while ptr is not None:
            ret += 1
            if ptr.val == num: break
            ptr = ptr.next
        else:
            ret = -1
        return ret

2. 查找所有元素

返回等于目标值num的所有元素的索引号列表；找不到则返回 [-1]。

    def findall(self, num):
        ptr,idx,ret = self,-1,[]
        while ptr is not None:
            idx += 1
            if ptr.val == num:
                ret.append(idx)
            ptr = ptr.next
        if ret == []: ret = [-1]
        return ret

删除操作

1. 清空

>>> def clear(self):
	self.val = self.next = None
	return self

>>> n = Node.build(1,2,3)
>>> n
Node(1->2->3->None)
>>> clear(n)
Node(None->None)
>>> n
Node(None->None)
>>> 

2. 销毁

设置一个类的内置__del__() 方法：当节点不再被需要调用时，引用计数为0时就会被回收，并且调用__del__()方法显示其回收过程。

【知识点】Python 采用自动引用计数（简称 ARC）的方式实现垃圾回收机制。该方法的核心思想是：每个 Python 对象都会配置一个计数器，初始 Python 实例对象的计数器值都为 0，如果有变量引用该实例对象，其计数器的值会加 1，依次类推；反之，每当一个变量取消对该实例对象的引用，计数器会减 1。如果一个 Python 对象的的计数器值为 0，则表明没有变量引用该 Python 对象，即证明程序不再需要它，此时 Python 就会自动调用 __del__() 方法将其回收。?

del obj 并不主动调用__del__方法，只有引用计数为0时，__del__()才会被执行，并且定义了__del_()的实例无法被Python的循环垃圾收集器收集，所以尽量不要自定义__del__()。一般情况下，__del__() 不会破坏垃圾处理器。

节点类中添加以下代码用以测试：?

    def __del__(self):
        print(id(self),self)

    def init1():
        a=Node(1)
        b=Node(2)
        return a

    def init2():
        a=Node(1)
        b=Node(2)
        a.next = b
        return a

测试结果大致反馈了被回收对象的id和内容：

>>> a = Node.init1()
55624680 2->None????????# init1()中的a没被调用，引用计数为0，即被回收
>>> a = Node.init2()
50818736 1->None????????# init1()中的b也不需要了，才被回收
>>> a = Node()
55624680 1->2->None????????# 这是init2()中的a，此时才被回收
55624752 2->None????????# 这是init2()中的b被回收
>>> a = Node.build(3,4,5)
55624680 None->None????????# 前2个是build方法中用过的两个临时空节点 ret
55624872 None->None
50818736 None->None????????# 这个是上一步 a=Node() 设置的空节点
>>> del a
55624704 3->4->5->None????????# del操作即可销毁，引用计数为0从头节点开始回收
55624872 4->5->None
55624920 5->None
>>>?

3. 删除头节点

4. 删除中间节点

5. 删除尾节点

6. 删除首个指定值的节点

7. 删除指定值的所有节点

8. 删除尾节点

编辑中。。。

    def pop(self):
        if self.next is None:
            ret = self.val
            self.val = self.next = None
            return ret
        temp = Node()
        ptr1,ptr2 = self,temp
        while ptr1.next is not None:
            ptr2.next = Node(ptr1.val)
            ptr1,ptr2 = ptr1.next,ptr2.next
            ret = ptr1.val
        self.val,self.next = temp.next.val,temp.next.next
        return ret

    def __del__(self):
        #print(self)
        pass

    def reverseList(self):
        ptr = ret = Node()
        num = self.pop()
        while num is not None:
            ptr.next = Node(tmp)
            ptr = ptr.next
            num = self.pop()
        return ret.next

    def reverse(self):
        tmp = Node()
        ptr = self
        while ptr is not None:
            tmp = Node(ptr.val,tmp)
            ptr = ptr.next
        self.val,self.next = tmp.val,tmp.next
        return self

    def __reversed__(self):
        ret,ptr = Node(),self
        while ptr is not None:
            ret = Node(ptr.val, ret)
            ptr = ptr.next
        return ret