Connect List 응용(원형, 이중)

연결List에 대해서 포스팅하면서, 단일연결List는 Next Index의 접근은 용이하지만, 이전 Index로 가는것은 어렵다고 했습니다.

 

이러한 문제점을 개선하기 위해서 고안된 개선된 Connect List중 원형연결 List, 이중연결 List가 있습니다.

 

추상화된 원형 연결 List와 이중 연결 List

1. 원형연결 List

기존 단일연결list의 마지막 Index의 Node는 항상 Next Node가 Null값을 갖게 됩니다.

 

이때 Data의 여부를 Search할 경우, 지속적으로 "Next Node가 Null인가?" 를 검사하게 됩니다.

 

하지만 마지막 Index의 Node를 첫번째 Index Node를 Pointing 하게 함 으로써 프로그램의 성능 향상을 도모할 수 있습니다.

 

파이썬으로 구현된 원형 연결 List입니다.

class node:
    def __init__(self,node_value,next_node):
        self.value = node_value        
        self.next = next_node
        

class cirular_c_list:
    def __init__(self):
        self.inital_node = node("start",None)        
            
    def add(self, element, index= None):
        start_node = self.inital_node.next        
        #마지막 Node일 경우 None이 아니라 inital Node의 Next Node를 Pointing함
        if index == None:
            while True:                     
                if start_node == None:                    
                    temp = node(element, None)
                    self.inital_node.next = temp
                    temp.next = self.inital_node.next
                    break
                elif start_node.next == self.inital_node.next:                    
                    start_node.next = node(element, self.inital_node.next)                                   
                    break
                else:                    
                    start_node = start_node.next
        elif index is not None:            
            for i in range(index-1):                                 
                start_node = start_node.next
            start_node.next = node(element, start_node.next)
            
    def remove(self, index):
        start_node = self.inital_node.next
        for i in range(index):
            if start_node.next == self.inital_node.next:
                return print("index is out of bound")
            else:
                if i == index-1:                
                    temp = start_node                                
                    start_node = start_node.next                
                else:
                    start_node = start_node.next
        temp.next = start_node.next        
            

    def show(self, node=888):
        if node == 888:
            node = self.inital_node.next  
        print(node.value)
        if node.next == self.inital_node.next:
            return print(-1)
        else:
            self.show(node.next)
        

test = [9,7,8,1,3,6,8]

test_list = cirular_c_list()

for i in test:    
    test_list.add(i)        

test_list.show()
=>9,7,8,1,3,6,8,-1

test_list.add(100, 1)

test_list.show()
=>9,100,7,8,1,3,6,8,-1

test_list.remove(6)

test_list.show()
=>9,100,7,8,1,3,8,-1

2. 이중연결 List

이중연결 List는 각 Element의 Node를 확장하여,

 

Next Node 이외에 이전 Last Node를 가르기는 항목은 추가한 연결List입니다.

 

이렇게되면 어떤 Node에 있던지 이전 Node에 대한 접근이 용이하고, 원형연결List의 장점을 모두 가질 수 있습니다(마지막 Node에서 원형연결List의 개념 추가)

 

파이썬으로 구현된 이중 연결 List입니다.

#node를 확장해서 last node pointing을 추가
class node:
    def __init__(self,last_node,node_value,next_node):
        self.last = last_node
        self.value = node_value        
        self.next = next_node        
        

class double_c_list:
    def __init__(self):
        self.inital_node = node(None,"start",None)        
            
    def add(self, element, index= None):
        start_node = self.inital_node.next
        #inital_node의 next는 index 0, last는 마지막 index를 Pointing
        if index == None:
            while True:                     
                if start_node == None:                    
                    temp = node(start_node,element, self.inital_node)
                    self.inital_node.next = temp
                    self.inital_node.last = temp
                    break
                elif start_node.next == self.inital_node:                    
                    start_node.next = node(start_node, element, self.inital_node)
                    break
                else:                    
                    start_node = start_node.next
        elif index is not None:            
            for i in range(index-1):                                 
                start_node = start_node.next
            start_node.next = node(start_node,element, start_node.next)
            
    #node를 제거할 때 last를 이용하기 때문에 이전 Node 저장 불필요
    def remove(self, index):
        start_node = self.inital_node.next
        for i in range(index):
            if start_node.next == self.inital_node.next:
                return print("index is out of bound")
            else:                
                start_node = start_node.next
        start_node.last.next = start_node.next
        start_node.next.last = start_node.last
            

    def show(self, node=888):
        if node == 888:
            node = self.inital_node.next  
        print(node.value)
        if node.next == self.inital_node:
            return print(-1)
        else:
            self.show(node.next)

test = [9,6,1,2,7,5,6]

test_list = double_c_list()
for i in test:    
    test_list.add(i)        

test_list.show()
=>9,6,1,2,7,5,6,-1

test_list.add(100, 1)

test_list.show()
=>9,100,6,1,2,7,5,6,-1

test_list.remove(6)

test_list.show()
=>9,100,6,1,2,7,6,-1