자료구조

Linked List

객체로 표현된 노드(Node)가 서로 연결된 자료구조이며, 각 노드는 해당 노드의 data와 그 다음 노드의 레퍼러스가 담긴 next로 이루어짐

class Node:
	"""링크드 리스트 노드"""

    def __init__(self,data):
        self.data = data
        self.next = None

위와 같이 각각의 노드를 정의하는 클래스가 있다. 이제 생성된 노드들을 생성하기 위한 링크스 리스트 클래스를 생성한다.

class LinkedList:
	"""링크드 리스트 클래스"""
    
    def __init__(self):
    	self.head = None
        self.tail = None
    
    def find_node(self,data):
    	"""링크드 리스트 탐색 메소드"""
        
        iterator = self.head
        while iterator is not None:
            if iterator.data == data:
            	return iterator
            iterator = iterator.next
        return None
        	
    def append(self,data):
    	"""링크드 리스트 추가 메소드"""
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node  # 링크드 리스트가 비어 있는 경우
            self.tail = new_node
        else:
            self.tail.next = new_node
            self.tail = new_node
 
    def find_node_at(self, index):
    	"""링크드 리스트 접근 메소드(인덱스로 접근)"""
        iterator = self.head
        
        for _ in range(index):
            iterator = iterator.next
            
        return iterator
        
    def delete_after(self, previous_node):
    	"""링크드 리스트 삭제 메소드"""
        data = previous_node.next.data
        
        if previous_node.next is self.tail:
            previous_node.next = None
            self.tail = previous_node
        else:
            previous_node.next = previous_node.next.next
            
        return data
            
    def __str__(self):
    	"""링크드 리스트 문자열 표현""""
        
        _str = "|"
        iterator = self.head
        
        while iterator is not None:
            div_str += f" {iterator.data} |"
            iterator = iterator.next
        return _str

다음과 같이 링크드 리스트의 탐색, 삽입, 삭제 등의 기능을 구현할 수 있다.

링크드 리스트에서의 연산 메소드에 대한 시간 복잡도는 $O(n)$ 로 볼 수 있다. 원하는 노드에 접근하기까지 최대 n-1개의 노드를 거쳐야하기 때문에 $O(n)$ 의 시간이 소요되며 해당 노드를 찾아 연산을 실행하는데 $O(1)$이 소요되어 총 $O(n+1)$
즉, $O(n)$이 소요된다.

하지만 head와 tail에 직접 접근하는 경우에는 링크드 리스트의 속성값 self.head / self.tail 에 직접 접근할 수 있으므로 접근 및 연산에 $O(1+1)$의 시간이 소요된다.

Doubly Linked List

앞서 살펴본 링크드 리스트 기본형을 Singly Linked List 로 표현한다. 이에 추가로 previous node 에 대한 레퍼러스를 담고 있는 링크드 리스트 형태를 doubly linked list 라고 표현한다.

class Node:
	"""더블리 링크드 리스트 노드"""
    
    def __init__(self, data):
    	self.data = data
        self.next = None
        self.prev = None

class LinkedList:
	
    def __init__(self):
    	self.head = None
        self.tail = None
    
    def append(self, data):
    	"""더블리 링크드 리스트 추가 메소드"""
        
        new_node = Node(data)
        
        if self.head is None:
            self.head = new_node
            self.tail = new_node
            
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

싱글리 링크드 리스트와 전체적인 부분에서는 비슷하지만, 연산 메소드를 정의할 때 다소 차이가 발생한다. 위와 같이 추가 연산을 예로 들었을 때, 추가되는 노드의 prev 속성을 기존의 tail 노드에 이어주는 추가 작업이 필요하다. 삭제와 같은 기타 다른 연산 메소드도 마찬가지로 각 노드의 앞, 뒤 노드를 함께 고려해야 한다.

singly vs doubly

대부분의 연산에 대한 시간 복잡도는 두 자료구조 모두 큰 차이가 없다. 다만, tail 노드를 삭제할 때 차이가 발생한다. 싱글리 링크드 리스트는 tail 노드의 바로 앞 노드를 찾아 tail 노드로 바꿔주는 작업이 필요하다.
head 에서 부터 n-2번 노드를 지나쳐야하고 이 때 접근 및 삭제에 걸리는 시간은 $O(n)$이다.

반면, 더블리 링크드 리스트이 경우 연산을 원하는 해당 노드를 인자로 받기 때문에 바로 접근 및 삭제할 수 있어 $O(1+1)$의 시간이 소요된다.

따라서, tail 노드에 대한 삭제 연산이 잦은 경우에는 더블리 링크드 리스트를 사용하는 것이 효율적이다.
그러나 더블리 링크드 리스트는 prev 속성을 하나 더 갖기 때문에 약 2배의 추가적인 공간을 소요한다.