Неортодоксальный связанный список в python

Question

Как часть моего A-Level Cirriculum я стал свидетелем программы для создания связанного списка с возможностью добавления и удаления узлов.

К сожалению, моя экзаменационная комиссия продиктовала это заданным образом. c неортодоксальный путь. Они хотят, чтобы узлы были объектами с двумя атрибутами (data и Pointer), хранящимися в стандартном списке.

Невероятно важно, чтобы это было сделано таким образом, поскольку экзаменационная комиссия не принимает другие методы: (

Это метод конструктора для узла, который я должен использовать

class ListNode:
    def __init__(self) :
        self.data = int()
        self.pointer = -1 

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

Может ли кто-нибудь помочь мне с рабочим решением, любая помощь очень ценится.

РЕДАКТИРОВАТЬ: Как и предполагалось, я публикую свою лучшую текущую попытку.

Пока у меня есть инициализация и добавление вниз (я думаю), но мне нужна помощь с удалением. Я также думаю, мне может понадобиться добавить мой код добавления для удаления на работу. Хотя я и не знал, как go держать указатели на правильных узлах после удаления.

Инициализация:

def initialiselist():
    List = [Node() for i in range(10)]
    startpointer = nullpointer
    freelistptr = 0

    for index in range(9):
        List[index].pointer = index + 1
    List[9].pointer = nullpointer

    for i in List:
        print(i.data, i.pointer)
    return List, startpointer, freelistptr

Добавление узлов:

def insertnode(List, startpointer, freelistptr, newdata):
    if startpointer == -1:                      #If list is empty
        List[freelistptr].data = newdata
        startpointer = freelistptr
        freelistptr = List[startpointer].pointer
        List[startpointer].pointer = -1
        return(List,startpointer,freelistptr)

    for i in List:
        if i.data == newdata:        
            print("You cannot have duplicate data")
            return(List,startpointer,freelistptr)

    if freelistptr == -1:
        print("The list is full")
        return(List,startpointer,freelistptr)

    elif freelistptr != -1:         #If Lis is not empty
        List[freelistptr].data = newdata

        if List[startpointer].data > newdata:             #If the new data is less than the startpointer 
            temp = List[freelistptr].pointer
            List[freelistptr].pointer = startpointer                    
            startpointer = freelistptr                                  
            freelistptr = temp
            return(List,startpointer,freelistptr)

        else:                                               #If the new data is greater than the startpointer

            if List[startpointer].pointer == -1:                            
                List[startpointer].pointer = freelistptr                
                temp = freelistptr                                      
                freelistptr = List[freelistptr].pointer             
                List[temp].pointer = -1
                return(List,startpointer,freelistptr)

            nextnodeptr = List[startpointer].pointer                        
            previousnodeptr = startpointer
            newnodeptr = freelistptr
            temp2 = List[freelistptr].pointer

            while True:
                if List[nextnodeptr].pointer == -1:
                    if List[nextnodeptr].data > newdata:
                        List[newnodeptr].pointer = nextnodeptr
                        List[previousnodeptr].pointer = newnodeptr
                        break
                    elif List[nextnodeptr].data < newdata:
                        List[nextnodeptr].pointer = newnodeptr
                        temp2 = List[freelistptr].pointer
                        List[newnodeptr].pointer = -1
                        break
                if List[nextnodeptr].data > newdata:
                    temp2 = List[freelistptr].pointer
                    List[newnodeptr].pointer = nextnodeptr
                    List[previousnodeptr].pointer = newnodeptr
                    break   
                else:
                    previousnodeptr = nextnodeptr
                    nextnodeptr = List[nextnodeptr].pointer

            freelistptr = temp2   
            return (List,startpointer,freelistptr)    

Я знаю, что это просто полная стена текста, но я не привык здесь публиковать сообщения, так что извините.

Мой вопрос: как сделать я удаляю узлы?

Answer 1

Если я правильно понимаю требование «неортодоксальности», базовая структура узлов должна быть стандартным списком. Это будет означать, что ваш класс узла должен быть подклассом list без каких-либо собственных атрибутов.

Вот как я мог бы подойти к этому:

class ListNode(list):

    @property
    def pointer(self): return (self[1:] or [None])[0]
    @pointer.setter
    def pointer(self,node): self[:] = [self.data,node]

    @property
    def data(self): return self[0] if self else None
    @data.setter
    def data(self,value): self[:1] = [value]

    def addNode(self,node): # to end of chain
        if self.pointer: self.pointer.addNode(node)
        else:            self.pointer = node

    def append(self,value):
        self.addNode(ListNode([value]))

    def insertNode(self,node): # before this node
        if self.pointer: node.addNode(self.pointer)        
        self.data,node.data       = node.data,self.data
        self.pointer,node.pointer = node,self.pointer

    def find(self,value):
        if self.data == value: return self
        if self.pointer: return self.pointer.find(value)

    def deleteNode(self,node): # needs to start from a previous node
        if self.pointer is node: self.pointer = node.pointer
        else:                    self.pointer.deleteNode(node)

    def __repr__(self):
        return f"{self.data}" + (f" --> {self.pointer}" if self.pointer else "")

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

использование:

head  = ListNode([0])
head.append(1)
head.append(2)
head.append(3)

print(head)
# 0 --> 1 --> 2 --> 3

node2 = head.find(2)
node4 = ListNode([4])
node2.insertNode(node4)

print(head)
# 0 --> 1 --> 4 --> 2 --> 3

node2 = head.find(2)
head.deleteNode(node2)

print(head)
# 0 --> 1 --> 4 --> 3