在 python 中创建链表而不使用本机列表

Question

我正在尝试在 python 中实现一个没有本机列表的动态单链表。不幸的是，这批代码的单元测试结果失败了。 Pycharm 没有标记任何语法错误，我不知道我的代码的哪些部分是错误的。

import unittest

class linked_list:

    front = rear = None
    current = None #used in iterator

    class node:

        def __init__(self, value, next):
            self.value = value
            self.next = next

    def empty(self):
        return self.empty

    def push_front(self, value):
        x = self.node(value, self.front)
        self.front = x
        if not self.rear:
            self.rear = x
        return x

    def push_back(self, value):
        if self.empty():
            self.front = self.rear = self.node(value, None)
        else:
            x = self.node(value, None)
            self.rear.next = x
            self.rear = x
        x = self.node(value, self.rear)
        self.rear = x
        return x

    def pop_front(self):
        if self.empty():
            raise RuntimeError("Empty List")
        x = self.front.value
        self.front = self.front.next
        if not self.front:
            self.rear = None
        return x

    def pop_back(self, value, next):
        if self.empty():
            raise RuntimeError("Empty List")
        y = self.rear.value
        x = self.front
        while x.next != self.rear:
            x = x.next
        self.rear = x
        return y

链表单元测试：

class test_linked_list (unittest.TestCase):
    def test_none(self):
        self.assertTrue(linked_list().empty())
    def test_pop_front_empty(self):
        self.assertRaises(RuntimeError, lambda: linked_list().pop_front())
    def test_pop_back_empty(self):
        self.assertRaises(RuntimeError, lambda: linked_list().pop_back())
    def test_push_back_pop_front(self):
        ll = linked_list()
        ll.push_back(1)
        ll.push_back(2)
        ll.push_back(3)
        self.assertFalse(ll.empty())
        self.assertEquals(ll.pop_front(), 1)
        self.assertEquals(ll.pop_front(), 2)
        self.assertEquals(ll.pop_front(), 3)
        self.assertTrue(ll.empty())
    def test_push_front_pop_front(self):
        ll = linked_list()
        ll.push_front(1)
        ll.push_front(2)
        ll.push_front(3)
        self.assertEquals(ll.pop_front(), 3)
        self.assertEquals(ll.pop_front(), 2)
        self.assertEquals(ll.pop_front(), 1)
        self.assertTrue(ll.empty())
    def test_push_front_pop_back(self):
        ll = linked_list()
        ll.push_front(1)
        ll.push_front(2)
        ll.push_front(3)
        self.assertFalse(ll.empty())
        self.assertEquals(ll.pop_back(), 1)
        self.assertEquals(ll.pop_back(), 2)
        self.assertEquals(ll.pop_back(), 3)
        self.assertTrue(ll.empty())
    def test_push_back_pop_back(self):
        ll = linked_list()
        ll.push_back(1)
        ll.push_back("foo")
        ll.push_back([3,2,1])
        self.assertFalse(ll.empty())
        self.assertEquals(ll.pop_back(),[3,2,1])
        self.assertEquals(ll.pop_back(), "foo")
        self.assertEquals(ll.pop_back(), 1)
        self.assertTrue(ll.empty())

编辑：

下面是来自调试器的Errors/Failures：

Failure Traceback (most recent call last): File "G:\CS2_Assignment1\Assignment 1.py", line 101, in test_push_back_pop_back self.assertFalse(ll.empty()) AssertionError: > is not false

Failure Traceback (most recent call last): File "G:\CS2_Assignment1\Assignment 1.py", line 72, in test_push_back_pop_front self.assertFalse(ll.empty()) AssertionError: > is not false

Failure Traceback (most recent call last): File "G:\CS2_Assignment1\Assignment 1.py", line 91, in test_push_front_pop_back self.assertFalse(ll.empty()) AssertionError: > is not false

Answer 1

首先，您的 linked_list class 需要一个 __init__ 方法。其次，你有一个名为 empty 的方法，所以你不应该有一个同名的变量。所以：

class linked_list:
    def __init__(self):  
        self.front = self.rear = None
        self.current = None #used in iterator
        self._empty = True

    def empty(self):
        return self._empty

Answer 2

像这样的测试先行的方法是编写好的代码的好方法。 unittest 告诉你错误在哪里。如果您不能通过目视检查修复它们，那么您可以构建临时示例脚本，用于在调试器中单步执行代码或打印以查看发生了什么。

我使用 unittest.main() 到运行并遇到了几个错误。一个是：TypeError: pop_back() missing 2 required positional arguments: 'value' and 'next' 果然，该方法的参数太多 def pop_back(self, value, next):。所以我只是删除了它们。

经过其余的，通过单元测试的脚本是：

import unittest

class linked_list:

    front = rear = None
    current = None #used in iterator

    class node:

        __slots__ = ['value', 'next']

        def __init__(self, value, next):
            self.value = value
            self.next = next

    def empty(self):
        return not self.front

    def push_front(self, value):
        x = self.node(value, self.front)
        self.front = x
        if not self.rear:
            self.rear = x

    def push_back(self, value):
        if self.empty():
            self.front = self.rear = self.node(value, None)
        else:
            x = self.node(value, None)
            self.rear.next = x
            self.rear = x

    def pop_front(self):
        if self.empty():
            raise RuntimeError("Empty List")
        x = self.front.value
        self.front = self.front.next
        if not self.front:
            self.rear = None
        return x

    def pop_back(self):
        if self.empty():
            raise RuntimeError("Empty List")
        y = self.rear.value
        if not self.front.next:
            self.front = self.rear = None
        else:
            x = self.front
            while x.next is not self.rear:
                x = x.next
            x.next = None
            self.rear = x
        return y


class test_linked_list (unittest.TestCase):
    def test_none(self):
        self.assertTrue(linked_list().empty())
    def test_pop_front_empty(self):
        self.assertRaises(RuntimeError, lambda: linked_list().pop_front())
    def test_pop_back_empty(self):
        self.assertRaises(RuntimeError, lambda: linked_list().pop_back())
    def test_push_back_pop_front(self):
        ll = linked_list()
        ll.push_back(1)
        ll.push_back(2)
        ll.push_back(3)
        self.assertFalse(ll.empty())
        self.assertEquals(ll.pop_front(), 1)
        self.assertEquals(ll.pop_front(), 2)
        self.assertEquals(ll.pop_front(), 3)
        self.assertTrue(ll.empty())
    def test_push_front_pop_front(self):
        ll = linked_list()
        ll.push_front(1)
        ll.push_front(2)
        ll.push_front(3)
        self.assertEquals(ll.pop_front(), 3)
        self.assertEquals(ll.pop_front(), 2)
        self.assertEquals(ll.pop_front(), 1)
        self.assertTrue(ll.empty())
    def test_push_front_pop_back(self):
        ll = linked_list()
        ll.push_front(1)
        ll.push_front(2)
        ll.push_front(3)
        self.assertFalse(ll.empty())
        self.assertEquals(ll.pop_back(), 1)
        self.assertEquals(ll.pop_back(), 2)
        self.assertEquals(ll.pop_back(), 3)
        self.assertTrue(ll.empty())
    def test_push_back_pop_back(self):
        ll = linked_list()
        ll.push_back(1)
        ll.push_back("foo")
        ll.push_back([3,2,1])
        self.assertFalse(ll.empty())
        self.assertEquals(ll.pop_back(),[3,2,1])
        self.assertEquals(ll.pop_back(), "foo")
        self.assertEquals(ll.pop_back(), 1)
        self.assertTrue(ll.empty())

if __name__ == '__main__':
    unittest.main()

Answer 3

部分错误已被他人指出；例如，正如@tdelaney 所说，self.empty() returns 本身，它是一种方法并且始终计算为 True。

但我认为整体设计还可以改进，也许展示不同的实现会对您有所帮助（好吧，我希望如此！）。所以我们开始吧。

首先，我们单独来一个Nodeclass。（像你那样嵌入它是可以的，但是 "flat is better than nested"。）此外 __repr__ 使调试更容易并且通常是用户友好的事情。

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

    def __repr__(self):
        type_name = type(self).__name__
        return '{}({!r}, {!r})'.format(type_name, self.value, self.next)

然后是 LinkedList 本身。除了你定义的API，如果实现迭代器协议就好了，所以我们可以做for x in llist。此外，列表的空（或缺少）听起来像一个属性并且很容易计算，所以让我们通过使用 property 使其像属性一样可访问。而且，按照单向链表的想法，我不保留对最后一个节点的引用。

class LinkedList:

    def __init__(self):
        self.head = None
        self._current = None  # for iteration

    def __repr__(self):
        return '<{} {}>'.format(type(self).__name__, self.head)

    def __iter__(self):
       self._current = self.head
       return self

    def __next__(self):
        if self._current is None:
            raise StopIteration
        current, self._current = self._current, self._current.next
        return current

    @property
    def is_empty(self):
        return self.head is None

    def push_front(self, value):
        self.head = Node(value, self.head)

    def push_back(self, value):
        last_node = self._find_last()
        if last_node is None:
            # list is empty, so push_front is the same as push_back
            self.push_front(value)
        else:
            last_node.next = Node(value, None)

    def pop_front(self):
        if self.is_empty:
            raise RuntimeError('list empty')
        value, self.head = self.head.value, self.head.next
        return value

    def pop_back(self):
        last_node = self._find_last()
        if last_node is None:
            raise RuntimeError('list empty')
        if last_node is self.head:
            self.head = None
        else:
            # at least two nodes left; need to find the penultimate node
            for node in self:
                if node.next is last_node:
                    node.next = None
        return last_node.value

    def _find_last(self):
        # Helper method for finding the last node
        last_node = None
        for node in self:
            last_node = node
        return last_node

我对这个实现进行了文档测试，它通过了：

>>> llist = LinkedList()
>>> llist.is_empty
True
>>> llist.push_front(1)
>>> llist.is_empty
False
>>> llist.push_front(0)
>>> llist.push_back(2)
>>> llist.push_back(3)
>>> llist
<LinkedList Node(0, Node(1, Node(2, Node(3, None))))>
>>> for node in llist:
...     print(node.value)
0
1
2
3
>>> llist.pop_front()
0
>>> llist
<LinkedList Node(1, Node(2, Node(3, None)))>
>>> llist.pop_back()
3
>>> llist
<LinkedList Node(1, Node(2, None))>

虽然不完美，因为我选择了一个非常简单的 _find_last 实现。它需要 for 循环来产生节点，而不是人们可能期望的它们的值，并且在大多数情况下它会强制每个 pop_back() 调用在列表上迭代两次。但我想现在它已经足够好了。

在 python 中创建链表而不使用本机列表

Creating linked-list in python without using native lists

python

linked-list

python-unittest