Doubly Linked List - Python

생성일: 2021년 11월 3일 오후 8:46

double.py

class NodeType:
    """ Node Type """
    def __init__(self, item):
        self.info = item
        self.next = None
        self.back = None

class DoublyLL:
    def __init__(self):
        self.head = NodeType('head')
    
    def find_item(self, item):
        '''[1]'''
        moreToSearch = True  
        location = self.head.next
        found = False
        while(moreToSearch and not found):
            if(item < location.info):
                moreToSearch = False
            elif (item == location.info):
                found = True
            else:
                location = location.next
                moreToSearch = (location != None)
        return location

    
    def insert_item(self, item, new):
        '''[2]'''
        newNode = NodeType(new)
        if(self.head.next != None):
            location = self.find_item(item)
            if(location.info > new):
                newNode.back = location.back
                newNode.next = location
                location.back.next = newNode
                location.back = newNode
            else:
                newNode.back = location
                location.next = newNode
                newNode.next = None
        else:
            self.head.next = newNode
            newNode.back = self.head
            newNode.next = None

    def delete_item(self, item):

        '''[3]'''
        location = self.find_item(item)
        if(location.next != None):
            location.back.next = location.next
            location.next.back = location.back
        else:
            location.back.next = None
        del location
        
            
    def __str__(self):
        cur_node = self.head
        items = []
        while cur_node is not None:
            items.append("(" + str(cur_node.info) + ")\n")
            cur_node = cur_node.next
        return "".join(items)

testdouble.py

from double import *

if __name__ == '__main__':

    doubly = DoublyLL()
    
    doubly.insert_item('head', '1')
    doubly.insert_item('1', '2')
    
    doubly.insert_item('2', '3')
    doubly.insert_item('3', '4')
    
    print(doubly)
    doubly.delete_item('2')
    doubly.delete_item('3')
    print(doubly)