python实现单链表的方法示例

前言

首先说下线性表,线性表是一种最基本,最简单的数据结构,通俗点讲就是一维的存储数据的结构。

线性表分为顺序表和链接表:

  • 顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,称为线性表的顺序存储结构或顺序映像;
  • 链式表示指的是用一组任意的存储单元存储线性表中的数据元素,称为线性表的链式存储结构。而他既可以是连续的也可以不连续,是通过一个与后继结点的连接信息构建起来的。

*顺序表(这个不是本次重点,简单介绍一下)

顺序表是用一段连续的存储单元依次存储数据元素,查找元素是很方便的,但是如果要向其中添加删除元素就不那么简单了。因为添加删除元素要先找到那个位置,由于顺序表内部是通过地址的连续才使他成为一个表,当删掉元素时,要把后面的元素全部向前移,填补上空出来的地址空间;添加元素也是一样,需要先把该位置后面的元素向后移去,才能在这块地址上添加元素。

以C语言为例:顺序表可以通过一个数组来表示,每创建一个数组就对应给他分配一块内存。当然除了静态分配空间,还可以动态扩展。后续的操作要在这块内存上进行,一般都需要移动数组元素,复杂度会很高。

在python中,顺序表还有两种表示方式:

  • 一体式结构
  • 分离式结构

这里的一体和分离是指表中的元素集合,和为实现正确操作而需记录的信息,这两部分是在同一块空间还是在旁边的一块新的空间中。

python中的tuple和list就是采用了顺序表的实现技术,不过tuple是不可变的,不支持对内部的操作。而list是一个元素个数可变的线性表,支持添加删除等操作。list的思想其实是和C语言中一样的,只是对其中的功能进行了一些封装,也就是list的那些属性。

*链式表

链表,顾名思义,相邻结点是通过链来连接的,那么什么是链呢。我们知道,C语言中有指针,指针通过地址来找到他的目标。如此说来,一个节点不仅仅有他的元素,还需要有一个他下一个元素的地址。

那么,这里需要指针和地址。python中的指针是什么呢?下面先把这个放一下,先去理解一下python里面变量标识的实质。

先看一下这个,为什么a和b的id是一样的呢?那我再问一个问题:python中交换两个变量的值时怎样来实现的?

1 a = 10
2 b = 20
3 a,b = b,a

为什么python可以这样来赋值呢?下面我再画一幅图。

 

现在是否能理解了呢,变量本身就是存储的一个地址,交换他们的值就是把自己的指向更改一下。那么现在知道了标识的含义,我们的指针域该怎么写呢,是不是直接用变量等于下一个结点啊。这样看来就不复杂了,接下来的内容就和一般的链表一样了。我在这里说这些就是为了弄清楚python是怎么建立链接的。

一、单链表

那么下面就通过一个类来实现一个节点,节点当中包括数据域和链接域,代码中实现了一些常用的功能,比如插入,查找等等。今天主要是说一下单链表是如何运用到python中的,由于我之前没有了解过这些。学习了之后,用自己之前的知识,就可以很方便的运用链表了。后面的代码就不过多解释了,自己仔细琢磨一下。有什么不理解的可以留言,我会尽量详细的回复。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Date  : 2018-06-12 11:23:21
# @Author : yudanqu (943775910@qq.com)
# @Link  : https://www.cnblogs.com/yudanqu/
# @Version : $Id$

class Node(object):
  """节点"""

  def __init__(self, elem):
    self.elem = elem
    self.next = None # 初始设置下一节点为空

'''
上面定义了一个节点的类,当然也可以直接使用python的一些结构。比如通过元组(elem, None)
'''

# 下面创建单链表,并实现其应有的功能

class SingleLinkList(object):
  """单链表"""

  def __init__(self, node=None): # 使用一个默认参数,在传入头结点时则接收,在没有传入时,就默认头结点为空
    self.__head = node

  def is_empty(self):
    '''链表是否为空'''
    return self.__head == None

  def length(self):
    '''链表长度'''
    # cur游标,用来移动遍历节点
    cur = self.__head
    # count记录数量
    count = 0
    while cur != None:
      count += 1
      cur = cur.next
    return count

  def travel(self):
    '''遍历整个列表'''
    cur = self.__head
    while cur != None:
      print(cur.elem, end=' ')
      cur = cur.next
    print("\n")

  def add(self, item):
    '''链表头部添加元素'''
    node = Node(item)
    node.next = self.__head
    self.__head = node

  def append(self, item):
    '''链表尾部添加元素'''
    node = Node(item)
    # 由于特殊情况当链表为空时没有next,所以在前面要做个判断
    if self.is_empty():
      self.__head = node
    else:
      cur = self.__head
      while cur.next != None:
        cur = cur.next
      cur.next = node

  def insert(self, pos, item):
    '''指定位置添加元素'''
    if pos <= 0:
        # 如果pos位置在0或者以前,那么都当做头插法来做
      self.add(item)
    elif pos > self.length() - 1:
      # 如果pos位置比原链表长,那么都当做尾插法来做
      self.append(item)
    else:
      per = self.__head
      count = 0
      while count < pos - 1:
        count += 1
        per = per.next
      # 当循环退出后,pre指向pos-1位置
      node = Node(item)
      node.next = per.next
      per.next = node

  def remove(self, item):
    '''删除节点'''
    cur = self.__head
    pre = None
    while cur != None:
      if cur.elem == item:
        # 先判断该节点是否是头结点
        if cur == self.__head:
          self.__head = cur.next
        else:
          pre.next = cur.next
        break
      else:
        pre = cur
        cur = cur.next

  def search(self, item):
    '''查找节点是否存在'''
    cur = self.__head
    while not cur:
      if cur.elem == item:
        return True
      else:
        cur = cur.next
    return False

if __name__ == "__main__":

    # node = Node(100) # 先创建一个节点传进去

  ll = SingleLinkList()
  print(ll.is_empty())
  print(ll.length())

  ll.append(3)
  ll.add(999)
  ll.insert(-3, 110)
  ll.insert(99, 111)
  print(ll.is_empty())
  print(ll.length())
  ll.travel()
  ll.remove(111)
  ll.travel()

二、单向循环链表和双向链表

与单链表相关联的,还有单向循环链表和双向链表:

单向循环链表:在单链表的基础上,再多一个由尾节点指向首节点的链接,首节点是指链表的第一个存数据的结点,而头结点是指指向第一个存数据的结点的那个东西,仅有个链接域,而不是真正存储内容的链表结点。需要注意的是,循环链表中,一些功能的创建是和单链表不一样的,比如判空、判满,它是循环的该怎么判断呢?这些内容可以在上面给出的单链表的实现中进行修改获得,可以试一下。

双向链表:与单链表相比,这个新增的特性就是双向。可以从前面向后面传递,也可以从后面向前面传递,这个前面和后面是我们自己定义的,认为从一端到另一端是正向,那么倒过来则相反。这个双向链表的实现和单链表也是基本上一样的。单向链表是除了数据域再添加一个链接域,来指向下一个结点。那么同样的道理,双向链表就再添加一个指向前一个结点的链接不就好了。这个时候再创建链表的时候就要把每个节点与前驱结点以及后继结点的链接建立好。

双向链表的插入和删除等等操作,都要注意,不要把存储的地址信息丢了,仔细考虑好两边的指向,先把谁链接上去,再链接谁。

今天本来只想说说前面那一点点内容的,写的写的,后面感觉不得不说一下,不过也没有写的比较完整。大家捡有用的东西来看。

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对我们的支持。

(0)

相关推荐

  • python实现单链表中删除倒数第K个节点的方法

    本文实例为大家分享了python实现单链表中删除倒数第K个节点的具体代码,供大家参考,具体内容如下 题目: 给定一个链表,删除其中倒数第k个节点. 代码: class LinkedListAlgorithms(object): def __init__(self): pass def rm_last_kth_node(self, k, linked_list): # 删除倒数第 K 个节点,针对单链表的 if linked_list.is_empty(): print 'The given li

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • python单链表实现代码实例

    链表的定义:链表(linked list)是由一组被称为结点的数据元素组成的数据结构,每个结点都包含结点本身的信息和指向下一个结点的地址.由于每个结点都包含了可以链接起来的地址信息,所以用一个变量就能够访问整个结点序列.也就是说,结点包含两部分信息:一部分用于存储数据元素的值,称为信息域:另一部分用于存储下一个数据元素地址的指针,称为指针域.链表中的第一个结点的地址存储在一个单独的结点中,称为头结点或首结点.链表中的最后一个结点没有后继元素,其指针域为空. python单链表实现代码: 复制代码

  • python版本单链表实现代码

    今天看了一下数据结构的书,发现其实数据结构没有几种,线性表,数组,字符串,队列和栈,等等,其实是一回事,然后就是树结构,图结构.数据结构的理论并不难,主要是要自己写一下这些数据结构以及对应的基本的操作方法,这样就能够更快的提高. 这一篇blog写一下线性表. 线性表:分为顺序表和链表 一.顺序表 顺序表就是相对于表中的数据,地址也是顺序的,所以可以随机存取.但是在操作插入和删除元素的时候,由于要满足地址的连续性,所以要移动很多的元素位置,因此,插入或者删除一个顺序表的元素的时间复杂度是o(n).

  • 单链表反转python实现代码示例

    单链表的反转可以使用循环,也可以使用递归的方式 1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可. 代码: class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head): #循环的方法反转链表 if head is None or head.next is None: return head; pre=None; c

  • 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 s

  • Python实现针对给定单链表删除指定节点的方法

    本文实例讲述了Python实现针对给定单链表删除指定节点的方法.分享给大家供大家参考,具体如下: 题目: 初始化定义一个单链表,删除指定节点,输出链表 下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:给定一个单链表删除指定节点 ''' class Node(object): ''''' 节点类 ''' def __init__(self,data): self.num=data self.next=N

  • Python单链表的简单实现方法

    本文实例讲述了Python单链表的简单实现方法,分享给大家供大家参考.具体方法如下: 通常来说,要定义一个单链表,首先定义链表元素:Element.它包含3个字段: list:标识自己属于哪一个list datum:改元素的value next:下一个节点的位置 具体实现代码如下: class LinkedList(object): class Element(object): def __init__(self,list,datum,next): self._list = list self.

  • Python3实现的反转单链表算法示例

    本文实例讲述了Python3实现的反转单链表算法.分享给大家供大家参考,具体如下: 反转一个单链表. 方案一:迭代 # Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head): """ :type head: ListNod

  • Python单链表简单实现代码

    本文实例讲述了Python单链表简单实现代码.分享给大家供大家参考,具体如下: 用Python模拟一下单链表,比较简单,初学者可以参考参考 #coding:utf-8 class Node(object): def __init__(self, data): self.data = data self.next = None class NodeList(object): def __init__(self, node): self.head = node self.head.next = No

随机推荐