python实现链表（单链，双链）

# code:utf-8
# createTime:2023.8.17

# -----------------------------------------------------------------------------
class Node:
    """
    节点类，每个数据就是一个节点，
    包含一个数据位和一个指针位，
    指针指向下一个数据的内存地址
    """
    def __init__(self, data=None):
        # 数据位
        self.data = data
        # 指针位
        self.next = None

    # 输出节点的值
    def __str__(self):
        return str(self.data)

# -----------------------------------------------------------------------------
# 为链表定义的错误类型 ---所需删除元素未找到
class DeleteNotFindError(Exception):
    def __init__(self, message):
        super().__init__(message)



# -----------------------------------------------------------------------------

class Link:
    """单向链表"""

    def __init__(self):
        self.head = None    # 头指针
        self.END = None     # 尾指针
        self._size = 0      # 链表大小的计数变量

    # function -> 追加数据
    def append(self, data)->None:

        # 初始化一个节点
        node = Node(data = data)

        # 判断链表是否为空，如果链表不为空
        if self.END:
            self.END.next = node    # 将指针指向下一个位置
            self.END = node         # 将数据存入内存

        # 如果链表为空
        else:
            self.head = node    # 头指针指向第一个数据
            self.END = node     # 尾指针指向第一个数据

        # 计数变量的自增
        self._size += 1

    # function -> 获取链表大小
    def getsize(self)->int:
        return int(self._size)

    # 返回生成器
    def __iter__(self):
        insert = self.head          # 获取头指针

        # 判断下一个内存地址是否存在
        while insert:
            val = insert.data       # 获取内存地址处存放的数据
            insert = insert.next    # 将指针指向下一个地址
            yield val               # 使用生成器yield返回数据

    # function -> 删除节点
    def delete(self, data):
        # 此处采用双指针模式进行查找

        insert = self.head          # 前指针，指向查找元素的前一位
        end = self.head             # 后指针，指向查找元素

        # 顺着链表查下去，时间复杂度位 O(n),如果后指针有值
        while end:

            # 如果值相等
            if end.data == data:

                # 如果需查找元素在开头
                if end == self.head:
                    self.head = self.head.next  # 直接修改头指针的指向
                else:
                    insert.next = end.next      # 将前指针的指向修改为后指针的下一位

                self._size -= 1                 # 计数变量自减

                # 利用return结束循环
                return

            # 双指针依次指向所有节点，知道查找到
            insert = end
            end = end.next

        else:
            # 输出错误提示
            raise DeleteNotFindError(f"Not find {data} in Link")

    # function -> 搜索节点
    def find(self, data)->bool:

        # 这里直接套用iter方法
        for i in self.__iter__():

            # 找到节点
            if i == data:
                return True     # 返回True

        else:
            return False        # 未找到节点返回False

    # function -> 清空链表
    def clear(self):
        """clear the entire Linklist"""
        self.head = None
        self.END = None
        self._size = 0

# -----------------------------------------------------------------------------

class Nodes(object):

    def __init__(self, data=None, next=None, prev=None):
        self.data = data        # 节点数据
        self.next = next        # 下一节点指针
        self.prev = prev        # 上一节点指针

# -----------------------------------------------------------------------------

class DoubleLink(object):

    def __init__(self):
        self.head = None        # 头节点
        self.end = None         # 尾节点
        self._size = 0          # 计数

    # function -> 添加元素
    def append(self, data):
        nodes = Nodes(data, None, None)
        if self.head is None:
            self.head = nodes
            self.end = self.head
        else:
            nodes.prev = self.end
            self.end.next = nodes
            self.end = nodes
            self._size += 1

    # function -> 删除元素
    def delete(self, data):
        # 删除元素分为四种不同的情况，这里要进行分类讨论
        # 第一种，链表为空
        current = self.head
        if current is None:
            # 输出错误提示
            raise DeleteNotFindError(f"Not find {data} in DoubleLink")
        # 第二种，要删除的节点位于链表头部
        elif current.data == data:
            self.head = current.next
            self.head.prev = None
            self._size -= 1

        elif self.end.data == data:
            self.end = self.end.prev
            self.end.next = None
            self._size -= 1
        else:
            while current:
                if current.data == data:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                    self._size -= 1
                    return

                current = current.next
            else:
                raise DeleteNotFindError(f"Not find {data} in DoubleLink")

    # function -> 获取链表节点数
    def getsize(self):
        return int(self._size)

    # 返回生成器
    def __iter__(self):
        insert = self.head          # 获取头指针

        # 判断下一个内存地址是否存在
        while insert:
            val = insert.data       # 获取内存地址处存放的数据
            insert = insert.next    # 将指针指向下一个地址
            yield val               # 使用生成器yield返回数据

说明：Node是单向链表的节点类，Nodes则是双向节点类

使用实例：

from main import *  # 导入链表代码所在文件

# 单链表
test = Link()
for i in range(1,10):
    test.append(i)
for i in test:
    print(i)

print("__________________________")
# 双链表
test = DoubleLink()
for i in range(1,10):
    test.append(i)

test.delete(5)
for i in test:
    print(i)

结果：

1
2
3
4
5
6
7
8
9
__________________________
1
2
3
4
6
7
8
9