创建n个节点的双向链表，并按相反顺序显示的Python程序

双向链表简单来说就是链表每个节点都是由前向后和后向前两个指针组成的数据结构，可以在O(1)的时间内访问前向节点和后向节点。Python中并没有内置的双向链表数据结构，我们需要自己实现。

更多Python相关文章，请阅读：Python 教程

双向链表Node类的定义

首先我们需要定义一个Node类来表示双向链表的节点，该类包含value、pre和next三个成员变量，分别表示节点的值、前向节点和后向节点。

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

双向链表DoublyLinkedList类的定义

然后我们需要定义一个DoublyLinkedList类来表示双向链表，该类包含head和tail两个成员变量，分别表示双向链表的起始节点和终止节点。

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

接下来我们需要实现几个双向链表的基本操作，包括节点插入、节点删除、链表反转等，详情见下面的代码。

双向链表的基本操作

节点插入

我们先实现节点插入的操作，该操作可以在任意位置插入一个新的节点：

    def insert(self, value, pos=None):
        node = Node(value)
        if not self.head:
            self.head = node
            self.tail = node
            return
        if pos is None:
            pos = self.tail
        if pos == self.head:
            node.next = self.head
            self.head.pre = node
            self.head = node
            return
        if pos == self.tail:
            node.pre = self.tail
            self.tail.next = node
            self.tail = node
            return
        node.pre = pos.pre
        node.next = pos
        pos.pre.next = node
        pos.pre = node
        return

这段代码的核心思想是根据参数pos的位置决定要插入的位置，然后分别处理节点的前向指针和后向指针。

节点删除

接下来我们实现一个节点删除的操作，该操作可以删除指定位置的节点：

    def delete(self, pos):
        if pos == self.head:
            self.head = pos.next
            pos.next.pre = None
            return
        if pos == self.tail:
            self.tail = pos.pre
            pos.pre.next = None
            return
        pos.pre.next = pos.next
        pos.next.pre = pos.pre
        return

这段代码的核心思想是先判断要删除的节点是否是起始节点或终止节点，然后分别处理与该节点相关的前向指针和后向指针。

链表反转

最后让我们来实现一个链表反转的操作，该操作可以将整个双向链表反转：

    def reverse(self):
        if not self.head:
            return
        cur = self.head
        self.tail = cur
        while cur:
            cur.pre, cur.next = cur.next, cur.pre
            cur = cur.pre
        self.head = self.tail
        self.tail = cur
        return

这段代码的核心思想是定义一个指针cur从链表的起始节点self.head开始遍历链表，然后不断交换cur的前向指针和后向指针即可将链表反转。

创建n个节点的双向链表并按相反顺序显示的示例程序

最后让我们来看一个完整的示例程序，该程序包含用于创建n个节点的双向链表的generateList函数和用于按相反顺序显示该链表的printList函数：

def generateList(n):
    dllist = DoublyLinkedList()
    for i in range(n):
        dllist.insert(i)
    return dllist

def printList(dllist):
    cur = dllist.tail
    while cur:
        print(cur.value)
        cur = cur.pre

dllist = generateList(5)
printList(dllist)
dllist.reverse()
printList(dllist)

这段代码先调用generateList函数生成一个包含5个节点的双向链表dllist，然后再调用printList函数按相反顺序输出该链表，最后再调用dllist的reverse方法将链表反转并再次调用printList函数按顺序输出该链表。