Python data structure 2-2

연결 리스트

Definition

연결리스트(linked list)는 값(value)과 다음 노드(node)에 대한 포인터가 포함된 노드로 이루어진 선형 리스트이다.
밑의 사진처럼 마지막 노드는 null값(None)을 가지고 있으나 연결 리스트의 구현 방법에 따라
마지막 노드의 포인터가 첫 노드를 가르킬 경우 원형 연결 리스트(Circle linked list)
인접한 두 노드가 서로로 연결될 경우 이중 연결 리스트(Doubly linked list)라고 한다.

Node

class Node:
    
    def __init__(self, value = None, pointer = None) -> None:
        self.value   = value
        self.pointer = pointer
    
    def set_current_node_value(self, value) -> None:
        self.value = value
    
    def set_current_node_pointer(self, new_pointer):
        self.pointer = new_pointer
    
    def go_next(self):
        return self.pointer

먼저 Node class 만을 활용해 Linked list를 구현해보았다.

head_node   = Node()
first_node  = Node(1, head_node)

이렇게 instance를 만들어 활용할 수 있다. pointer에는 다음 Node의 인스턴스를 지정해줌으로써 node간 연결(linked)이 되는 구조이다. 이제 Node class 안에 선언해준 method를 이용해 다음 node를 연결해보면 다음과 같이 코드를 짤 수 있다.

head_node   = Node()
first_node  = Node()
second_node = Node()
# Node instance created

first_node.set_current_node_value(1)
head_node.set_current_node_pointer(first_node)
# first_node에 value 선언 및 head_node과 연결

second_node.set_current_node_value(3)
first_node.set_current_node_pointer(second_node)
# second_node에 value 선언 및 first_node와 연결

이런식으로 node 하나에는 value(값)과 다음 노드를 가르키는 pointer가 함께 있으며 첫 node는 None(null)에 연결되어있는 형태를 Linked list라고 한다.
그렇기 때문에 head_node에서 pointer를 참조해 second_node의 value를 참조할 수 있으며

print(head_node.pointer.pointer.value)
print(first_node.pointer.value)
print(second_node.value)

세개의 print 결과는 모두 3임을 알 수 있다.
추가적으로 이렇게 마지막 노드를 다시 head 노드와 연결해준 형태를 원형 연결 리스트(circle linked list)라고 한다.

last_node = Node()
last_node.set_current_node_value(5)
last_node.set_current_node_pointer(head_node)

FILO type Linked List

선입 후출 타입의 연결 리스트를 구현해보았다.

class Node:
    
    def __init__(self, value = None, pointer = None) -> None:
        self.value   = value
        self.pointer = pointer
    
    def __repr__(self) -> str:
        return repr([self.value, self.pointer])

class SingleLinkedList:
    
    def __init__(self, maxsize : int = 0) -> None:
        self.maxsize = maxsize
        self.head    = None
        self.length  = 0
    
    def _print_list(self):
        
        node = self.head
        while node:
            print([node.value, node.pointer], end = ", ")
            node = node.pointer
        print()
    
    def _add(self, value):
        self.head = Node(value, self.head)
        
        self.length += 1
        
        if self.length > self.maxsize:
            raise Full
    
    def _find(self, index : int) -> dict:
        prev = None
        node = self.head
        i = 0
        while node and i < index:
            prev = node
            node = node.pointer
            i += 1
        
        print(f"index of {i} is {node.value}")
        return {
            "node"  : node,
            "index" : i,
            "prev"  : prev,
            }
    
    def _find_by_value(self, value) -> dict:
        prev  = None
        node  = self.head
        found = False
        i     = 0
        while node and not found:
            if node.value == value:
                found = True
            else:
                prev = node
                node = node.pointer
            i += 1
        
        if found:
            print(f"{value} in index of {i} node")
            return {
                "node"  : node,
                "index" : i,
                "prev"  : prev,
                }
        else:
            print(f"{value} NotFound")
    
    def _delete(self, prev : Node, node : Node) -> None:
        if not prev:
            self.head = node.pointer
        else:
            prev.pointer = node.pointer
        
        self.length -= 1
    
    def _delete_node(self, index : int) -> None:
        _find_result = self._find(index)
        
        if index == _find_result["index"]:
            print(f'{_find_result["node"].value} is deleted')
            self._delete(_find_result["prev"], _find_result["node"])
    
    def _delete_node_by_value(self, value) -> None:
        _find_result = self._find_by_value(value)
        
        if _find_result is not None:
            self._delete(_find_result["prev"], _find_result["node"])
        else:
            print(f"No node for value {value}")

Node 클레스에 따로 value와 pointer를 선언해주는 method없이 연결 리스트 클래스를 활용해 만들 수도 있다.(여담으로 예외처리가 완벽히 구현되지 않은 코드이다.)

sll_instance = SingleLinkedList(maxsize = 10)
print(value, 
for i in range(1,11):
    sll_instance._add(i)
    print(sll_instance.head)
# 결과 : 
[1, None]
[2, [1, None]]
[3, [2, [1, None]]]
[4, [3, [2, [1, None]]]]
[5, [4, [3, [2, [1, None]]]]]
[6, [5, [4, [3, [2, [1, None]]]]]]
[7, [6, [5, [4, [3, [2, [1, None]]]]]]]
[8, [7, [6, [5, [4, [3, [2, [1, None]]]]]]]]
[9, [8, [7, [6, [5, [4, [3, [2, [1, None]]]]]]]]]
[10, [9, [8, [7, [6, [5, [4, [3, [2, [1, None]]]]]]]]]]
sll_instance._print_list()
# 결과 : 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,

직접 구현한 _add method를 이용해 linked list를 구현하고 결과를 확인해보면 위와 같이 출력된다. 처음 null(None)값을 갖는 head에서 시작해 이전 노드를 pointer로 가지는 새로운 Node가 생성되는 형태이다.

sll_instance._find(2)
# 결과 : index of 2 is 8
sll_instance._delete_node(2)
sll_instance._print_list()
# 결과 : 10, 9, 7, 6, 5, 4, 3, 2, 1,

2번 index에 해당하는 node를 지워보았다. 결과에서 볼 수 있듯이 값이 8인 node가 삭제된 것을 알 수 있다.

sll_instance._find_by_value(8)
# 결과 : 8 NotFound
sll_instance._delete_node_by_value(8)
# 결과 : 8 NotFound
No node for value 8

이렇게 지워진 값을 찾거나 다시 지우려고하면 없는 value를 찾고 있기 때문에 에러 메세지와 함께 동작하지 않는 걸 알 수 있다.

FIFO type Linked List

FIFO type의 연결 리스트는 다음과 같이 구현하였다.

class Node:
    
    def __init__(self, value = None, pointer = None) -> None:
        self.value   = value
        self.pointer = pointer
    
    def __repr__(self) -> str:
        return repr([self.value, self.pointer])
        
class FIFOSingleLinkedList:
    
    def __init__(self, maxsize : int = 0) -> None:
        self.head    = None
        self.tail    = None
        self.length  = 0
        self.maxsize = maxsize
    
    def _print_list(self) -> None:
        node = self.head
        while node:
            print(node.value, end = ", ")
            node = node.pointer
        print()
    
    def _add(self, value) -> None:
        node = Node(value)
        
        if self.head is None:
            self.head = node
            self.tail = node
        if self.tail:
            self.tail.pointer = node
        self.tail = node
        
        self.length += 1
    
    def _find(self, index : int) -> dict:
        prev = None
        node = self.head
        
        i = 0
        while node and i < index:
            prev = node
            node = self.pointer
            i += 1
        
        return {
            "node"  : node,
            "index" : i,
            "prev"  : prev,
            }
    
    def _find_by_value(self, value) -> dict:
        prev = None
        node = self.head
        
        index = 0
        found = False
        while node and not found:
            if node.value == value:
                found = True
            else:
                prev = node
                node = node.pointer
            index += 1
        
        if found:
            print(f"{value} found on index of {index}")
            return {
                "node"  : node,
                "index" : index,
                "prev"  : prev,
            }
        print(f"{value} NotFound")
    
    def _delete_first(self):
        self.length = 0
        self.head   = None
        self.tail   = None
    
    def _delete(self, index : int) -> None:
        if self.head is not None or self.head.pointer is not None:
            self._delete_first()
        
        find_result = self._find(index)
        if find_result["index"] == index and (node := find_result["node"]):
            if not find_result["index"] or not (prev := find_result["prev"]):
                self.head = node.pointer
                self.tail = node.pointer
            else:
                prev.pointer = node.pointer
            
            self.length -= 1
    
    def _delete_by_value(self, value) -> None:
        if self.head is None or self.head.pointer is None:
            self._delete_first()
        
        find_result = self._find_by_value(value)
        if find_result is not None:
            if (node := find_result["node"]) and (node.value == value):
                self.length -= 1
                if not find_result["index"] or not (prev := find_result["prev"]):
                    self.head = node.pointer
                    self.tail = node.pointer
                prev.pointer = node.pointer