Python 算法.3

云深之无迹 2021-04-13


单向链表

单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域。这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值。

  • 表元素域elem用来存放具体的数据。

  • 链接域next用来存放下一个节点的位置(python中的标识)

  • 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点。

实现其中以一个子单元,节点

先init

判空

列表长度得计算,就是对节点得数量进行统计

对节点得数据进行打印

class SingleLinkList(object): """单链表"""
def __init__(self): self._head = None
# 一开始得初始化过程,C中是指针,py里面没有这个概念 # 所以将_heade赋值为None,其实就是空指针得意思 # 至于标识符前面有下划线,一是属于一种具体得实现,所以私有化,用户解除不到,然后就是避免同名冲突
def is_empty(self): """判断链表是否为空""" return self._head == None # 直接就是去判断头节点得赋值情况
def length(self): """链表长度""" # cur初始时指向头节点 cur = self._head count = 0 # 尾节点指向None,当未到达尾部时 while cur != None: count += 1 # 将cur后移一个节点 cur = cur.next return count # 就是顺着结点往下运行,到一个,计数变量+1,在此之前按计数变量会先赋值为0 # 这个结构一定是用循环结构了,这个循环结构用了头节点得赋值情况来运行 # 最后用return返回我们需要得信息
def travel(self): """遍历链表""" cur = self._head # 首先读取节点得标识 while cur != None: # 继续使用循环来判断吧 print(cur.item, cur=cur.next) # 前面是具体得数据元素,后面通过不停得高兴节点得信息来进行打印 print("")

头部添加元素

实现,我们来具体得聊聊如何实现他

这个也该放这里


  1. 对于我们得插入这样得行为,其实就是考虑我们得一个数据得小单位该如何得插入大得数据单元里面,而且对在头部插入又最为头麻。

  2. 首先就是我们要生成一个待插入得节点

  3. 因为一开始我们得链表是完整得,就是有头节点得,那我们在头插入就是要取代这个东西

  4. 注意得是,对于一个链表得节点来讲,其结构就是指针加数据段

  5. 所以我们就要把我们待加入得节点得指针域,取代原有得指针

  6. 具体看代码,从我们得node里面获取next得信息,然后赋值给_head得变量,完成头节点得更新动作

  7. 接着完成整体得插入行为,注意是从左往右看


我们继续分析一个,就是尾端得插入。

比较简单,但是需要知道得一点是需要判断后面得这个元素是不是在一个新得空表内部进行了添加


评论
热门推荐
相关推荐
X
广告
我要评论
0
0
点击右上角,分享到朋友圈 我知道啦
请使用浏览器分享功能 我知道啦