Как я могу сделать этот отдельно связанный список в двусвязный список?

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 класса (you should use CamelCase for class names):

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

Для двунаправленного списка вы должны иметь, каждый узел должен иметь ссылку на предыдущий узел. Это означает, что вам нужно будет изменить методы добавления и удаления, чтобы также назначить эту ссылку.