链表的知识总结

链式结构内存不连续的,而是一个个串起来的,每个链接表的节点保存一个指向下一个节点的指针。

⭐ 链式结构包含:node(节点)还有value(值),由于内存不连续的,那么对于数据的插入,只需找到一个节点便可以插入数据,这也是链表优于列表的一个优点,反之,对于数据的删除,由于不是连续的,不能通过索引删除数据,只能一一遍历删除元素。
 
⭐ 接下来上代码 单链表的增删功能
# 定义一个结点的类
class Node():
    def __init__(self,value=None,next=None):
        self.next = next
        self.value = value
    
    def __str__(self):
        return "Node:{}".format(self.value)

# 定义一个连接点的类
class Linklist():

    def __init__(self):
        self.root = Node()
        self.size = 0
        self.next = None  # 增加新数据时,将信数据的地址与谁关联

    # 只要是追加 就要创造节点
    def append(self,value):
        node = Node(value)
        # 判断root节点下面是否有数据
        if not self.next: # 如果没有节点
            self.root.next = node  # 将新节点挂在root后面
        else:
            self.next.next = node  # 将新节点挂在最后一个节点上  
        self.next = node # 重新赋值 一开始的是None
        self.size += 1
    
    def append_first(self,value):
        # 只要是追加 就要创造节点
        node = Node(value)
        # 判断root下面是否存在节点
        if not self.next:
            self.root.next = node
            self.next = node
        else:
            temp = self.root.next # 获取原来root后面的那个节点
            self.root.next = node #  将新节点挂在root后面
            node.next = temp # 新的节点的下一个节点是原来的root的节点
    
    # 迭代链表 
    def __iter__(self):
        # 获得root节点下面的数据
        current = self.root.next
        # 判断current是否有之 由于一开始赋予value和next没有值 所以进行判断 否则报错
        if current:
            # 判断时候有下一个节点 有的话则返回下一个结点的值
            while current is not self.next: # self.next可以列结成最后一个节点
                yield current
                current = current.next
            yield current
    
    # 查找数据
    def find(self,value):
        for n in self.__iter__():
            if n.value == value:
                return n
    
    # 查找出现的次数
    def find_count(self,value):
        count = 0
        for n in self.__iter__():
            if n.value == value:
                count += 1
        return count
    
    # 移除数据(链表的移除,需要逐一遍历,找到当前元素的节点,再删除)
    def remove(self,value):
        prve = self.root
        for n in self.__iter__():
            # 判断节点的值与要删除的值是否相等
            if n.value == value:
                # 查看是不是最后一个节点
                if n == self.next:
                    # 更新倒数第二节点的关系
                    prve.next = None
                    # 更新最后一个节点为原倒数第二个节点
                    self.next = prve
                prve.next = None
                # 删除当前节点
                del n 
                # 链表大小减少
                self.size -= 1
                return True
            prve = n
    
    def remove_all(self,value):
        prve =self.root
        for n in self.__iter__():
            if n.value == value:
                if n == self.next:
                    prve.next = None
                    self.next = prve
                prve.next = n.next
                # 删除当前节点
                del n 
                # 链表大小减少
                self.size -= 1
                return True
            prve = n

if __name__ == "__main__":
    link = Linklist()
    link.append("孙悟空")   
    link.append("猪八戒")   
    link.append("孙悟空")   
    link.append("猪八戒")   
    link.append("猪八戒")   
    link.append("唐僧")   
    link.append_first("唐僧")
    link.append_first("唐僧")
    # for v in link:
    #     print(v) 
    # print(link.find('孙悟空'))
    # print(link.find_count('唐僧'))  

    print("**************删除之前的数据******************")
    for v in link:
        print(v)
    link.remove('唐僧')
    link.remove('唐僧')
    link.remove('唐僧')
    link.remove('唐僧')
    link.remove('孙悟空')
    link.remove('猪八戒')

    link.remove_all("猪八戒")
    link.remove_all("孙悟空")
    link.remove_all("唐僧")     

    print("**************删除之后的数据******************")
    for v in link:
        print(v)        

链表的知识总结

 

 

 

 ⭐ 接下来上代码 双链表的增删功能:

# 定义一个结点的类
class Node():
    def __init__(self,value=None,node=None,next=None):
        self.value = value
        self.node = node
        self.next = next
    def __str__(self):
        return "Node:{}".format(self.value)
    
# 定义一个连接点的类
class DoubleLinkedList():
    def __init__(self):
        self.root = Node()
        self.size = 0
        self.end = None
    
    def append(self,value):
        node = Node(value)
        # 判断root节点下面是否有数据
        if not self.end: # 如果没有元素
            self.root.next = node  # 将root 的下一个节点 设置为新的node节点
            node.prev = self.root  # 设置新节点的 上一个节点 为 root
        else:
            self.end.next = node  # 将原来最后节点的下一个节点 设置为新的node节点
            node.prev = self.end # 设置新节点的 上一个节点 为 原来的最后一个节点
        self.end = node # 更新最后 一个节点新加的node节点
        self.size += 1
    
    def append_first(self,value):
        node = Node(value) # 封装节点对象
        # 判断是否已经有数据
        if not self.end:# 如果没有元素
            self.end = node # 更新最后 一个节点新加的node节点
        else:
            # temp指向node,node指向root,root指向temp
            temp = self.root.next # 保存原来的第一个节点
            node.next = temp # 设置新节的下一个节为原来的 第一个节点
            temp.prev = node # 更新原来的第一个节点的上一个节点位置为 新的node节点
        node.prev = self.root # 设置新节点的 上一个节点 为 root
        self.root.next = node # 将root 的下一个节点 设置为新的node节点
        self.size += 1

    # 正序循环
    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.end:
                yield current.value
                current = current.next
            yield current.value
    
    # 倒叙循环
    def revers_iter(self):
        current  = self.end #获取最后一节点
        if current:
            while current is not self.root:
                yield current
                current = current.prev

if __name__ == "__main__":
    link = DoubleLinkedList()
    link.append('孙悟空')
    link.append('猪八戒')
    link.append_first('唐三藏')

    for v in link:
        print(v)

    print('-'*30)

    for v in link.revers_iter():
        print(v)
    
          

链表的知识总结

 

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:链表的知识总结 - Python技术站

(0)
上一篇 2023年4月2日 下午5:14
下一篇 2023年4月2日 下午5:14

相关文章

  • Pandas简单操作(学习总结)

    Pandas 的主要数据结构是 Series (一维数据)与 DataFrame(二维数据),是一个提供高性能、易于使用的数据结构和数据分析工具。 接下来查看Pandas的基本使用:  ⭐ 文件的基本操作 # 导入模块 import pandas as pd import numpy as np   # 读取文件 stu = pd.read_excel(‘.…

    2023年4月2日
    00
  • Python 字符串的常用方法

    Python 包含6种数据类型,其中Number(数字)、String(字符串)、Tuple(元组)、 List(列表)、Dictionary(字典)、Set(集合); 这节主要讲字符串,它的本质是:字符序列。Python 的字符串是不可变的,我们无法对原字符串做任何修改。但可以将字符串的一部分复制到新创建的字符串,达到“看起来修改”的效果。Python 不…

    2023年4月2日
    00
  • 获取字典中values值中最大的数,返回对应的keys

    1.字典中键值对的获取 print(data.values()) # 查看字典的值 print(data.keys()) # 查看字典的key 2.对字典中的值进行排序 sorted(data.values()) sorted(data.values(),reverse=True) # 倒序 3.实操练习:获取字典中values值中最大的数,返回对应的key…

    2023年4月2日
    00
合作推广
合作推广
分享本页
返回顶部