链式结构

内存空间不在需要连续

n : next 存储的是下一个值的地址

t: 上一个值的地址

v: 值的数值存储

有n有t,是双向链表结构

只有n,是单向链表结构

在头部加数据, O(1)

删除任意一个元素的时候,n2指向v3即可,效率也很高.

如果查看v2元素是什么时候,效率就不高了,只能从第一个往下找.

代码模拟链表

# 节点对象,value和next
class Node:
    def __init__(self, value=None, next_=None):
        self.value = value
        self.next_ = next_

    def __str__(self):
        return f"Node: {self.value}"


# 链式结构
class LinkedList:
    def __init__(self):
        # 初始化根节点,根节点无数据,每次遍历都是从这里去观察,
        # 不管是在链表前 还是后加数据,都是在root.next_后面
        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的next_为node
        else:
            self.end.next_ = node  # 已经有数据,指定下一个节点的next_为node
        self.end = node
        self.size += 1

    def append_first(self, value):
        node = Node(value)

        if not self.end:  # 没有节点的时候
            self.root.next_ = node
            self.end = node
        else:  # 有节点的时候
            t = self.root.next_  # 原来root后面的节点.第一个节点
            self.root.next_ = node  # 设置新的第一个节点
            node.next_ = t  # 新的第一个节点 -> 原来的第一个节点
        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 find(self, value):
        for n in self:
            if n.value == value:
                return f"{n} {id(n)}"

    def count(self, value):
        c = 0
        for n in self:
            if n.value == value:
                c += 1
        return c

    def remove(self, value):
        # 上一个节点
        prev = self.root
        for n in self:
            if n.value == value:
                # 上一个节点 -> 链接 下一个节点

                if n == self.end:
                    prev.next_ = None
                    self.end = prev
                else:
                    prev.next_ = n.next_
                del n
                self.size -= 1
                return True

            # 更新上一个节点
            prev = n

    def remove_all(self, value):
        # 上一个节点
        prev = self.root
        for n in self:
            if n.value == value:
                # 上一个节点 -> 链接下一个节点
                if n == self.end:
                    prev.next_ = None
                    self.end = prev
                else:
                    prev.next_ = n.next_
                del n
                self.size -= 1
                continue
            # 更新上一个节点
            prev = n


if __name__ == '__main__':
    link = LinkedList()
    link.append("孙悟空")
    link.append("猪八戒1")
    link.append("猪八戒1")
    link.append("猪八戒")
    for v in link:
        print(v)

    link.remove_all("猪八戒1")
    print("--------------")
    for v in link:
        print(v)