我怎样才能把这个单链表变成一个双向链表

Question

>我在Python中创建了一个链表，它是单链接的。 这工作得很好，但我想实现它，以便它是双重链接的，但我很难弄清楚如何做到这一点。

# node class
class node:
    def __init__(self):
        self.data = None # contains the data
        self.next = None # contains the reference to the next node
# linked list class
class linked_list:
    def __init__(self):
        self.cur_node = None
    def add_node(self, data):
        new_node = node() # create a new node
        new_node.data = data
        new_node.next = self.cur_node # link the new node to the 'previous' node.
        self.cur_node = new_node # set the current node to the new one.
    def list_print(self):
        node = self.cur_node # cant point to ll!
        while node:
            print(node.data)
            node = node.next

我知道我需要向节点类添加self.previous，并且我认为我需要向linked list构造函数和add_node函数添加一些东西，但我不确定从哪里开始。

我

实际上不需要在程序中使用此功能，我只是想了解如何在较低级别实现链表。

Answer 1

与其说

这是一个编码问题，不如说是一个概念问题。您需要弄清楚您希望代码的行为方式。实现所需的行为(在这种情况下(一点也不困难。

假设我们想要这些行为：

# construction
dlist = DoublyLinkedList()
# access to head and tail nodes
dlist.head  # should return the head node
dlist.tail  # should return the tail node
dlist.head.prev is None  # should be True
dlist.tail.next is None  # should be True 
# adding nodes at both ends
dlist.add_head()
dlist.add_tail()
# iteration in both directions
for node in dlist:
    # do something to the node
for node in reversed(dlist):
    # do something to the node

当你写出这样的所需行为时，你也会准备好一些测试代码。

现在让我们从修改Node类开始(你应该使用 CamelCase 作为类名(：

class Node:
    def __init__(self, data=None, prev=None, next=None):
        self.data = data
        self.prev = prev
        self.next = next
    def __repr__(self):
        return '<{}, {}>'.format(self.data, self.next)

我们添加prev因为这显然是必需的。但是，我们还通过data和next作为参数来改进您的原始版本，因此您可以在创建节点时设置这些值。拥有__repr__总是很好的，如果不是为了其他任何事情，也可以进行调试。

现在是列表本身。关键是，(a(而不是一个cur_node，你需要列表中的两个句柄，我一直称之为head和tail，以及(b(添加节点时，第一个节点是一个特殊情况，我们必须对head和tail进行更改。

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
    def __repr__(self):
        return '<DoublyLinkedList {}>'.format(self.head)
    def add_head(self, data=None):
        if self.head is None:
            self.head = self.tail = Node(data)  # the very fist node
        else:
            new_head = Node(data=data, next=self.head)  # prev is None
            self.head.prev = self.head = new_head
    def add_tail(self, data=None):
        if self.tail is None:
            self.head = self.tail = Node(data)  # the very first node
        else:
            new_tail = Node(data=data, prev=self.tail)  # next is None
            self.tail.next = self.tail = new_tail
    # implements iteration from head to tail
    def __iter__(self):
        current = self.head
        while current is not None:
            yield current
            current= current.next
    # implements iteration from tail to head
    def __reversed__(self):
        current = self.tail
        while current  is not None:
            yield current
            current = current.prev

让我们测试一下

>>> dlist = DoublyLinkedList()
>>> print(dlist)
<DoublyLinkedList None>
>>> dlist.add_head(1)
>>> dlist.add_tail(2)
>>> dlist.add_tail(3)
>>> dlist.add_head(0)
>>> print(dlist)  # __repr__ is such a nice thing to have
<DoublyLinkedList <0, <1, <2, <3, None>>>>>
>>> print(dlist.head)
<0, <1, <2, <3, None>>>>
>>> print(dlist.tail)
<3, None>
>>> print(dlist.head.prev is None, dlist.tail.next is None)
True, True
>>> print(dlist.tail.prev.next is dlist.tail)
True
>>> [node.data for node in dlist]
[0, 1, 2, 3]
>>> for node in reversed(dlist):
...     print(node.data, node)
3 <3, None>
2 <2, <3, None>>
1 <1, <2, <3, None>>>
0 <0, <1, <2, <3, None>>>>

Answer 2

对于双向链表，您应该拥有，每个节点都应该具有对前一个节点的引用。 这意味着您需要修改添加和删除方法以分配此引用。