使用python实现链表操作
一、概念梳理
链表是计算机科学里面应用应用最广泛的数据结构之一。它是最简单的数据结构之一，同时也是比较高阶的数据结构（例如棧、环形缓冲和队列）
简单的说，一个列表就是单数据通过索引集合在一起。在C里面这叫做指针。比方说，一个数据元素可以由地址元素，地理元素、路由信息活着交易细节等等组成。但是链表里面的元素类型都是一样的，是一种特殊的列表。
一个单独的列表元素叫做一个节点。这些节点不像数组一样都按顺序存储在内存当中，相反，你可以通过一个节点指向另外一个节点的指针在内存不同的地方找到这些元素。列表最后一项习惯用NIL表示，相当于python里面的None
这里介绍两种不同的列表——单链表和双链表。双链表中的某个节点只会指向列表中的下一个元素，但是在双链表里面，当前节点同时也会指向前一个节点。所以双链表会占用更多的内存，因为它需要额外的变量去存储索引
图一、单链表
图2:双链表
单链表可以从头到尾顺序查询，但是反过来就不是那么容易了。然而，双链表不管你是从哪个节点开始，从任意方向查询都是一样的。在单链表中增加和删除节点只需要两步，但是在双链表里就需要四步了。
但是在python里面没有提供像双链表一样的数据结构，所以我们可以自己创建一个这样的数据结构
二、如果使用python创建链表
（1）.将节点定义成一个数据结构
首先我们将节点类定义成ListNode，该类在初始化实例对象时，定义了两个实例变量，其中data用来存储节点的值，next用来存储下一个节点的索引，下面详细介绍一下一个节点要定义的方法和属性
__init__()：初始化节点 self.data：存储节点的值 self.next：存储指向下一个节点的索引 has_value()：将当前节点值和其他的值比较
上面的方法和属性涵盖了一个节点应有的基本属性和行为
Listing1:The ListNode class
上面创建了最简单的节点类，下面初始化ListNode的对象
Listing2:初始化节点
上面创建了三个独立的节点
（2）创建一个单链表类
现在我们定义一个名为SingleLinkedList的类去管理我们的节点，它包含了下面这些方法：
__init__()：初始化对象 list_length()：返回节点数量 output_list():输出节点值 add_list_item():在列表末尾增加一个新的节点 unordered_search():根据一个特殊值去查询列表 remove_list_item_by_id()：根据节点id移除节点
下面一一讲解这些方法
__init__()定义了head和tail，都初始化为None
Listing3:The SingleLinkedList class(part one)
(3)、添加节点
通过add_list_item()添加列表元素。先检测是不是ListNode的实例，如果不是，就新建一个节点。如果列表还是空的话，就把该节点当作头节点，如果不是空，就将当前节点指向下一个元素（也就是刚新添加的节点）。把新节点添加到列表当中
Listing4:The SinglelinkedList class(part two)
list_length()方法计算节点数量，返回列表的长度。在一个循环当中循环列表，self.next依次指向下一个节点
Listing5:The SingleLinkedList class(part three)
output_list()用来输出新的节点值
Listing6:The SingleLinkedList class(part four)
下面我们初始化SingleLinkedList的实例track，然后创建4个节点。
（4）查询列表
查询整个列表使用unordered_search()。它需要使用一个额外的参数帮助查询。列表的头是切入点。
(5)、从列表中移除一个元素
从列表中移除一个节点 时，指向该节点索引需要被移动到，被移除节点的下一个节点。被移除的节点会由python的垃圾回收机制清除
Listing10:Removing a node by node number
（6）、创建一个双链表
创建双链表其实就是在ListNode的基础上，在创建一个previous的属性
Listing11：Extended list node class
然后我们就可以依据上面的定义新建一个双链表类
添加新的节点跟单链表有所不同
移除双链表中的节点
python实际运用
输出结果
（7）、使用队列实现双向列表
您可能感兴趣的文章:
- Python 数据结构之旋转链表
- Python数据结构之翻转链表
- 浅谈Python单向链表的实现
- Python实现的数据结构与算法之链表详解
相关推荐
-
浅谈Python单向链表的实现
链表由一系列不必在内存中相连的结构构成,这些对象按线性顺序排序.每个结构含有表元素和指向后继元素的指针.最后一个单元的指针指向NULL.为了方便链表的删除与插入操作,可以为链表添加一个表头. 删除操作可以通过修改一个指针来实现. 插入操作需要执行两次指针调整. 1. 单向链表的实现 1.1 Node实现 每个Node分为两部分.一部分含有链表的元素,可以称为数据域:另一部分为一指针,指向下一个Node. class Node(): __slots__=['_item','_next'] #限定N
-
Python实现的数据结构与算法之链表详解
本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin
-
Python数据结构之翻转链表
翻转一个链表 样例:给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null 一种比较简单的方法是用"摘除法".就是先新建一个空节点,然后遍历整个链表,依次令遍历到的节点指向新建链表的头节点. 那样例来说,步骤是这样的: 1. 新建空节点:None 2. 1->None 3. 2->1->None 4. 3->2->1->None 代码就非常简单了: """
-
Python 数据结构之旋转链表
题目描述:给定一个链表,旋转链表,使得每个节点向右移动k个位置,其中k是一个非负数 样例:给出链表1->2->3->4->5->null和k=2:返回4->5->1->2->3->null 首先,观察一下这个题目要达到的目的,其实,换一种说法,可以这样来描述:给出一个k值,将链表从倒数第k个节点处起之后的部分移动到链表前面,就样例来说,其实是将4->5这一部分移动到整个链表前面,变成4->5->1->2->3->
-
使用python实现链表操作
一.概念梳理 链表是计算机科学里面应用应用最广泛的数据结构之一.它是最简单的数据结构之一,同时也是比较高阶的数据结构(例如棧.环形缓冲和队列) 简单的说,一个列表就是单数据通过索引集合在一起.在C里面这叫做指针.比方说,一个数据元素可以由地址元素,地理元素.路由信息活着交易细节等等组成.但是链表里面的元素类型都是一样的,是一种特殊的列表. 一个单独的列表元素叫做一个节点.这些节点不像数组一样都按顺序存储在内存当中,相反,你可以通过一个节点指向另外一个节点的指针在内存不同的地方找到这些元素.列表最
-
python实现从尾到头打印单链表操作示例
本文实例讲述了python实现从尾到头打印单链表操作.分享给大家供大家参考,具体如下: # coding=utf-8 class SingleNode: def __init__(self, item): self.item = item self.next = None class SingleLinkedList: """ is_empty() 链表是否为空 print_end_to_head() 从尾到头打印单链表 append(item) 链表尾部添加元素 "
-
python如何对链表操作
链表 链表(linked list)是由一组被称为结点的数据元素组成的数据结构,每个结点都包含结点本身的信息和指向下一个结点的地址. 由于每个结点都包含了可以链接起来的地址信息,所以用一个变量就能够访问整个结点序列. 也就是说,结点包含两部分信息:一部分用于存储数据元素的值,称为信息域:另一部分用于存储下一个数据元素地址的指针,称为指针域.链表中的第一个结点的地址存储在一个单独的结点中,称为头结点或首结点.链表中的最后一个结点没有后继元素,其指针域为空. 代码 class Node(): '创建
-
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
-
Python 实现链表实例代码
Python 实现链表实例代码 前言 算法和数据结构是一个亘古不变的话题,作为一个程序员,掌握常用的数据结构实现是非常非常的有必要的. 实现清单 实现链表,本质上和语言是无关的.但是灵活度却和实现它的语言密切相关.今天用Python来实现一下,包含如下操作: ['addNode(self, data)'] ['append(self, value)'] ['prepend(self, value)'] ['insert(self, index, value)'] ['delNode(self,
-
python数据结构链表之单向链表(实例讲解)
单向链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域elem用来存放具体的数据. 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点. 节点实现 class Node(object): """单链表的结点""" def __i
-
python单向链表的基本实现与使用方法【定义、遍历、添加、删除、查找等】
本文实例讲述了python单向链表的基本实现与使用方法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- #! python3 class Node(): def __init__(self,item): #初始化这个节点,值和下一个指向 self.item = item self.next = None class SingleLinklist(): def __init__(self): #初始化这个单链表的头指针为空 self._head = None def
-
Python单向链表和双向链表原理与用法实例详解
本文实例讲述了Python单向链表和双向链表原理与用法.分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大. 链表由一个个节点组成. 单向链表的节点分为两个部分:存储的对象和对下一个节点的引用.注意是指向下一个节点. 而双向链表区别于单向链表的是它是由三个部分组成:存储的对象.对下一个节点的引用.对上一个节点的引用,可以实现双向遍历. 单向列表的结构如下图: head是头节点,tail是尾节点,每个节点由Data存储对象和Next对下
-
python无序链表删除重复项的方法
题目描述: 给定一个没有排序的链表,去掉重复项,并保留原顺序 如: 1->3->1->5->5->7,去掉重复项后变为:1->3->5->7 方法: 顺序删除 递归删除 1.顺序删除 由于这种方法采用双重循环对链表进行遍历,因此,时间复杂度为O(n**2) 在遍历链表的过程中,使用了常数个额外的指针变量来保存当前遍历的结点,前驱结点和被删除的结点,所以空间复杂度为O(1) #!/usr/bin/env python3 # -*- coding: utf-8
-
Python双链表原理与实现方法详解
本文实例讲述了Python双链表原理与实现方法.分享给大家供大家参考,具体如下: Python实现双链表 文章目录 Python实现双链表 单链表与双链表比较 双链表的实现 定义链表节点 初始化双链表 判断链表是否为空 双链表尾部添加元素 双链表头部添加节点: 双链表表头删除 双链表按位置插入 双链表删除指定节点 完整代码 单链表与双链表比较 双链表比单链表多一个前驱指针位置,空间效率不占优势 由于双链表中的节点既可以向前也可以向后,相比单链表在查找方面效率更高(可使用二分法) 双链表的实现 定