python实现数据结构——链表 Python

class Node:
    """链表节点"""
    def __init__(self, data):
        self.data = data   # 数据域
        self.next = None   # 指针域，指向下一个节点

class LinkedList:
    """单向链表"""
    def __init__(self):
        self.head = None   # 头指针

    def is_empty(self):
        """判断链表是否为空"""
        return self.head is None

    def add_first(self, data):
        """在链表头部插入节点"""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def add_last(self, data):
        """在链表尾部插入节点"""
        new_node = Node(data)
        if self.is_empty():
            self.head = new_node
            return
        current = self.head
        while current.next:   # 找到最后一个节点
            current = current.next
        current.next = new_node

    def remove_first(self):
        """删除头节点并返回其数据"""
        if self.is_empty():
            raise IndexError("链表为空")
        removed_data = self.head.data
        self.head = self.head.next
        return removed_data

    def remove_last(self):
        """删除尾节点并返回其数据"""
        if self.is_empty():
            raise IndexError("链表为空")
        # 只有一个节点的情况
        if self.head.next is None:
            removed_data = self.head.data
            self.head = None
            return removed_data
        # 找到倒数第二个节点
        current = self.head
        while current.next.next:
            current = current.next
        removed_data = current.next.data
        current.next = None
        return removed_data

    def traverse(self):
        """遍历链表并打印所有数据"""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements) if elements else "空链表")

    def search(self, target):
        """查找链表中是否存在目标值"""
        current = self.head
        while current:
            if current.data == target:
                return True
            current = current.next
        return False

# 创建链表
ll = LinkedList()
print("初始链表：")
ll.traverse()          # 空链表

# 添加元素
ll.add_last(10)
ll.add_last(20)
ll.add_first(5)
ll.add_last(30)
print("添加元素后：")
ll.traverse()          # 5 -> 10 -> 20 -> 30

# 删除操作
print("删除头节点：", ll.remove_first())  # 5
print("删除尾节点：", ll.remove_last())   # 30
ll.traverse()          # 10 -> 20

# 查找
print("查找20：", ll.search(20))   # True
print("查找99：", ll.search(99))   # False