链表的知识总结

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

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