Python数据结构之单链表详解

本文实例为大家分享了Python数据结构之单链表的具体代码，供大家参考，具体内容如下#节

本文实例为大家分享了Python数据结构之单链表的具体代码，供大家参考，具体内容如下

# 节点类
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

# 单链表
class SingleLinkedList():
 def __init__(self):
 self._head = None #初始化链表为空 始终指向链表的头部
 self._size = 0 # 链表大小

 # 返回链表的大小
 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 isEmpty(self):
 return self._head == None

 # 在链表前端添加元素
 def add(self,item):
 temp = Node(item) # 创建新的节点
 temp.setNext(self._head) # 新创建的next指针指向_head
 self._head = temp # _head指向新创建的指针

 # 在链表尾部添加元素
 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:
 return -1 # 返回-1表示不存在

 # 删除表中的某项元素
 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()

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持脚本之家。