python3实现链表

python3实现链表

尝试用Python实现链表，实现了添加元素append(), 删除元素pop()，获取元素getItem()，设置元素setItem()，打印链表printChain()，输出链表长度getLen()功能，并尝试逐步进行优化，特此记录。

1. 基础版本。

此版本的主要问题有：（1）没有对index进行验证；（2）定位前一个元素的代码冗余。

class ChainCell():
    '''本类是链表的基础元素类'''
    def __init__(self,value=None,nextCell=None):
        self.value=value;
        self.next=nextCell;
        
class Chain():
    '''本类实现链表'''
    def __init__(self,values=None):   
        '''初始化函数，如果有初始元素，要求以链表或者元组的形式传递'''
        self.head=None
        if values:
            self.length=0
            for value in values:
                newCell=ChainCell(value)
                if not self.head:
                    self.head=newCell
                else:
                    self.last.next=newCell
                self.last=newCell
                self.length+=1
                
      def append(self,value,index=-1):   
        '''向链表中的index位置添加元素'''
        newCell=ChainCell(value)
        if index==-1 or index==self.length:
            self.last.next,self.last=newCell,newCell
        elif index==0 or index==-self.length-1:
            newCell.next=self.head
            self.head=newCell
        else:
            lastCell=self.head
            n=index-1 if index>0 else self.length-abs(index)
            for i in range(n):
                lastCell=lastCell.next
            newCell.next=lastCell.next
            lastCell.next=newCell
        self.length+=1
        return value
    
    def pop(self,index=-1):
        '''d出链表中的元素'''
        # 没有办法直接删除最后一个元素，因为要修改上一个元素的next指针
        if index==0:
            self.head=self.head.next
        else:
            n=index-1 if index>0 else self.length-abs(index)-1
            lastCell=self.head
            for i in range(n):
                lastCell=lastCell.next
            lastCell.next=lastCell.next.next   
        self.length-=1
    
    def getCell(self,index):
        '''对应“查”功能，是链表最基础的功能，时间复杂度为O(n)
        根据下标，获得某个链表元素的值,支持正负两种下标表示形式'''
        if index==0:
            return self.head.value
        else:
            lastCell=self.head
            n=index if index>0 else self.length-abs(index)+1
            for i in range(n):
                lastCell=lastCell.next
            return lastCell.value
    
    def setCell(self ,index,value):
        '''根据下标，设置某个链表元素的值'''
        lastCell=self.head
        n=index-1 if index>0 else self.length-abs(index)-1
        for i in range(n):
            lastCell=lastCell.next
        lastCell.next.value=value
        return value
    
    def printChain(self):
        '''输出所有的链表元素'''
        # for i in range(self.length): 两种遍历方式
        if not self.head:   #或者if self.length==0
            print('当前链表中没有元素！')
            return
        else:
            lastCell=self.head
            values=[lastCell.value]
            while lastCell.next:
                lastCell=lastCell.next
                values.append(lastCell.value)
            print(values)
    
    def getLen(self):
        '''输出链表的长度'''
        # return self.length  最简单，适合维护了这个变量的情况
        if not self.head:
            return 
        else:
            count=1
            lastCell=self.head
            while lastCell.next:
                lastCell=lastCell.next
                count+=1
            return count

2. 修改版本1

定义函数checkLegal判断index 是否合法

'''链表，注意正负坐标的转化，abs(posiIndex)+abs(negaIndex)=self.length
    另外需要注意到底是定位到index前一个元素，还是index元素本身'''
class ChainCell():
    '''本类是链表的基础元素类'''
    def __init__(self,value=None,nextCell=None):
        self.value=value;
        self.next=nextCell;
        
class Chain():
    '''本类实现链表'''
    def __init__(self,values=None):   
        '''初始化函数，如果有初始元素，要求以链表或者元组的形式传递'''
        self.head=None
        if values:
            self.length=0
            for value in values:
                newCell=ChainCell(value)
                if not self.head:
                    self.head=newCell
                else:
                    self.last.next=newCell
                self.last=newCell
                self.length+=1
                
    def checkLegal(self,index,funcName=None):   
        '''该函数为类的内部函数，用来判断用户输入的下标是否合理，如果不合理，则会报错，如果合理，则将index原路返回。
        funcName为函数的名称，因为append函数比get等函数的边界大一'''
        maxLength=self.length if funcName=='append' else self.length-1
        if index>maxLength or (index<0 and abs(index)>maxLength+1):
            raise IndexError("下标超出支持的范围")
        elif not isinstance(index,int):
            raise IndexError("下标必须是整数")
        else:
            return index
    
    def append(self,value,index=-1):   
        '''向链表中的index位置添加元素'''
        self.checkLegal(index,'append')  #也可以使用sys模块下的sys._getframe().f_code.co_name
        newCell=ChainCell(value)
        if index==-1 or index==self.length:   #在最后插入元素
            self.last.next,self.last=newCell,newCell
        elif index==0 or index==-self.length-1:  #在第一个位置插入元素
            newCell.next=self.head
            self.head=newCell
        else:
            lastCell=self.head
            n=index-1 if index>0 else self.length-abs(index)
            for i in range(n):
                lastCell=lastCell.next
            newCell.next=lastCell.next
            lastCell.next=newCell
        self.length+=1
        return value
    
    def pop(self,index=-1):
        '''d出链表中的元素'''
        self.checkLegal(index)
        # 没有办法直接删除最后一个元素，因为要修改上一个元素的next指针
        if index==0:
            self.head=self.head.next
        else:
            n=index-1 if index>0 else self.length-abs(index)-1
            lastCell=self.head
            for i in range(n):
                lastCell=lastCell.next
            lastCell.next=lastCell.next.next   
        self.length-=1
    
    def getCell(self,index):
        '''对应“查”功能，是链表最基础的功能，时间复杂度为O(n)
        根据下标，获得某个链表元素的值,支持正负两种下标表示形式'''
        self.checkLegal(index)
        if index==0:
            return self.head.value
        else:
            lastCell=self.head
            n=index if index>0 else self.length-abs(index)+1
            for i in range(n):
                lastCell=lastCell.next
            return lastCell.value
    
    def setCell(self ,index,value):
        '''根据下标，设置某个链表元素的值'''
        self.checkLegal(index)
        lastCell=self.head
        n=index-1 if index>0 else self.length-abs(index)-1
        for i in range(n):
            lastCell=lastCell.next
        lastCell.next.value=value
        return value
    
    def printChain(self):
        '''输出所有的链表元素'''
        # for i in range(self.length): 两种遍历方式
        if not self.head:   #或者if self.length==0
            print('当前链表中没有元素！')
            return
        else:
            lastCell=self.head
            values=[lastCell.value]
            while lastCell.next:
                lastCell=lastCell.next
                values.append(lastCell.value)
            print(values)
    
    def getLen(self):
        '''输出链表的长度'''
        # return self.length  最简单，适合维护了这个变量的情况
        if not self.head:
            return 
        else:
            count=1
            lastCell=self.head
            while lastCell.next:
                lastCell=lastCell.next
                count+=1
            return count

3. 修改版本2

将checkLegal变成装饰器

'''链表，注意正负坐标的转化，abs(posiIndex)+abs(negaIndex)=self.length
    另外需要注意到底是定位到index前一个元素，还是index元素本身'''
class ChainCell():
    '''本类是链表的基础元素类'''
    def __init__(self,value=None,nextCell=None):
        self.value=value;
        self.next=nextCell;
        
class Chain():
    '''本类实现链表'''
    def __init__(self,values=None):   
        '''初始化函数，如果有初始元素，要求以链表或者元组的形式传递'''
        self.head=None
        if values:
            self.length=0
            for value in values:
                newCell=ChainCell(value)
                if not self.head:
                    self.head=newCell
                else:
                    self.last.next=newCell
                self.last=newCell
                self.length+=1
                
    def isLegal(self,maxLength,*args,**kargs):   
        '''该函数为类的内部函数，用来判断用户输入的下标是否合理，如果不合理，则会报错，如果合理，则将index原路返回。
        funcName为函数的名称，因为append函数比get等函数的边界大一'''
        
        if not args:   #判断index参数是以何种形式给出的，args和kargs里存储的都是实参，默认值不会出现在里面
            if 'index' in kargs:
                index=kargs['index']
            else:
                index=-1
        else:
            index=args[0]
        if index>maxLength or (index<0 and abs(index)>maxLength+1):
            raise IndexError("下标超出支持的范围")
        elif not isinstance(index,int):
            raise IndexError("下标必须是整数")
        else:
            return index
        
    def checkLegal(func):
        '''装饰器类，用来检查用户输入是否合法'''
        def isLegalWarpFunc(self,*args,**kargs):   #使用同一个装饰器是不是对被装饰的函数有统一的函数格式要求
            maxLength=self.length if func.__name__=='append' else self.length-1
            print(maxLength)
            self.isLegal(maxLength,*args,**kargs)
            func(self,*args,**kargs)        
        return isLegalWarpFunc 
    
    @checkLegal
    def append(self,index=-1,value=None):   
        '''向链表中的index位置添加元素'''
        newCell=ChainCell(value)
        if index==-1 or index==self.length:   #在最后插入元素
            self.last.next,self.last=newCell,newCell
        elif index==0 or index==-self.length-1:  #在第一个位置插入元素
            newCell.next=self.head
            self.head=newCell
        else:
            lastCell=self.head
            n=index-1 if index>0 else self.length-abs(index)
            for i in range(n):
                lastCell=lastCell.next
            newCell.next=lastCell.next
            lastCell.next=newCell
        self.length+=1
        return value
    
    @checkLegal
    def pop(self,index=-1):
        '''d出链表中的元素'''
        # 没有办法直接删除最后一个元素，因为要修改上一个元素的next指针
        if index==0:
            self.head=self.head.next
        else:
            n=index-1 if index>0 else self.length-abs(index)-1
            lastCell=self.head
            for i in range(n):
                lastCell=lastCell.next
            lastCell.next=lastCell.next.next   
        self.length-=1
    
    @checkLegal
    def getCell(self,index):
        '''对应“查”功能，是链表最基础的功能，时间复杂度为O(n)
        根据下标，获得某个链表元素的值,支持正负两种下标表示形式'''
        if index==0:
            return self.head.value
        else:
            lastCell=self.head
            n=index if index>0 else self.length-abs(index)+1
            for i in range(n):
                lastCell=lastCell.next
            return lastCell.value
    
    @checkLegal
    def setCell(self ,index,value):
        '''根据下标，设置某个链表元素的值'''
        lastCell=self.head
        n=index-1 if index>0 else self.length-abs(index)-1
        for i in range(n):
            lastCell=lastCell.next
        lastCell.next.value=value
        return value
    
    def printChain(self):
        '''输出所有的链表元素'''
        # for i in range(self.length): 两种遍历方式
        if not self.head:   #或者if self.length==0
            print('当前链表中没有元素！')
            return
        else:
            lastCell=self.head
            values=[lastCell.value]
            while lastCell.next:
                lastCell=lastCell.next
                values.append(lastCell.value)
            print(values)
    
    def getLen(self):
        '''输出链表的长度'''
        # return self.length  最简单，适合维护了这个变量的情况
        if not self.head:
            return 
        else:
            count=1
            lastCell=self.head
            while lastCell.next:
                lastCell=lastCell.next
                count+=1
            return count

 4. 修改版本3

将元素定位抽象为函数

'''链表，注意正负坐标的转化，abs(posiIndex)+abs(negaIndex)=self.length
    另外需要注意到底是定位到index前一个元素，还是index元素本身'''
class ChainCell():
    '''本类是链表的基础元素类'''
    def __init__(self,value=None,nextCell=None):
        self.value=value;
        self.next=nextCell;
        
class Chain():
    '''本类实现链表'''
    def __init__(self,values=None):   
        '''初始化函数，如果有初始元素，要求以链表或者元组的形式传递'''
        self.head=None
        if values:
            self.length=0
            for value in values:
                newCell=ChainCell(value)
                if not self.head:
                    self.head=newCell
                else:
                    self.last.next=newCell
                self.last=newCell
                self.length+=1
                
    def isLegal(self,funcName,*args,**kargs):   
        '''该函数为类的内部函数，用来判断用户输入的下标是否合理。
        如果下标不合理，则会报错，如果合理，则将index原路返回。
        funcName为函数的名称，因为append函数比get等函数的边界大一'''
        
        if not args:   #判断index参数是以何种形式给出的，args和kargs里存储的都是实参，默认值不会出现在里面
            if 'index' in kargs:
                index=kargs['index']
            else:
                index=-1
        else:
            index=args[0]

        maxLength=self.length+1 if funcName=='append' else self.length   #在这里改变链表的长度，好像不太好
        print('maxLength is ',maxLength)
        if index>maxLength-1 or (index<0 and abs(index)>maxLength):
            raise IndexError("下标超出支持的范围")
        elif not isinstance(index,int):
            raise IndexError("下标必须是整数")
        else:
            return index
        
    def checkLegal(func):
        '''装饰器类，用来检查用户输入是否合法'''
        def isLegalWarpFunc(self,*args,**kargs):   #使用同一个装饰器是不是对被装饰的函数有统一的函数格式要求
            self.isLegal(func.__name__,*args,**kargs)
            return func(self,*args,**kargs)        
        return isLegalWarpFunc 
    
    def neg2pos(self,index):
        if index<0: index=self.length-abs(index) 
        return index
    
    def getLast(self,index):
        '''该函数用来获得index位置的上一个元素并返回'''
        lastCell=self.head
        for i in range(index-1):
            lastCell=lastCell.next
        return lastCell
    
    @checkLegal
    def append(self,index=-1,value=None):   
        '''向链表中的index位置添加元素'''
        index=self.neg2pos(index)
        newCell=ChainCell(value)
        if index==self.length:   #在最后插入元素
            self.last.next,self.last=newCell,newCell
        elif index==0:  #在第一个位置插入元素
            newCell.next=self.head
            self.head=newCell
        else:
            lastCell=self.getLast(index)
            newCell.next=lastCell.next
            lastCell.next=newCell
        self.length+=1
        return value
    
    @checkLegal
    def pop(self,index=-1):
        '''弹出链表中的元素'''
        # 没有办法直接删除最后一个元素，因为要修改上一个元素的next指针
        index=self.neg2pos(index)
        if index==0:
            self.head=self.head.next
        else:
            lastCell=self.getLast(index)
            lastCell.next=lastCell.next.next   
        self.length-=1
    
    @checkLegal
    def getCell(self,index):
        '''对应“查”功能，是链表最基础的功能，时间复杂度为O(n)
        根据下标，获得某个链表元素的值,支持正负两种下标表示形式'''
        index=self.neg2pos(index)
        if index==0:
            return self.head.value
        else:
            lastCell=self.getLast(index)
            return lastCell.next.value
    
    @checkLegal
    def setCell(self ,index,value):
        '''根据下标，设置某个链表元素的值'''
        index=self.neg2pos(index)
        lastCell=self.head
        if index==0:
            lastCell.value=value
            return value
        lastCell=self.getLast(index)
        lastCell.next.value=value
        return value
    
    def printChain(self):
        '''输出所有的链表元素'''
        # for i in range(self.length): 两种遍历方式
        if not self.head:   #或者if self.length==0
            print('当前链表中没有元素！')
            return
        else:
            lastCell=self.head
            values=[lastCell.value]
            while lastCell.next:
                lastCell=lastCell.next
                values.append(lastCell.value)
            print(values)
    
    def getLen(self):
        '''输出链表的长度'''
        # return self.length  最简单，适合维护了这个变量的情况
        if not self.head:
            return 
        else:
            count=1
            lastCell=self.head
            while lastCell.next:
                lastCell=lastCell.next
                count+=1
            return count

5. 修改版本4

添加功能测试 。以上功能通过手工验证效果有限，还浪费时间。可以通过写一种完全正确的方法（不考虑复杂度），对比两种方法的输出，来验证方法的正确性。

'''链表，注意正负坐标的转化，abs(posiIndex)+abs(negaIndex)=self.length
    另外需要注意到底是定位到index前一个元素，还是index元素本身'''
import random  
class ChainCell():
    '''本类是链表的基础元素类'''
    def __init__(self,value=None,nextCell=None):
        self.value=value;
        self.next=nextCell;
        
class Chain():
    '''本类实现链表'''
    def __init__(self,values=None):   
        '''初始化函数，如果有初始元素，要求以链表或者元组的形式传递'''
        self.head=None
        if values:
            self.length=0
            for value in values:
                newCell=ChainCell(value)
                if not self.head:
                    self.head=newCell
                else:
                    self.last.next=newCell
                self.last=newCell
                self.length+=1
                
    def isLegal(self,*args,**kargs):   
        '''该函数为类的内部函数，用来判断用户输入的下标是否合理。
        如果下标不合理，则会报错，如果合理，则将index原路返回。
        funcName为函数的名称，因为append函数比get等函数的边界大一'''
        
        if not args:   #判断index参数是以何种形式给出的，args和kargs里存储的都是实参，默认值不会出现在里面
            if 'index' in kargs:
                index=kargs['index']
            else:
                index=-1
        else:
            index=args[0]

        if index>self.length-1 or (index<0 and abs(index)>self.length):
            raise IndexError( "index out of range")
        elif not isinstance(index,int):
            raise IndexError("下标必须是整数")
        else:
            return index
        
    def checkLegal(func):
        '''装饰器类，用来检查用户输入是否合法'''
        def isLegalWarpFunc(self,*args,**kargs):   #使用同一个装饰器是不是对被装饰的函数有统一的函数格式要求
            self.isLegal(*args,**kargs)
            return func(self,*args,**kargs)        
        return isLegalWarpFunc 
    
    def neg2pos(self,index):
        if index<0: index=self.length-abs(index) 
        return index
    
    def getLast(self,index):
        '''该函数用来获得index位置的上一个元素并返回'''
        lastCell=self.head
        for i in range(index-1):
            lastCell=lastCell.next
        return lastCell
    
    def append(self,index=-1,value=None):   
        '''向链表中的index位置之前添加元素'''
        if not isinstance(index,int): raise IndexError('下标必须是整数')
        if index<0:
            if abs(index)>=self.length:
                index=0
            else:
                index=self.length-abs(index)
        if index>=self.length: index=-1
            
        newCell=ChainCell(value)
        if index==-1:   #在最后插入元素
            self.last.next,self.last=newCell,newCell
        elif index==0:  #在第一个位置插入元素
            newCell.next=self.head
            self.head=newCell
        else:
            lastCell=self.getLast(index)
            newCell.next=lastCell.next
            lastCell.next=newCell
        self.length+=1
        return value
    
    @checkLegal
    def pop(self,index=-1):
        '''d出链表中的元素'''
        # 没有办法直接删除最后一个元素，因为要修改上一个元素的next指针
        index=self.neg2pos(index)
        if index==0:
            self.head=self.head.next
        else:
            lastCell=self.getLast(index)
            lastCell.next=lastCell.next.next   
        self.length-=1
    
    @checkLegal
    def getCell(self,index):
        '''对应“查”功能，是链表最基础的功能，时间复杂度为O(n)
        根据下标，获得某个链表元素的值,支持正负两种下标表示形式'''
        index=self.neg2pos(index)
        if index==0:
            return self.head.value
        else:
            lastCell=self.getLast(index)
            return lastCell.next.value
    
    @checkLegal
    def setCell(self ,index,value):
        '''根据下标，设置某个链表元素的值'''
        index=self.neg2pos(index)
        lastCell=self.head
        if index==0:
            lastCell.value=value
            return value
        lastCell=self.getLast(index)
        lastCell.next.value=value
        return value
    
    def printChain(self):
        '''输出所有的链表元素'''
        # for i in range(self.length): 两种遍历方式
        if not self.head:   #或者if self.length==0
            print('当前链表中没有元素！')
            return
        else:
            lastCell=self.head
            values=[lastCell.value]
            while lastCell.next:
                lastCell=lastCell.next
                values.append(lastCell.value)
            return values
    
    def getLen(self):
        '''输出链表的长度'''
        # return self.length  最简单，适合维护了这个变量的情况
        if not self.head:
            return 
        else:
            count=1
            lastCell=self.head
            while lastCell.next:
                lastCell=lastCell.next
                count+=1
            return count
        
class listChain():
    '''本类是用python的chain，实现类似于链表的功能，但是实际上底层结构和链表无关'''
    def __init__(self,values=None):
        self.values=[] if values==None else values
        
    def append(self,index=-1,value=None):
        '''Python insert函数，可以在指定的index前插入元素'''
        self.values.insert(index,value)  #indet函数中，如果下标超出数据界限，则默认添加在数组两端
        
    def pop(self,index=-1):
        self.values.pop(index)
        
    def getCell(self,index):
        return self.values[index]
    
    def setCell(self,index,value):
        self.values[index]=value
        return value
    
    def printChain(self):
        return self.values
        
    def getLen(self):
        return len(self.values)

def testChain(c,index):
    '''用于测试链表的功能，index 是随机产生的下标'''
    commands=['c.append({},{})'.format(index[0],index[1]),
              'c.pop(index={})'.format(index[2]),
              'z=c.getCell({})'.format(index[3]),
              'c.setCell(index={},value={})'.format(index[4],index[5])]
    for line in commands:   #通过循环，保证出现异常后，程序可以继续运行
        try:
              exec(line)
        except Exception as e :
            print(str(e))
            continue

#用户初始化链表的列表，可以放到循环外边或者里面，因为浅拷贝的问题，会导致修改链表也修改li
li=[1,2,3,4,5]
for k in range(100):   #设置测试多少次
    # print(li)
    #li=[random.randint(-10,10) for i in range(random.randint(1,10))]  
    c1=Chain(li)
    c2=listChain(li)
    indexes=[random.randint(-10,10) for i in range(6)]
    testChain(c1,indexes)
    testChain(c2,indexes)
    if c1.printChain()!=c2.printChain():
        print("*"*60)   #字符串中的字符串，要注意区分单双引号
        print(indexes)
        print(li)

 

参考文章：

Python 函数装饰器 | 菜鸟教程

python 使用装饰器做函数参数自动检查 - 知乎