百木园-与人分享,
就是让自己快乐。

链表的知识总结

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

⭐ 链式结构包含: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)
    
          

 


来源:https://www.cnblogs.com/lxxduang/p/16562327.html
本站部分图文来源于网络,如有侵权请联系删除。

未经允许不得转载:百木园 » 链表的知识总结

相关推荐

  • 暂无文章