浅谈Python单向链表的实现-Python-Tutorial-php.cn

链表由一系列不必在内存中相连的结构构成，这些对象按线性顺序排序。每个结构含有表元素和指向后继元素的指针。最后一个单元的指针指向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

Nach dem Login kopieren

1.2 SinglelinkedList的实现

class SingleLinkedList(): 
  def __init__(self):
    self._head=None  #初始化链表为空表
    self._size=0

Nach dem Login kopieren

1.3 检测链表是否为空

def isEmpty(self):
  return self._head==None

Nach dem Login kopieren

1.4 add在链表前端添加元素

def add(self,item):
  temp=Node(item)
  temp.setNext(self._head)
  self._head=temp

Nach dem Login kopieren

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为链表最后的元素

Nach dem Login kopieren

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

Nach dem Login kopieren

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

Nach dem Login kopieren

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

Nach dem Login kopieren

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)

Nach dem Login kopieren

全部代码

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

Nach dem Login kopieren

Verwandte Etiketten：

python

Quelle：php.cn

Vorheriger Artikel：在DigitalOcean的服务器上部署flaskblog应用 Nächster Artikel：在Windows系统上搭建Nginx+Python+MySQL环境的教程

Erklärung dieser Website

Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Neueste Artikel des Autors