将单链表更改为双向链表

Question

我创建了一个单链表函数，我的教授说，为了获得额外的学分，我们可以将其更改为双链表。我读了一些东西，比如添加一个prev_节点函数，比如这样。

class ListNode(object):

    def __init__(self, item = None, prev = None, link = None):

        '''creates a ListNode with the specified data value and link
        post: creates a ListNode with the specified data value and link'''

        self.item = item
        self.prev = prev
        self.link = link

然而，我不知道从那里去哪里。我知道我需要像这里一样加上一个尾巴和一个脑袋。

from DoublyListNode import ListNode

class LinkedList(object):

    #--------------------------------------------------------------

    def __init__(self, seq=()):

        """ Pre: Creates a Linked List
        Post: Creates a list containing the items in the seq=()"""

        if seq == ():

            # If there is no items to be put into the list, then it creates an empty one.
            self.head = None
            self.tail = None

        else:

            # Creates a node for the first item.
            self.head = ListNode(seq[0], None)

            # If there are remaining items, then they're added while keeping track of the last node.
            last = self.head
            for item in seq[1:]:
                last.link = ListNode(item, None)
                last = last.link

        self.size = len(seq)

谁能告诉我，（不要为我做这件事），我必须做什么才能把我的链接列表变成一个双重链接列表？我知道我现在必须参考尾巴和头部，但我对如何做到这一点很困惑。

Answer 1

我知道我现在必须参考尾巴和头部，但我对如何做到这一点很困惑。

一个很好的开始方法是用英语写下你想做什么：

我有一个链表，我需要将其转换为双链表。为此，每个节点都需要跟踪prev和next，而我的列表需要head和tail节点。创建列表时，head和tail应指向同一项。当我向列表中添加一个新项目时，它应该成为最后一个节点，即它的。prev元素应该是前一个。尾部，它应该是。下一个项目也适用于该项目。

一旦你对你想做的事情有了描述，那么将其翻译成代码应该相对简单。

Answer 2

我不懂Python，但在Haskell中有一种方法可以做到：

import qualified Data.Vector as V
import Data.Vector (Vector, (!), fromList)

data DLL a = DLL {prevP :: Maybe (DLL a),
                  val :: a,
                  nextP :: Maybe (DLL a)}

list2DLL :: [a]->DLL a
list2DLL = vec2DLL . fromList

prev :: Int -> Maybe Int
prev i | i <= 0 = Nothing
prev i = Just (i-1)

next :: Int -> Int -> Maybe Int
next i lim | i < lim-1 = Just(i+1)
next _ _ = Nothing

vec2DLL :: Vector a -> DLL a
vec2DLL v = scaffold ! 0 where
  scaffold = V.mapWithIndex go v
  go i a = DLL (fmap (scaffold!) $ prev i)
               a
               (fmap (scaffold!) $ next i (length v))