程序员之家 服务器常用软件
快捷导航
您的位置：首页 → 脚本专栏 → python → Python单向链表的实现

浅谈Python单向链表的实现

 更新时间：2015年12月24日 11:21:16   投稿：hebedich  
本文给大家简单介绍了下链表的知识，然后用Python模拟一下单链表，比较简单，初学者可以参考参考，大神可以给我点改进意见
（福利推荐：【腾讯云】服务器最新限时优惠活动，云服务器1核2G仅99元/年、2核4G仅768元/3年，立即抢购>>>：9i0i.cn/qcloud）

（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）

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

1.2 SinglelinkedList的实现

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

1.3 检测链表是否为空

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

1.4 add在链表前端添加元素

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

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

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

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

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

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)

全部代码

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

您可能感兴趣的文章:

相关文章

  • pycharm中导入不了torch包的解决方案

    pycharm中导入不了torch包的解决方案

    这篇文章主要介绍了pycharm中导入不了torch包的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教
    2023-08-08
  • python 普通克里金（Kriging）法的实现

    python 普通克里金（Kriging）法的实现

    这篇文章主要介绍了python 普通克里金（Kriging）法的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
    2019-12-12
  • tensorflow实现残差网络方式(mnist数据集)

    tensorflow实现残差网络方式(mnist数据集)

    这篇文章主要介绍了tensorflow实现残差网络方式(mnist数据集)，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧
    2020-05-05
  • 利用Python实现Picgo图床工具

    利用Python实现Picgo图床工具

    这篇文章主要介绍了如何利用Python实现Picgo图床工具，PyPicGo?是一款图床工具,是PicGo是Python版实现，并支持各种插件自定义插件，目前PyPicGo自带了gitee、github、SM.MS和七牛云图传，以及rename、notify和typora等插件,下面来看文章内容介绍,需要的朋友可以参考一下
    2021-11-11
  • 使用PyTorch将文件夹下的图片分为训练集和验证集实例

    使用PyTorch将文件夹下的图片分为训练集和验证集实例

    今天小编就为大家分享一篇使用PyTorch将文件夹下的图片分为训练集和验证集实例，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧
    2020-01-01
  • 在Python中使用循环进行迭代的方法小结

    在Python中使用循环进行迭代的方法小结

    Python中的循环结构是编程中的重要组成部分,本文详细介绍这两种循环的使用方法、它们之间的差异以及如何选择合适的循环类型,此外,我还将介绍一些高级循环控制技巧,如列表推导式和生成器表达式,感兴趣的朋友一起看看吧
    2024-01-01
  • python 多线程与多进程效率测试

    python 多线程与多进程效率测试

    这篇文章主要介绍了python 多线程与多进程效率测试，在Python中，计算密集型任务适用于多进程，IO密集型任务适用于多线程、接下来看看文章得实例吧,需要的朋友可以参考一下哟
    2021-10-10
  • python实现简单贪吃蛇游戏

    python实现简单贪吃蛇游戏

    这篇文章主要为大家详细介绍了python实现简单贪吃蛇游戏，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下
    2020-09-09
  • 三步实现Django Paginator分页的方法

    三步实现Django Paginator分页的方法

    这篇文章主要介绍了三步实现Django Paginator分页的方法，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
    2019-06-06
  • 用python写PDF转换器的实现

    用python写PDF转换器的实现

    这篇文章主要介绍了用python写PDF转换器的实现，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
    2020-10-10

最新评论

?


http://www.vxiaotou.com