Connect List(연결리스트)

일반적인 Array가 있다고 해봅시다.

 

일반적으로 Array의 순서는 메모리의 물리적인 순서와 동일합니다.

 

이때, Array 중간에 Element을 삽입하기 위해선

 

삽입된 위치 이후는 전부 이동을 해 줘야합니다.

 

추상화된 Array에서 새로운 Value의 삽입

연결리스트는 중간에 Element를 삽입할 때 발생하는 Memory의 읽기/쓰기를 최소화 하는 자료구조입니다.

 

추상화된 연결List

Node를 생성하고, 해당 Node의 Next Node를 Pointing 하게하는 자료구조 입니다.

 

위 이미지를 보면 알수있지만, 연결List의 순서는 Mem주소의 물리적인 순서와 무관합니다!

 

덕분에 연결List를 활용할 경우, Element의 삭제 & 추가에 따른 Memory 읽기/쓰기를 최소화 할 수 있습니다.

Connect List의 Element 추가, 삭제

추상화된 이미지를 보면, 마치 전화선 연결하는 것 처럼 서로의 연결을 바꿔줍니다.

 

때문에 해당 자료구조가 연결List라고 불리며, Element의 추가, 삭제가 다른 Element에 영향을 주지 않습니다.

 

하지만 Node가 Next Node만 연결되어 있기 때문에, 이미 지나간 Node를 찾을수가 없어보입니다.

 

이러한 문제점을 해결하기 위한 이중연결List, 원형연결List는 추후 다루도록 하겠습니다.

 

아래는 Python으로 구현된 Connect List 소스코드입니다.

import copy

#Element의 기본적인 Node 선언
class node:
    def __init__(self,node_value,next_node):
        self.value = node_value        
        self.next = next_node
        

class c_list:
    def __init__(self):
        #시작위치를 알기위한 Node
        self.inital_node = node("start",None)
            
    def add(self, element, index= None):
        start_node = self.inital_node
        #index가 없이 삽입되면 마지막 Node에 Element를 추가
        if index == None:
            while True:                     
                if start_node.next == None:                    
                    start_node.next = node(element, None)                    
                    break
                else:                    
                    start_node = start_node.next
        #해당 index위치까지 이동하여 Element를 추가하고, 연결을 고침
        elif index is not None:            
            for i in range(index):                                 
                if start_node.next == None:
                    return print("index is out of bound")
                else:
                    start_node = start_node.next
            start_node.next = node(element, start_node.next)
            
    def remove(self, index):
    	#해당 index이전의 node를 저장하고, 다음 Node를 받아
        #index이전의 Node와 index 다음 Node를 연결해줌
        start_node = self.inital_node                
        for i in range(index+1):
            if start_node.next == None:
                return print("index is out of bound")
            else:
                if i == index:                
                    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        
        print(node.value)
        if node.next == None:
            return print(-1)
        else:
            self.show(node.next)
        

import random
test = [2,6,4,7,0,5,8,1,9,3]

test_list = c_list()
for i in test:    
    test_list.add(i) 
  
test_list.show()
=> start 2 6 4 7 0 5 8 1 9 3

test_list.add(100, 1)

test_list.show()
=> start 2 100 6 4 7 0 5 8 1 9 3

test_list.remove(8)

test_list.show()
=> start 2 100 6 4 7 0 5 8 9 3