python单向链表实例详解

使用python实现单向链表,供大家参考,具体内容如下

单向链表:是将所有的数据作为一个个节点,将所有的节点链接在一起。每一个节点中又分为: 存储数据区,链接区

存储数据区: 存储具体的数据

链接区: 指向下一个节点

分析实现:

1、 分析:根据链表的特性,首先要存放有数据的容器,还要有存放节点的容器
2、 节点类中:要有数据区和next区
3、 链表类中:存放所有节点

单链表操作

1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在

代码实现

# Functions  函数声明
class Node():
    """
    存放节点类
    每次调用该类,实例化一个节点
    默认每个节点中有数据区,next区。
    数据区为该数据,next区为空
    """
    def __init__(self, item,next=None):
        self.item = item
        self.next = next
        pass

class Linklist():
    """
    存放数据类
    将所有的节点存放起来的容器
    首先,默认链表为空,在这里需要有一个头节点,默认头节点为空

    """
    def __init__(self, head=None):
        self.head = head

    def is_empty(self):
        return self.head == None

    def append(self, item):
        """
        往链表尾部添加数据
        1、实例化游标:使用游标指向每一个数据,检索数据和判断数据next是否为空
        2、移动游标,从头节点开始,每次使用self.next移动,以为next指向的就是下一个数据
        3、添加数据,首先判断链表是否为空,为空的情况下,直接将头节点等于node数据
        4、如果不为空,需要从头节点开始,移动游标,判断游标指向的next是否为空
        5、使用循环不停的移动节点,当遇到节点中的next为空的情况下停止移动
        6、循环条件: 当 条件 != None, 进入循环获取,当cur为空时就不会进入循环,所以在这里要使用 cur != None
        """
        # 首先要实例化一个节点
        node = Node(item)
        # 如果链表为空
        if self.is_empty():
            # 直接将头节点的next添加node
            self.head = node
        else:
            # 实例化一个游标
            cur = self.head
            while cur.next != None:
                # 移动游标,得到最后一个游标的数据
                cur = cur.next
            # 将移动后的数据的下一个next添加上 node
            cur.next=node
            pass

    def travel(self):
        """遍历数据"""
        # 实例化一个游标
        cur = self.head
        # 数据链为空的情况
        if self.is_empty():
            print('')
        else:
            # 获取每个数据区中的数据
            # 移动游标,每移动一次,输出一次数据区内的数据
            while cur != None:
                print(cur.item, end=' ')
                cur = cur.next
            print()

    def length(self):
        """返回链表的长度"""
        # 实例化游标
        cur = self.head
        # 计数,这里对空链表进行判断,如果是链表,则不会进入循环,直接输出 0
        count = 0
        # 移动游标,获取下一个数据,然后让count +=1
        while cur != None:
            # 计数
            count+=1
            # 移动游标
            cur = cur.next
        return count

    def add(self, item):
        """
        头部添加数据
        分析: 将数据添加到第一个节点当中
        1、 需要先将node的next指向 原第一个节点,这原第一个节点就是self.head
        2、 再讲self.head指向node进行连接
        """
        # 先实例化节点
        node = Node(item)
        # 将数据添加到头部当中
        node.next=self.head
        self.head=node

    def insert(self, index, item):
        """
        指定位置添加数据
        分析:
        1、首先要找到,该位置的数据
        2、将要添加的数据next等于 原位置的next数据
        3、原数据的 next等于node新数据
        """
        if index<=0:
            # 如果输入的索引小于或者等于O,默认使用头插发
            self.add(item)
        elif index>self.length():
            # 如果输入的索引大于链表的长度,使用尾插法
            self.append(item)
        else:
            # 实例化数据节点
            node = Node(item)
            # 找到该数据的位置
            # 实例化一个游标
            cur = self.head
            # 计数
            conent = 0
            while conent<(index-1):
                conent+=1
                cur = cur.next

            node.next=cur.next
            cur.next=node

    def search(self, item):
        """
        查询指定的数据是否存在
        分析: 查询指定的数据,需要对整个链表扫描,判断这个数据是否等的该节点中的数据
        """
        # 实例化一个游标
        cur = self.head
        # 进行判断是否相等
        while cur != None:
            # 判断
            if cur.item == item:
                return True
            else:
                cur = cur.next
            pass
        # 否则返回False
        return False

    def remove(self, item):
        """
        移除指定的数据
        分析:
        1、删除数据,需要首先判断数据是否存在
        2、找到该数据所在的位置,将该数据的上一个数据的next指向自己的next
        3、如何获取该数据的指向,和上一个数据的指向
        4、需要定义两个指针
        5、先将两个指针相等,再讲一个指针先移动一次,再同时移动

        """
        # 先找到该数据
        cur = self.head
        por = None

        while cur != None:
            if cur.item==item:
                # 要判断是否为第一个节点
                if cur == self.head:
                    self.head = cur.next
                else:
                    por.next = cur.next
                break
            else:
                # 如果在当前节点中没有相等的,将节点进行移动
                # 移动要注意,现将两个游标相等,再讲另一个游标移动一次
                por = cur
                cur = cur.next

测试运行

# 程序的入口
if __name__ == "__main__":
    s = Linklist()
    s.append(100)
    s.append(200)
    s.append(300)
    s.add(1)
    s.add(12)
    s.insert(-1,6)
    
    s.travel()       #  6 12 1 100 200 300 
    print(s.length())  # 6
    print(s.search(11)) # False
    s.remove(12)
    s.travel()       # 6 1 100 200 300 
    print(s.length())  # 5
    print(s.search(11)) # False
    pass

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • python如何实现单向链表及单向链表的反转

    链表的定义 链表中的每个节点会存储相邻节点的位置信息,单链表中的每个节点只存储下一关节点的位置信息 单向链表的实现 class ListNode: def __init__(self, val): self.val = val self.next = None 要实现单向链表只需要把几个节点关联起来就可以了,把一个节点的next设置为另一个节点就可以了,例如创建一个A->B->C 的单向链表可以这么写: first_node = ListNode("A") second_n

  • Python单向链表和双向链表原理与用法实例详解

    本文实例讲述了Python单向链表和双向链表原理与用法.分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大. 链表由一个个节点组成. 单向链表的节点分为两个部分:存储的对象和对下一个节点的引用.注意是指向下一个节点. 而双向链表区别于单向链表的是它是由三个部分组成:存储的对象.对下一个节点的引用.对上一个节点的引用,可以实现双向遍历. 单向列表的结构如下图: head是头节点,tail是尾节点,每个节点由Data存储对象和Next对下

  • 浅谈Python单向链表的实现

    链表由一系列不必在内存中相连的结构构成,这些对象按线性顺序排序.每个结构含有表元素和指向后继元素的指针.最后一个单元的指针指向NULL.为了方便链表的删除与插入操作,可以为链表添加一个表头. 删除操作可以通过修改一个指针来实现. 插入操作需要执行两次指针调整. 1. 单向链表的实现 1.1 Node实现 每个Node分为两部分.一部分含有链表的元素,可以称为数据域:另一部分为一指针,指向下一个Node. class Node(): __slots__=['_item','_next'] #限定N

  • python实现单向链表详解

    本文研究的主要是Python中实现单向链表的相关内容,具体如下. 什么是链表 链表顾名思义就是-链 链表是一种动态数据结构,他的特点是用一组任意的存储单元存放数据元素.链表中每一个元素成为"结点",每一个结点都是由数据域和指针域组成的.跟数组不同链表不用预先定义大小,而且硬件支持的话可以无限扩展. 链表与数组的不同点: 数组需要预先定义大小,无法适应数据动态地增减,数据小于定义的长度会浪费内存,数据超过预定义的长度无法插入.而链表是动态增删数据,可以随意增加. 数组适用于获取元素的操作

  • Python实现单向链表

    单向链表每个节点都是由两部分组成:数据字段和指针,指针指向下一个元素在内存中的位置. 单向链表的第一个节点节点是链表头指针,而最后一个节点的指针设为None,不指向任何元素.(链表头指针相当重要!!!) 使用Python实现单向链表,我们可以使用一个节点类来封装节点,每创建一个节点就生成一个节点类的实例. 这里主要实现了单向链表节点的遍历.添加.插入.删除,反转. 代码如下: class Player:     """节点类"""     def

  • python实现获取单向链表倒数第k个结点的值示例

    本文实例讲述了python实现获取单向链表倒数第k个结点的值.分享给大家供大家参考,具体如下: #初始化链表的结点 class Node(): def __init__(self,item): self.item = item self.next = None #传入头结点,获取整个链表的长度 def length(headNode): if headNode == None: return None count = 0 currentNode =headNode #尝试了一下带有环的链表,计算

  • python数据结构链表之单向链表(实例讲解)

    单向链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域elem用来存放具体的数据. 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点. 节点实现 class Node(object): """单链表的结点""" def __i

  • python实现反转部分单向链表

    题目: 给定一个单链表的头指针 head, 以及两个整数 a 和 b,在单链表中反转 linked_list[a-b] 的结点,然后返回整个链表的头指针. 例如: 单链表[1000, 5, 12, 100, 45, 'cecil', 999], a = 4, b = 6, 返回的链表是[1000, 5, 12, 100, 999, 'cecil', 45],也就是说, a 和 b分别为索引值.如果a 和 b 超过了索引范围就返回错误. 代码: 我写的不够简洁,比较繁琐,但是能跑通,繁琐的原因在于

  • python中的单向链表实现

    目录 一.单向链表概念 二.建立节点对象 三.链表对象的初始定义 四.判断链表是否为空 五.获取链表长度 六.向头部添加节点 七.向尾部添加节点 八.指定位置插入节点 九.删除指定位置的节点 十.查找是否有该数据的节点 十一.遍历输出整个链表 十二.输入数据创建链表 十三.具体实现 一.单向链表概念 单向链表的链接方向是单向的,由结点构成,head指针指向第一个成为head结点,而终止于最后一个指向None的指针,对链表的访问要通过顺序读取从头部开始. 二.建立节点对象 class Node:

  • python单向链表实例详解

    使用python实现单向链表,供大家参考,具体内容如下 单向链表:是将所有的数据作为一个个节点,将所有的节点链接在一起.每一个节点中又分为: 存储数据区,链接区 存储数据区: 存储具体的数据 链接区: 指向下一个节点 分析实现: 1. 分析:根据链表的特性,首先要存放有数据的容器,还要有存放节点的容器2. 节点类中:要有数据区和next区3. 链表类中:存放所有节点 单链表操作 1.链表是否为空2.链表的长度3.遍历链表4.链表头部添加元素5.链表尾部添加元素6.链表指定位置添加元素7.链表删除

  • python单向循环链表实例详解

    使用python实现单向循环链表,供大家参考,具体内容如下 单向循环链表 将所有的链接在一起,每一个节点分为数据存储区和链接区,数据区存储数据,链接区链接下一个节点 item: 存储数据的地方next: 链接下一个节点注意: 单向循环链表是首位链接,即尾部的节点要和头部的节点链接 单向链表操作 1.链表是否为空2.链表的长度3.遍历链表4.链表头部添加元素5.链表尾部添加元素6.链表指定位置添加元素7.链表删除节点8.查找节点是否存在 代码实现 # Functions  函数声明 class N

  • Python 调用Java实例详解

    Python 调用Java实例详解 前言: Python 对服务器端编程不如Java 所以这方面可能要调用Java代码 前提: Linux 环境  1 安装 jpype1 安装后测试代码: from jpype import * startJVM(getDefaultJVMPath(), "-ea") java.lang.System.out.println("Hello World") shutdownJVM() 2 调用非jdk的jar包, test.jar 包

  • python 系统调用的实例详解

    python 系统调用的实例详解               本文将通过两种方法对python 系统调用进行讲解,包括python使用CreateProcess函数运行其他程序和ctypes模块的实例, 一 python使用CreateProcess函数运行其他程序 >>> import win32process >>> handle = win32process.CreateProcess('c:\\windows\\notepad.exe','',None,None

  • Python 加密的实例详解

     Python 加密的实例详解 hashlib支持md5,sha1,sha256,sha384,sha512,用法和md5一样 import hashlib #hashlib支持md5,sha1,sha256,sha384,sha512,用法和md5一样 m = hashlib.md5() #创建加密对象 m.update(b'password') #对输入内容进行加密, m.digest() #获取二进制加密密文 m.hexdigest() #获取十六进制加密密文 '''''python3默认

  • Python 异常处理的实例详解

    Python 异常处理的实例详解 与许多面向对象语言一样,Python 具有异常处理,通过使用 try...except 块来实现. Note: Python v s. Java 的异常处理 Python 使用 try...except 来处理异常,使用 raise 来引发异常.Java 和 C++ 使用 try...catch 来处理异常,使用 throw 来引发异常. 异常在 Python 中无处不在:实际上在标准 Python 库中的每个模块都使用了它们,并且 Python 自已会在许多不

  • Python字符串处理实例详解

    Python字符串处理实例详解 一.拆分含有多种分隔符的字符串 1.如何拆分含有多种分隔符的字符串 问题: 我们要把某个字符串依据分隔符号拆分不同的字段,该字符串包含多种不同的分隔符,例如: s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz" 其中;,|,\t 都是分隔符号,如何处理? 方法一: 连续使用str.split()方法,每次处理一种分隔符号 s = "ab;cd|efg|hi,jkl|mn\topq;rst,uvw\txyz&q

  • Linux中的内核链表实例详解

    Linux中的内核链表实例详解 链表中一般都要进行初始化.插入.删除.显示.释放链表,寻找节点这几个操作,下面我对这几个操作进行简单的介绍,因为我的能力不足,可能有些东西理解的不够深入,造成一定的错误,请各位博友指出. A.Linux内核链表中的几个主要函数(下面是内核中的源码拿出来给大家分析一下) 1)初始化: #define INIT_LIST_HEAD(ptr) do { \ (ptr)->next = (ptr); (ptr)->prev = (ptr); \ } while (0)

  • Python 多线程的实例详解

     Python 多线程的实例详解 一)线程基础 1.创建线程: thread模块提供了start_new_thread函数,用以创建线程.start_new_thread函数成功创建后还可以对其进行操作. 其函数原型: start_new_thread(function,atgs[,kwargs]) 其参数含义如下: function: 在线程中执行的函数名     args:元组形式的参数列表.     kwargs: 可选参数,以字典的形式指定参数 方法一:通过使用thread模块中的函数创

  • C++调用Python基础功能实例详解

    c++调用Python首先安装Python,以win7为例,Python路径为:c:\Python35\,通过mingw编译c++代码. 编写makefile文件,首先要添加包含路径: inc_path += c:/Python35/include 然后添加链接参数: ld_flag += c:/Python35/libs/libpython35.a 在源文件中添加头文件引用: #include "Python.h" Python解释器需要进行初始化,完成任务后需要终止: void s

随机推荐