포인터/커서를 이용한 연결 리스트

배열로 구현한 연결 리스트의 한계

 

[a, b, c, d]의 배열에서 a와 b 사이에 e을 삽입한다면 c, d를 하나씩 뒤로 이동해야합니다. 삭제하는 경우에도 마찬가지로 데이터를 옮겨야 하므로 효율적이지 않습니다.

 

파이썬의 연결 리스트

 

연결 리스트는 임의의 위치에 원소를 삽입하거나 삭제할 때 빠르게 수행할 수 있다는 장점이 있지만, 메모리와 속도 면에서는 배열보다 효율이 떨어집니다. 파이썬의 리스트는 이러한 연결 리스트의 자료구조가 아니라 모든 원소를 연속으로 메모리에 배치하는 '배열'로 내부에서 구현하고 있습니다. 그러므로 속도가 급격히 떨어지지는 않습니다.

 

또 원소를 하나씩 추가/삽입 시 내부에서 메모리를 해제하거나 확보하지 않습니다. 실제 필요한 메모리보다 여유 있게 미리 마련하기 때문입니다.

 

포인터를 이용한 연결 리스트

 

노드 클래스입니다. data와 뒤쪽 노드에 대한 참조를 가리키는 노드형 next 필드로 구성됩니다.

class Node:
    """연결 리스트용 노드 클래스"""

    def __init__(self, data: Any = None, next: Node = None):
        """초기화"""
        self.data = data
        self.next = next

 

다음은 연결 리스트 구현을 위한 각 함수입니다. 

class LinkedList:
    """연결 리스트 클래스"""

    def __init__(self) -> None:
        """초기화"""
        self.no = 0
        self.head = None
        self.current = None
    

    def __len__(self) -> int:
        """연결 리스트의 노드 개수를 반환"""
        return self.no
    

    def search(self, data: Any) -> int:
        """data와 값이 같은 노드를 검색"""
        cnt = 0
        ptr = self.head
        while ptr is not None:
            if ptr.data == data:
                self.current = ptr
                return cnt
            cnt += 1
            ptr = ptr.next
        return -1


    def __contains__(self, data: Any) -> bool:
        """연결 리스트에 data가 포함되어 있는지 확인"""
        return self.search(data) >= 0


    def add_first(self, data: Any) -> None:
        """맨 앞에 노드를 삽입"""
        # 삽입하기 전의 머리 노드를 ptr로 저장
        ptr = self.head
        self.head = self.current = Node(data, ptr)
        self.no += 1


    def add_last(self, data: Any):
        """맨 끝에 노드를 삽입"""
        if self.head is None:
            self.add_first(data)
        else:
            ptr = self.head
            while ptr.next is not None:
                ptr = ptr.next
            ptr.next = self.current = Node(data, None)
            self.no += 1

    
    def remove_first(self) -> None:
        """머리 노드를 삭제"""
        if self.head is not None:
            self.head = self.current = self.head.next
        self.no -= 1
    

    def remove_last(self):
        """꼬리 노드를 삭제"""
        if self.head is not None:
            if self.head.next is None:
                self.remove_first()
            else:
                ptr = self.head
                pre = self.head
            while ptr.next is not None:
                pre = ptr
                ptr = ptr.next 
            pre.next = None
            self.current = pre
            self.no -= 1
            
    def remove(self, p: None) -> None:
        """노드 p를 삭제"""
        if self.head is not None:
            if p is self.head():
                self.remove_first()
            else:
                ptr = self.head
            while ptr.next is not p:
                ptr = ptr.next
                if ptr is None:
                    return
            ptr.next = p.next
            self.current = ptr
            self.no -= 1

        
    def remove_current_node(self) -> None:
        """주목 노드를 삭제"""
        self.remove(self.current)


    def clear(self) -> None:
        """전체 노드를 삭제"""
        while self.head is not None:
            self.remove_first()
        self.current = None
        self.no = 0

    
    def next(self) -> bool:
        """주목 노드를 한 칸 뒤로 이동"""
        if self.current is None or self.current.next is None:
            return False
        self.current = self.current.next
        return True


    def print_current_node(self) -> None:
        """주목 노드를 출력"""
        if self.current is None:
            print('주목 노드가 존재하지 않습니다.')
        else:
            print(self.current.data)

 

커서를 이용한 연결 리스트

 

포인터를 사용한 연결 리스트는 노드를 삽입/삭제할 때 데이터를 이동하지 않고 처리하는 특징이 있습니다. 하지만 노드를 삽입/삭제할 때마다 내부에서 노드용 인스턴스를 생성하고 소멸하는데 이때 메모리를 확보하고 해제하는데 쓰는 비용을 무시할 수 없습니다.

 

그러므로 프로그램을 실행하면서 데이터 개수가 크게 변하지 않거나, 데이터 최대 개수를 예측할 수 있는 경우라면 배열 안의 원소를 사용하여 효율적으로 운용할 수 있습니다. 

 

커서를 이용한 연결리스트는 여기서 커서라는 포인터를 사용하여 노드 클래스를 구현합니다. 이때 next 필드는 리스트의 다음 뒤쪽 인덱스를 표현합니다. 물론 마지막 꼬리 노드의 뒤쪽 포인터(next)는 -1입니다.

class Node:
    """연결 리스트용 노드 클래스(배열 커서 버전)"""

    def __init__(self, data = Null, next = Null, dnext = Null):
        """초기화"""
        self.data = data
        self.next = next
        # 프리 리스트의 뒤쪽 포인터
        self.dnext = dnext

 

여기서 프리 리스트는 삭제된 레코드 그룹을 관리할 때 사용되는 자료구조입니다. 프리 리스트를 사용하면 삭제 후 비어 있는 배열의 문제를 해결할 수 있습니다.