Преобразование односвязного списка в двусвязный список

Я создал функцию односвязного списка, и мой профессор сказал, что для дополнительной оценки мы можем превратить ее в двусвязный список. Я прочитал несколько вещей, таких как добавление функции prev_node, такой как эта.

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)

Может ли кто-нибудь сказать мне (НЕ ДЕЛАТЬ ЭТО ДЛЯ МЕНЯ), что я должен сделать, чтобы изменить свой связанный список на дважды связанный список? Я знаю, что теперь мне нужно сослаться на хвост, а также на голову, но я совершенно не понимаю, как это сделать.


python data-structures doubly-linked-list singly-linked-list
person Cooper    schedule 04.03.2015    source источник
comment
Каждый раз, когда вы добавляете новый узел к tail, замените tail новым узлом. Каждый раз, когда вы вставляете в позицию 0, замените head новым узлом. Каждый раз, когда вы удаляете tail, замените tail на prev хвостового узла. Каждый раз, когда вы удаляете head, замените head на next головного узла.   -  person aruisdante    schedule 05.03.2015
comment
Обратите внимание, что односвязность или двусвязность фактически ничего не меняет в поведении связанного списка. Это просто меняет способ итерации; В односвязном списке вы можете выполнять итерацию только от головы к хвосту, в двусвязном списке вы можете выполнять итерацию в любом направлении. С технической точки зрения в обоих случаях было бы полезно хранить tail; это делает добавление к списку намного быстрее (хотя поддерживать актуальность tail в односвязном списке сложнее, поскольку вы не можете найти новый tail из старого, вам нужно перебирать весь список).   -  person aruisdante    schedule 05.03.2015
comment
В коде Rosetta есть реализации основных структур данных на многих языках. Определенно существует двусвязный список Python. Поиск этого может дать вам некоторые идеи.   -  person Paul Rooney    schedule 05.03.2015

Ответы (2)


arrow_upward
0
arrow_downward

Я не знаю 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))
person dfeuer    schedule 05.03.2015

arrow_upward
0
arrow_downward

Я знаю, что теперь мне нужно сослаться на хвост, а также на голову, но я совершенно не понимаю, как это сделать.

Отличный способ начать — написать на английском языке, что вы хотите сделать:

У меня есть связанный список, и мне нужно преобразовать его в двусвязный список. Для этого каждый узел должен отслеживать узлы prev и next, а моему списку нужны узлы head и tail. Когда я создаю список, head и tail должны указывать на один и тот же элемент. Когда я добавляю новый элемент в свой список, он должен стать последним узлом, его элемент .prev должен быть предыдущим .tail, и он также должен быть элементом .next для этого элемента.

Если у вас есть описание того, что вы хотите сделать, то будет относительно просто перевести его в код.

person Wayne Werner    schedule 05.03.2015