要定义一个单链表,首先定义链表元素:Element.它包含3个字段:
list:标识自己属于哪一个list
datum:改元素的value
next:下一个节点的位置
class LinkedList(object):
class Element(object):
def __init__(self,list,datum,next):
self._list = list
self._datum = datum
self._next = next
def getDatum(self):
return self._datum
datum = property(
fget = lambda self: self.getDatum())
def getNext(self):
return self._next
next = property(
fget = lambda self: self.getNext())
Element的构造函数很简单,只是用参数初始化新的节点.
接下来,我们定义LinkedList的初始化函数:
def __init__(self):
self._head = None
self._tail = None
这个函数初始化列表的头和尾元素.
另,我们也定义一个链表清空函数,用于将链表初始化为空链表:
def purge(self):
self._head = None
self._tail = None
我们为链表类定义3个属性:head,tail和isEmpty
,分别表示链表的头,尾和判断链表是否为空.
def getHead(self):
return self._head
head = property(
fget = lambda self: self.getHead())
def getTail(self):
return self._tail
tail = property(
fget = lambda self: self.getTail())
def IsEmpty(self):
return self._head == None
isEmpty = property(
fget = lambda self: self.IsEmpty())
我们为链表类再定义两个属性,first和last, 用于获得链表的头和尾元素的值.当链表为空时,抛出ContainerEmpty异常:
def getFirst(self):
if self._head is None:
raise ContainerEmpty
return self._head._datum
first = property(
fget = lambda self: self.getFirst())
def getLast(self):
if self._tail is None:
raise ContainerEmpty
return self._tail._datum
last = property(
fget = lambda self: self.getLast ())
prepend函数用于将元素插入链表头,这样,插入后的元素变成新的链表头:
def prepend(self,item):
tmp = self.Element (self,item,self._head)
if self._head is None:
self._tail = tmp
self._head = tmp
append函数用于给链表末尾添加元素.当链表为空时,添加的元素成为链表的头元素,然后,将元素添加到链表的尾部.
def append(self,item):
tmp = Element(self,item,None)
if self._head is None:
self._head = tmp
else:
self._tail._next = tmp
self._tail = tmp
给链表定义copy函数,它是 一个浅拷贝函数,首先建立一个空链表,然后逐个添加元素:
def __copy__(self):
lst = LinkedList()
ptr = self._head
while ptr is not None:
lst.append(ptr._datum)
ptr = ptr._next
return lst
定义链表的删除函数extract,用于删除链表中的特定元素.首先查找该元素的位置,如果不存在,提示KeyError异常.当元素是头元素时,将其下一个节点变为头元素;当其节点是尾元素时,将上一个节点变成尾元素.然后删除它.
def extract(self,item):
prePtr = ptr = self._head
while ptr is not None and ptr._datum is not item:
prePtr = ptr
ptr = ptr._next
if ptr is None:
raise KeyError
if ptr == self._head:
self._head = ptr._next
else:
prePtr._next = ptr._next
if ptr == self._tail:
self._tail = prePtr
find函数用于查找指定的元素,当没有找到时,返回None:
def find(self,item):
ptr = self._head
while ptr is not None and ptr._datum is not item:
ptr = ptr._next
return ptr
至此,一个简单的单链表就已经实现了,可以继续扩展它的功能.
分享到:
相关推荐
主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
主要给大家介绍了关于python实现单链表的相关资料,文中通过示例代码介绍的非常详细,对大家学习或者使用python具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
数组 问题:实现一个支持动态扩容的数组 问题:实现一个大小固定的有序数组,支持动态增删改操作 问题:实现两个有序数组合并为一个有序数组 ...资源中包括常用语言:c、java、python、go等实现源码,方便参考学习。
对于有一定基础或热衷于研究的人来说,可以在这些基础代码上进行修改和扩展,实现其他功能。 【沟通交流】: 有任何使用上的问题,欢迎随时与博主沟通,博主会及时解答。 鼓励下载和使用,并欢迎大家互相学习,共同...
单链表逆置是数据结构学习和...3. **源代码示例**:在CSDN技术社区和其他代码分享网站上,程序员们提供了大量C、C++、Java、Python等多种编程语言实现单链表逆置的源代码。这些代码资源能够帮助学习者直观理解算法流
AlgorithmWithLeetCode 本仓库主要记录自己的一个学习路径,同时刷题的过程中也会... :利用一个单链表来实现栈的数据结构。只针对栈顶元素进行操作,可借用单链表的头可以让所有栈的操作在O(1)的完成。 嘘……工作
给单链表加一js实现欢迎来到 100 天 介绍 这是伴随我决定进行 100 天编码挑战的 repo,在那里我学习和创造了很棒的东西,使用 Python、Javascript、C# 和 go。 让我们一起学习和创造很棒的东西。 内容 第 1/100 天:...
该代码由Amit Bansal在学习数据结构和算法时编写。 参考GFG,NPTEL,CLRS。 该存储库包含: 单链表。 添加两个数字表示的链表。 气泡在链接列表中排序合并在链接列表中排序合并排序链表反向使用或不使用堆栈的...
Java单链表源码分析学习指导 两个人策划了一份学习指南 数学 结石 线性代数 ( ) 概率与统计 () 麻省理工学院概率(数学,慢慢来,这对数学有好处)(视频): 一般(未分类) (, ) () ( ) () () - 需要免费注册 () ...
出于研究目的,我正在Python中实现数据结构和算法。 个人博客: : 算法 种类 图形 -SSC 未分类 贪心算法-背包问题 动态编程-背包问题 数据结构 单链表 双链表 堆 队列 循环队列 圆形双端队列 堆 特里
各种算法和数据结构的实现已经通过动画幻灯片进行了演示和实现。 它涵盖了许多关于算法和数据结构的面试室问题。 问题和解决方案由- 动画幻灯片。 (为了使算法可视化更快) IDE 上的编码算法。 该课程涵盖以下主题 ...
添加 Python 代码,学习极客时间的数据结构与算法之美课程的笔记和代码,以及 python 代码实现的 leetcode 题目。 已完成课程: , , C++ 2016-12 记录 学习数据结构和算法时的一些练习代码。 有关算法性能的基本...
学习结构体排序查找以及链表的使用#include #include #include struct student { int num; double score; char name[100]; struct student *next; }; int cmp(const void *a,const void *b) { struct student *...
这样的一大好处是,读者可以边看书,边实现自己的代码,然后提交到网站上验证自己的想法是否正确。AlgoHub的使命是成为最好的算法学习和交流平台。AlgoHub囊括了 POJ, ZOJ, leetcode, HackerRank 等网站的经典题目...