## Python数据结构之单链表详解

| |
[ 所属分类 开发（python） | 发布者 店小二03 | 时间 | 作者 红领巾 ] 0人收藏点击收藏

# 节点类
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
# 单链表
def __init__(self):
self._size = 0 # 链表大小
# 返回链表的大小
def size(self):
count = 0
while current != None:
count += 1
current = current.getNext()
return count
# 遍历链表
def travel(self):
while current != None:
print(current.getItem())
current = current.getNext()
# 检查链表是否为空
def isEmpty(self):
# 在链表前端添加元素
temp = Node(item) # 创建新的节点
# 在链表尾部添加元素
def append(self,item):
temp = Node(item)
if self.isEmpty():
else:
while current.getNext() != None:
current = current.getNext() # 遍历列表
current.setNext(temp) # 此时current为链表最后的元素，在末尾插入
# 检索元素是否在链表中
def search(self,item):
founditem = False
if current.getItem() == item:
founditem = True
else:
current = current.getNext()
return founditem
# 索引元素在表中的位置
def index(self,item):
count = 0
found = None
count += 1
if current.getItem() == item:
found = True
else:
current = current.getNext()
if found:
return count
else:
return -1 # 返回-1表示不存在
# 删除表中的某项元素
def remove(self,item):
pre = None
while current!=None:
if current.getItem() == item:
if not pre:
else:
pre.setNext(current.getNext())
break
else:
pre = current
current = current.getNext()
# 在链表任意位置插入元素
def insert(self,pos,item):
if pos <= 1:
elif pos > self.size():
self.append(item)
else:
temp = Node(item)
count = 1
pre = None
while count < pos:
count += 1
pre = current
current = current.getNext()
pre.setNext(temp)
temp.setNext(current)
if __name__=='__main__':
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()