01-链式结构

在前文提到的线性结构中，存在中间插入数据不方便的现象，因此为了解决这个问题，提出了链式结构。链式结构分为单链式结构和双链式结构。

单链式结构
双链式结构

1. 什么是链式结构

链式结构是为了解决线性结构中间插入数据速度不友好而提出的解决方法，对初始化的数据添加next属性，使得它指向下一个节点，这样需要添加数据或者删除数据（完全删除，非重置为None）只需要将链式结构打断并重新连接即可实现。不过需要牺牲线性结构的快速查询性能。

• 单链式结构
  • 单链式结构解决了插入数据和完全删除数据问题，查找数据则需要进行遍历查找。但是因为单链式结构只有next一个属性，因此无法逆序遍历。
• 双链式结构
  • 双链式结构根据单链式结构无法逆序而添加新的属性，prev属性，指向它的上一个节点，实现了数据的逆序遍历。

2. 链式结构的优缺点

• 优点
  • 链式结构可以快速插入数据
• 缺点
  • 查找某一个数据或者说显示某一个数据需要进行遍历查找

3. 代码

3.1 单链式结构

class Node():
    def __init__(self, value=None, next=None):
        self.value = value
        self.next = next
    
    # 用于显示
    def __str__(self):
        return self.value


class LinkedList():
    def __init__(self):
        # 初始化root节点为空，不进行展示
        self.root = Node()
        self.size = 0  # 记录有多少元素
        self.next = None  # 增加新数据时，将新数据的地址与谁关联

    def append(self, value):
        node = Node(value)
        # 判断是否已经有数据
        if not self.next:  # 如果没有节点时
            self.root.next = node  # 将新节点挂到root后面
        else:
            self.next.next = node  # 将新节点挂到最后一个节点上
        # 同时要将添加的数据设置为最后一个节点
        self.next = node
        self.size += 1

    def append_first(self, value):
        node = Node(value)
        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后的节点
        self.size += 1

    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.next:
                yield current
                current = current.next
            yield current

    # 查找数据需要进行遍历整个链式表
    def find(self, value):
        for data in self.__iter__():
            if data.value == value:
                return data

    def find_count(self, value):
        count = 0
        for data in self.__iter__():
            if data.value == value:
                count += 1
        return count

    def remove(self, value):
        prev = self.root
        for data in self.__iter__():
            # 判断节点的值与要删除的值是否相等
            if data.value == value:
                # 查看是不是最后一个节点
                if data == self.next:
                    # 更新倒数第二节点的关系
                    prev.next = None
                    # 更新最后一个节点为原倒数第二个节点
                    self.next = prev
                prev.next = data.next
                del data
                self.size -= 1
                return True
            prev = data

    def remove_all(self, value):
        prev = self.root
        for data in self.__iter__():
            if data.value == value:
                if data == self.next:
                    prev.next = None
                    self.next = prev
                prev.next = data.next
                del data
                self.size -= 1
                continue
            prev = data

3.2 双链式结构

class Node():
    def __init__(self, value=None, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next

    def __str__(self):
        return self.value


class DoubleLinkedList():
    def __init__(self):
        self.root = Node()
        self.size = 0
        self.end = None

    def append(self, value):
        node = Node(value)  # 封装节点对象
        # 判断是否已经有数据
        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 = 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
                current = current.next
            yield current

    def revers_iter(self):
        current = self.end  # 获取最后一节点
        if current:
            while current is not self.root:
                yield current
                current = current.prev