Python实现环形链表

Python实现环形链表完整攻略

在Python中实现环形链表，可以使用节点嵌套的方式来表示链表。具体实现方式为，定义一个Node类，包含val和next属性，其中next属性指向下一个节点。为了实现环形链表，只需将最后一个节点的next属性指向头节点即可。

下面是在Python中实现环形链表的完整示例代码：

class Node():
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

class CircularLinkedList():
    def __init__(self):
        self.head = Node()
        self.head.next = self.head  # 将head节点的next属性指向自身

    def is_empty(self):
        return self.head.next == self.head

    def add(self, item):
        new_node = Node(item)
        new_node.next = self.head.next
        self.head.next = new_node

    def remove(self, item):
        cur_node = self.head
        while cur_node.next != self.head:
            if cur_node.next.val == item:
                cur_node.next = cur_node.next.next
                break
            cur_node = cur_node.next

    def search(self, item):
        cur_node = self.head
        while cur_node.next != self.head:
            if cur_node.next.val == item:
                return True
            cur_node = cur_node.next
        return False

    def __len__(self):
        length = 0
        cur_node = self.head
        while cur_node.next != self.head:
            length += 1
            cur_node = cur_node.next
        return length

    def append(self, item):
        new_node = Node(item)
        if self.is_empty():
            self.head.next = new_node
        else:
            cur_node = self.head
            while cur_node.next != self.head:
                cur_node = cur_node.next
            cur_node.next = new_node
        new_node.next = self.head

    def insert(self, pos, item):
        if pos <= 0:
            self.add(item)
        elif pos > len(self) - 1:
            self.append(item)
        else:
            new_node = Node(item)
            cur_node = self.head
            for i in range(pos):
                cur_node = cur_node.next
            new_node.next = cur_node.next
            cur_node.next = new_node

    def display(self):
        cur_node = self.head
        while cur_node.next != self.head:
            print(cur_node.next.val, end=' ')
            cur_node = cur_node.next
        print()

以上代码中，我们构建了一个CircularLinkedList类。其中，Node类表示一个链表节点，包含数值和指向下一个节点的next属性。CircularLinkedList类中定义了多种链表操作方法，包括判断链表是否为空、添加节点、删除节点、搜索节点等。

另外，我们通过判断cur_node.next是否等于self.head来确定是否到达了环形链表的末尾。

下面是一个简单的示例，演示如何创建一个环形链表，并对其进行插入、删除、遍历等操作：

# 示例1：创建环形链表并操作
cll = CircularLinkedList()

# 添加
cll.add(1)
cll.add(2)
cll.add(3)
cll.display()  # output: 3 2 1

# 删除
cll.remove(2)
cll.display()  # output: 3 1

# 遍历
cll.add(4)
cll.display()  # output: 4 3 1

# 插入
cll.insert(1, 5)
cll.display()  # output: 4 5 3 1

另外，我们可以套用Python自带的unittest模块，对线性链表的功能进行测试。下面是一个示例：

# 示例2：使用unittest测试
import unittest

class TestCircularLinkedList(unittest.TestCase):
    def test_append(self):
        cll = CircularLinkedList()
        cll.append(1)
        self.assertEqual(cll.is_empty(), False)
        self.assertEqual(len(cll), 1)

        cll.append(2)
        self.assertEqual(len(cll), 2)

        cll.append(3)
        self.assertEqual(len(cll), 3)

    def test_insert(self):
        cll = CircularLinkedList()
        cll.insert(0, 2)
        self.assertEqual(cll.is_empty(), False)
        self.assertEqual(len(cll), 1)

        cll.insert(0, 1)
        cll.insert(2, 3)
        cll.insert(1, 4)
        self.assertEqual(len(cll), 4)

    def test_remove(self):
        cll = CircularLinkedList()
        cll.remove(1)
        self.assertEqual(cll.is_empty(), True)
        self.assertEqual(len(cll), 0)

        cll.append(1)
        cll.append(2)
        cll.append(3)
        cll.remove(2)
        self.assertEqual(len(cll), 2)
        self.assertEqual(cll.search(2), False)

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

以上示例中，我们使用unittest模块，对线性链表的append、insert、remove方法进行了测试，并验证其是否符合预期。