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()