浅谈Python单向链表的实现
作者:hebedich 时间:2023-01-18 14:00:39
链表由一系列不必在内存中相连的结构构成,这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向NULL。为了方便链表的删除与插入操作,可以为链表添加一个表头。
删除操作可以通过修改一个指针来实现。
插入操作需要执行两次指针调整。
1. 单向链表的实现
1.1 Node实现
每个Node分为两部分。一部分含有链表的元素,可以称为数据域;另一部分为一指针,指向下一个Node。
class Node():
__slots__=['_item','_next'] #限定Node实例的属性
def __init__(self,item):
self._item=item
self._next=None #Node的指针部分默认指向None
def getItem(self):
return self._item
def getNext(self):
return self._next
def setItem(self,newitem):
self._item=newitem
def setNext(self,newnext):
self._next=newnext
1.2 SinglelinkedList的实现
class SingleLinkedList():
def __init__(self):
self._head=None #初始化链表为空表
self._size=0
1.3 检测链表是否为空
def isEmpty(self):
return self._head==None
1.4 add在链表前端添加元素
def add(self,item):
temp=Node(item)
temp.setNext(self._head)
self._head=temp
1.5 append在链表尾部添加元素
def append(self,item):
temp=Node(item)
if self.isEmpty():
self._head=temp #若为空表,将添加的元素设为第一个元素
else:
current=self._head
while current.getNext()!=None:
current=current.getNext() #遍历链表
current.setNext(temp) #此时current为链表最后的元素
1.6 search检索元素是否在链表中
def search(self,item):
current=self._head
founditem=False
while current!=None and not founditem:
if current.getItem()==item:
founditem=True
else:
current=current.getNext()
return founditem
1.7 index索引元素在链表中的位置
def index(self,item):
current=self._head
count=0
found=None
while current!=None and not found:
count+=1
if current.getItem()==item:
found=True
else:
current=current.getNext()
if found:
return count
else:
raise ValueError,'%s is not in linkedlist'%item
1.8 remove删除链表中的某项元素
def remove(self,item):
current=self._head
pre=None
while current!=None:
if current.getItem()==item:
if not pre:
self._head=current.getNext()
else:
pre.setNext(current.getNext())
break
else:
pre=current
current=current.getNext()
1.9 insert链表中插入元素
def insert(self,pos,item):
if pos<=1:
self.add(item)
elif pos>self.size():
self.append(item)
else:
temp=Node(item)
count=1
pre=None
current=self._head
while count<pos:
count+=1
pre=current
current=current.getNext()
pre.setNext(temp)
temp.setNext(current)
全部代码
class Node():
__slots__=['_item','_next']
def __init__(self,item):
self._item=item
self._next=None
def getItem(self):
return self._item
def getNext(self):
return self._next
def setItem(self,newitem):
self._item=newitem
def setNext(self,newnext):
self._next=newnext
class SingleLinkedList():
def __init__(self):
self._head=None #初始化为空链表
def isEmpty(self):
return self._head==None
def size(self):
current=self._head
count=0
while current!=None:
count+=1
current=current.getNext()
return count
def travel(self):
current=self._head
while current!=None:
print current.getItem()
current=current.getNext()
def add(self,item):
temp=Node(item)
temp.setNext(self._head)
self._head=temp
def append(self,item):
temp=Node(item)
if self.isEmpty():
self._head=temp #若为空表,将添加的元素设为第一个元素
else:
current=self._head
while current.getNext()!=None:
current=current.getNext() #遍历链表
current.setNext(temp) #此时current为链表最后的元素
def search(self,item):
current=self._head
founditem=False
while current!=None and not founditem:
if current.getItem()==item:
founditem=True
else:
current=current.getNext()
return founditem
def index(self,item):
current=self._head
count=0
found=None
while current!=None and not found:
count+=1
if current.getItem()==item:
found=True
else:
current=current.getNext()
if found:
return count
else:
raise ValueError,'%s is not in linkedlist'%item
def remove(self,item):
current=self._head
pre=None
while current!=None:
if current.getItem()==item:
if not pre:
self._head=current.getNext()
else:
pre.setNext(current.getNext())
break
else:
pre=current
current=current.getNext()
def insert(self,pos,item):
if pos<=1:
self.add(item)
elif pos>self.size():
self.append(item)
else:
temp=Node(item)
count=1
pre=None
current=self._head
while count<pos:
count+=1
pre=current
current=current.getNext()
pre.setNext(temp)
temp.setNext(current)
if __name__=='__main__':
a=SingleLinkedList()
for i in range(1,10):
a.append(i)
print a.size()
a.travel()
print a.search(6)
print a.index(5)
a.remove(4)
a.travel()
a.insert(4,100)
a.travel()
标签:Python,单向链表
0
投稿
猜你喜欢
Python实现的最近最少使用算法
2022-07-10 22:48:27
微信小程序下载工具及调试详解
2022-10-30 09:06:05
在IE8中继续使用滤镜及IE8的一些CSS扩展属性
2009-02-21 11:18:00
phpstudy apache开启ssi使用详解
2023-05-25 08:04:44
python多进程操作实例
2021-12-02 21:42:46
php curl选项列表(超详细)
2023-07-18 15:19:32
vue指令之表单控件绑定v-model v-model与v-bind结合使用
2023-07-02 16:28:15
一次Mysql使用IN大数据量的优化记录
2024-01-29 07:49:19
调试Django时打印SQL语句的日志代码实例
2021-06-09 05:29:42
PHP 中文简繁互转代码 完美支持大陆、香港、台湾及新加坡
2023-11-15 11:46:16
Python私有属性私有方法应用实例解析
2022-11-08 05:09:03
javascript结合canvas实现图片旋转效果
2023-08-07 23:47:59
日式酒店电梯面板设计
2008-06-08 13:23:00
MySQL在Windows中net start mysql 启动MySQL服务报错 发生系统错误解决方案
2024-01-12 21:39:42
教你快速掌握怎样在Windows下升级MySQL
2008-12-31 17:08:00
浅析python递归函数和河内塔问题
2023-03-05 21:27:33
网站有效设计的10个原则
2008-02-11 17:12:00
浅谈数据库日期类型字段设计应该如何选择
2024-01-21 13:55:21
简单了解python字符串前面加r,u的含义
2021-12-26 19:08:39
Golang并发利器sync.Once的用法详解
2024-04-25 15:12:06