双向链表插入节点并输出 - Python 代码示例

双向链表插入节点并输出 - Python 代码示例

本示例演示了如何使用 Python 实现一个带头结点的双向链表，以及如何插入节点并输出正反向链表元素。

代码:

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

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(None)
        self.tail = Node(None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def insert(self, pos, data):
        if pos < 1 or pos > self.length() + 1:
            return 'error'

        new_node = Node(data)
        curr = self.head
        for i in range(pos):
            curr = curr.next

        new_node.prev = curr.prev
        new_node.next = curr
        curr.prev.next = new_node
        curr.prev = new_node

    def length(self):
        curr = self.head.next
        count = 0
        while curr != self.tail:
            curr = curr.next
            count += 1
        return count

    def forward_output(self):
        curr = self.head.next
        output = ''
        while curr != self.tail:
            output += str(curr.data) + ' '
            curr = curr.next
        return output.strip()

    def backward_output(self):
        curr = self.tail.prev
        output = ''
        while curr != self.head:
            output += str(curr.data) + ' '
            curr = curr.prev
        return output.strip()

n = int(input())
nums = list(map(int, input().split()))
pos, e = map(int, input().split())

dll = DoublyLinkedList()
for num in nums:
    dll.insert(dll.length() + 1, num)
dll.insert(pos, e)

print(dll.forward_output())
print(dll.backward_output())

代码解析:

1. Node 类: 每个节点包含数据 (data)、前驱指针 (prev) 和后继指针 (next)。
2. DoublyLinkedList 类:
   • 初始化时创建头结点 (head) 和尾结点 (tail)，并将它们链接起来。
   • insert(pos, data) 方法: 插入节点到指定位置。
   • length() 方法: 返回链表长度。
   • forward_output() 方法: 从头结点开始顺向输出链表元素。
   • backward_output() 方法: 从尾结点开始逆向输出链表元素。

运行示例:

输入:

5
-4 5 2 7 0
2 100

输出:

-4 100 5 2 7 0
0 7 2 5 100 -4

说明:

1. 首先输入链表的长度 (N)。
2. 接着输入 N 个整数，用来创建初始链表。
3. 最后输入插入位置 (pos) 和插入元素的值 (e)。

代码的关键:

• 使用 prev 和 next 指针实现双向链表的连接。
• 插入节点时，需要更新前后节点的指针指向。
• 遍历链表时，可以使用 curr.next 和 curr.prev 指针来访问前后节点。

总结:

本示例演示了如何使用 Python 实现双向链表并进行插入节点操作。通过学习本示例，您可以更好地理解双向链表的数据结构，以及如何用代码实现相关操作。