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)