基于链表实现Python栈时，空栈调用pop方法抛出AttributeError问题求助

问题描述 #

我正在尝试用链表实现栈的pop函数，栈非空时运行正常，但空栈调用pop时会抛出错误：AttributeError: 'LinkedList' object has no attribute 'next'。调试发现第三次调用pop（栈为空时）触发这个错误，后续压入元素再pop又能正常工作。以下是我的代码和测试用例：

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)
    
    def push(self, new_element):
        """将新元素压入栈顶"""
        if self.ll is None:
            self.ll = new_element
        else:
            current = new_element
            current.next = self.ll
            self.ll = new_element
    
    def pop(self):
        """移除并返回栈顶的第一个元素"""
        if self.ll is None:
            return None
        else:
            popped = self.ll
            self.ll = self.ll.next
            return popped

# 测试用例
# 创建若干元素
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# 初始化栈
stack = Stack(e1)

# 测试栈功能
print stack.pop().value
print stack.pop().value
print stack.pop().value
print stack.pop()
stack.push(e4)
print stack.pop().value

错误原因分析 #

核心问题是你搞混了Stack类中self.ll的类型：

• self.ll是LinkedList实例，但你在push和pop里直接把它当作Element对象操作（比如访问self.ll.next），这完全违背了类的设计逻辑。
• 具体执行流程的bug：
  1. 初始化栈时，self.ll = LinkedList(e1)，此时self.ll.head是e1，self.ll本身是链表对象。
  2. 第一次push(e2)时，你错误地把self.ll（链表对象）赋值给current.next，然后把self.ll改成了e2（元素对象）——直接破坏了self.ll的类型！
  3. 前三次pop后，self.ll被改成None，第四次pop虽然返回了None，但后续push(e4)又把self.ll改成了元素对象，所以之后的pop看似正常，实则逻辑已经完全混乱。

解决方法 #

修正push和pop方法，正确操作LinkedList的head属性，而非直接修改self.ll本身：

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)
    
    def push(self, new_element):
        """将新元素压入栈顶"""
        # 新元素的next指向当前链表的头部
        new_element.next = self.ll.head
        # 更新链表头部为新元素，完成入栈
        self.ll.head = new_element
    
    def pop(self):
        """移除并返回栈顶的第一个元素"""
        if self.ll.head is None:
            return None
        else:
            popped = self.ll.head
            # 将链表头部移动到下一个元素，完成出栈
            self.ll.head = popped.next
            # 断开弹出元素的next引用（可选，但更规范，避免意外关联原链表）
            popped.next = None
            return popped

# 测试用例
# 创建若干元素
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# 初始化栈
stack = Stack(e1)

# 测试栈功能
stack.push(e2)
stack.push(e3)
print(stack.pop().value)  # 输出3
print(stack.pop().value)  # 输出2
print(stack.pop().value)  # 输出1
print(stack.pop())        # 输出None
stack.push(e4)
print(stack.pop().value)  # 输出4

关键修正点 #

• push方法：始终操作self.ll.head，让新元素成为链表的新头部，完全符合栈“后进先出”的特性。
• pop方法：判断self.ll.head是否为空，弹出时更新头部为下一个元素，同时断开弹出元素的next引用，避免潜在的引用问题。
• 修正后，栈的逻辑完全基于链表的头部操作，不会再出现类型混淆导致的错误。

内容的提问来源于stack exchange，提问作者German1212