尝试用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):
'''弹出链表中的元素'''
# 没有办法直接删除最后一个元素，因为要修改上一个元素的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):
'''弹出链表中的元素'''
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):
'''弹出链表中的元素'''
# 没有办法直接删除最后一个元素，因为要修改上一个元素的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):
'''弹出链表中的元素'''
# 没有办法直接删除最后一个元素，因为要修改上一个元素的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 使用装饰器做函数参数自动检查 - 知乎
