实例详解Python数据结构之单链表-木庄网络博客

本文摘自php中文网，作者巴扎黑，侵删。

这篇文章主要为大家详细介绍了Python数据结构之单链表的相关资料，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

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