Python Demo of string reverse by LinkList

 #2020.09.29 by JK ,  #DoubleLinkList

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

#1. stack , FILO ,表現 放入 > 拿出 後 => 自然反轉  : 沒有多餘搬移.

#2. 插入動作只需變動兩個指標OBJECT 3次置換 , :沒有多餘搬移.

class Node:

    def __init__(self, data):

        self.data = data

        self.nextNode = None

        self.prevNode = None

class doubly_linked_list:

    

    def __init__(self):

        self.head =Node(None)    #當下操作指標(Node)移到 NewNode上

    

    def push(self, NewVal):

        NewNode = Node(NewVal)

        NewNode.nextNode = self.head    #NewNode next -> 虛擬端點 

        self.head.prevNode=NewNode      #虛擬端點  pre -> NewNode  

        #if self.head is not None:

        #    self.head.prevNode = NewNode

        #---move---

        self.head = NewNode             #當下操作指標(Node)移到 NewNode上

    

    

    def insert(self, NewVal , PreN):

        PreNode=self.findpreNode( (PreN-1) )

        NewNode = Node(NewVal)

        

        NewNode.nextNode=PreNode.nextNode

        NewNode.prevNode=PreNode

        PreNode.nextNode=NewNode

 

        self.head=self.findTOP(self.head) # 操作指標移動到TOP

    def findTOP(self , Node):

   

        while self.head.prevNode is not None:

            self.head= self.head.prevNode

        return self.head

    

    def POPStack(self ):

        out=[]

        while (self.head.nextNode is not None):

            out.append(self.head.data)

            #print(self.head.data)

            self.head= self.head.nextNode

        return out

    

    def findpreNode(self,N ):

        for i in range(0, N):

            self.head=self.head.nextNode

        return self.head

#--------

def str_Reverse(input_str):

    dllist = doubly_linked_list()   

    for m in input_str:

        dllist.push(m)

    

    

    #-----Demo 插入--

    dllist.insert(NewVal=99 , PreN=4)

    

    str_reverse=dllist.POPStack()

    return str_reverse

if __name__ == '__main__':

    input_str=[1,2,3,4,5]

    print('input=',input_str)

    str_reverse=str_Reverse(input_str)

    print( 'output',str_reverse)