отсортированные для двусвязного Списка

Question

Я следующий 2 классов узлов и doublylinked списка

class DLLNode(object): 
    def __Init__ (self, data, prev_node=None, next_node=None): 
    self.data=data 
    self.prev_node=prev_node 
    self.next_node=next_node 

    def __str__(self): 
    return str(self.data) 

class DoublyLinkedList(object): 
    def __init__(self, head=None, tail=None): 
    self.head=head 
    self.tail=tail 
    self.size=0 

    def add_to_head(self, data): 
    newNode = DLLNode(data) 
    if self.head==None: 
     self.head=self.tail=newNode 
     self.head.prev_node=self.tail.next_node=None 
    else: 
     self.head.prev_node=newNode 
     newNode.next_node=self.head 
     self.head=newNode 

    def add_to_tail(self, data): 
    newNode=DLLNode(data) 
    if self.head==None: 
     self.head=self.tail=newNode 
     self.head.prev_node=self.tail.next_node=None 
    else: 
     self.tail.next_node=newNode 
     newNode.prev_node=self.tail 
     self.tail=newNode 
     self.tail.next_node=None 

    def remove_head(self): 
    node=self.head 
    if self.head==self.tail: 
     self.prev_node=self.next_node=self.head=self.tail=None 
     return 
    if self.head!=self.tail: 
     node=node.next_node 
     node.prev_node=None 
     self.head=node 

    def remove_tail(self): 
    node=self.tail 
    if self.head==self.tail: 
     self.prev_node=self.next_node=self.head=self.tail=None 
     return 
    if self.head!=self.tail: 
     self.tail=node.prev_node 
     self.tail.next_node=None 


    def index(self,element): 
    current = self.head 
    while current != None: 
     if current.data == element: 
     return current.position 
    else: 
     current = current.next 
     return -1 

Я хочу создать третий класс под названием SortedList, который является подклассом класса для DoublyLinkedList. Класс должен добавить и удалить, который добавляет и удаляет объект в список, и сохраняет список отсортированным. И «средний» метод для возврата среднего элемента списка. Не уверен, как я должен создать этот класс, немного смущенный.

Answer 1

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

Класс с двойным соединением, имеет только интерфейс с двойным завершенным очередью (dequeue), поэтому вхождение с текущими методами фактически невозможно, и вам нужно будет написать это самостоятельно.

Кроме того, расширение двусвязного списка не имеет особого смысла, поскольку методы add_to_head и add_to_tail не являются допустимыми для отсортированного списка, который должен допускать только одну «вставку» (возможно, называемую «add», name неважно), который мог бы положить что-то в голову или хвост, но мог бы поместить его куда угодно. Из-за этого вы можете рассмотреть другую иерархию наследования.

Наконец для отслеживающих среднего элемента, вы должны решить, что средний означает, что в контексте четной длиной списка, а затем, когда вы:

• вставить что-то до середины списка, вам может потребоваться изменить середину своего предшественника
• Вставить что-то после середины списка, вам может потребоваться изменить середину на ее преемника,
• удалить что-то до середины списка, вам может потребоваться изменить средний к нему преемник
• удалить что-нибудь после того, как в середине списка, возможно, потребуется изменить середину его предшественника
• удалить середину списка, то вам нужно будет установить середину либо его предшественника или преемника

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