[자료구조] 파이썬으로 단일연결리스트 구현하기

단일연결리스트

동적 배열의 단점

동적 배열은 연속된 메모리 공간에 값을 할당한다. 파이썬의 리스트는 값을 직접 저장하지 않고 해당하는 객체의 주소를 저장하는 레퍼런스 배열이기 때문에 다른 언어의 배열과는 약간 다르다.

동적 배열은 먼저 크기를 할당해 메모리 공간을 미리 확보해놓고 이후에 값을 저장하기 때문에 대부분의 경우 저장하는 요소의 수가 배열의 길이보다 작다.
append 연산은 분할 분석 방식으로는 O(1) 의 시간복잡도를 가지지만 실제로는 배열이 가득 찼을 때 resize 연산을 하면서 O(n) 의 시간복잡도를 가진다. 즉 특정 시점(배열이 가득 찼을 때)에 연산 속도가 갑자기 느려진다. 이는 실시간 시스템에서는 문제를 유발할 수 있다.

동적 배열의 단점을 정리하면 아래와 같다.

• 동적 배열의 길이는 저장하는 요소의 수보다 길어서 메모리 낭비가 생긴다.
• 분할 분석 방식은 실시간 시스템에서 허용되지 않을 수 있다.(특정 시점에 갑자기 느려지면 안될 수도 있으니까)
• 배열의 삽입 또는 삭제 연산 비용이 O(n)으로 비싸다.

 

단일연결리스트

위와 같은 문제점은 연결리스트를 구현함으로써 해결될 수 있다. 물론 trade-off는 있다. 단일연결리스트는 각 요소별로 노드를 할당해 관리한다. 각 노드들은 객체의 레퍼런스와 다음 노드를 가리키는 링크를 저장하고 있다. 미리 고정된 크기가 할당되는 것이 아니라 필요할 때마다 노드를 추가하기 때문에 리스트의 요소의 수만큼 노드가 존재하므로 메모리의 낭비가 없다. 삽입/삭제 연산 시 앞 노드의 링크만 바꿔주면 되기 때문에 O(1) 의 시간복잡도를 가진다. 하지만 데이터에 접근할때는 헤드부터 순차적으로 리스트를 순회하기 때문에 O(n) 의 시간복잡도를 가진다.

 

단일연결리스트의 성능

Operation	Running Time
add_first()	O(1)
add_last()	O(n)
pop_first()	O(1)
pop_last()	O(n)
node_at(k)	O(k)
search()	O(n)
len()	O(n)

데이터를 삽입, 삭제하는 연산 자체는 O(1) 의 시간복잡도를 가지지만 데이터에 접근하는데 O(n) 의 시간복잡도를 가진다.

 

구현

Node 클래스

우선 객체를 저장하는 element와 다음 노드의 링크를 저장할 next를 가진 _Node 클래스를 정의한다.

class SinglyLinkedList:
    class _Node:
        def __init__(self, element=None, next=None):
            self._element = element
            self._next = next

       def __str__(self):
           return str(self._element) ## 요소를 문자열로 변환하여 반환, print함수에서 사용된다.

생성자

리스트에 포함되어야 할 정보는 리스트의 가장 첫 번째 노드를 나타내는 head와 리스트의 길이이다. tail은 명시적으로 구현하는 경우도 있고 그렇지 않은 경우도 있다. 그리고 list를 출력하는데 사용할 함수도 하나 만들어 준다.

    def __init__(self):
        self._head = None
        self._size = 0

    def __len__(self):
        return self._size  ## len(A) 호출 시 사용된다.

    ## head부터 더 이상 노드가 존재하지 않을 때까지 노드를 순회하며 출력한다.
    def printList(self):
        v = self._head
        while v:
            print(v._element, "->", end=" ")
            v = v._next
        print("None")

printList()를 이용하지 않고 그냥 print함수를 이용해서 리스트를 찍고 싶은 마음이 생긴다. 그렇게 하려면 클래스 내부에 \__str\__이라는 특별한 함수를 선언해줘야 하는데, 뒷부분에서 구현하기로 한다.

add_first

리스트의 가장 앞에 새로운 노드를 추가한다.

    def add_first(self, element):
        newest = self._Node(element, self._head)  # 새 노드의 다음 노드를 기존의 head로 지정. newest._next = self.head
        self._head = newest  # 새 노드를 head로 지정
        self._size += 1

newest = self._Node(element, self._head) 노드를 새로 생성하는데, 새로운 노드의 다음 노드는 무엇을 가리키고 있어야 할까? 바로 새로운 노드가 추가되기 전까지 head였던 녀석이다. 그러므로 새 노드의 next에 self.head를 할당해준다.

add_last

리스트의 가장 끝에 새로운 노드를 추가한다.

    def add_last(self, element):
        newest = self._Node(element)
        if self._head is None:  # 빈 리스트일 경우
            self.add_first(element)
        else:
            tail = self._head
            while tail._next is not None:
                tail = tail._next  # 리스트의 끝까지 이동
            tail._next = newest    # 가장 마지막 노드의 다음 노드를 새 노드로 지정
            self._size += 1

pop_first

리스트의 가장 첫 번째 노드를 삭제하고 반환한다. head는 원래 head였던 녀석의 다음 노드가 된다.

    def pop_first(self):
        if self._head is None:
            return None
        element = self._head
        self._head = self._head._next
        self._size -= 1
        return element

pop_last

    def pop_last(self):
        if self._head is None:
            return None
        tail = self._head
        prev = None
        while tail._next is not None:
            prev = tail
            tail = tail._next
        # 루프를 탈출하면 tail은 마지막 노드, prev는 그 이전 노드를 가리킴
        # 만일 리스트의 요소가 하나라면 반복문을 수행하지 않음
        if prev is None:
            self._head = None
        else:
            prev._next = None
        self._size -= 1
        return tail._element

이 예제에서는 tail의 정보를 따로 관리하지 않기 때문에 head부터 순차적으로 리스트를 탐색하며 마지막 노드로 이동한다. 이때 리스트의 요소가 하나인 경우에는 self._head가 None이 되어야 하므로 케이스를 분리해서 생각한다.

node_at

이번에는 노드의 인덱스를 받아서 값을 리턴하는 메서드를 만들어보자

    def node_at(self, index):
        if not isinstance(index, int):
            raise TypeError('invalid index type')

        if index < 0 or index >= self._size:
            raise IndexError('index out of range')

        if not self._head:
            raise IndexError("index out of range")

        curr = self._head
        for _ in range(index):
            curr = curr._next
        return curr

앞의 조건문 세 개는 단순한 유효성 검사이다. head부터 인덱스로 주어진 값만큼 다음 노드를 탐색한다.

search(), print()

이번에는 찾고자하는 element를 입력받아 있으면 그것을 반환하고 없으면 None을 반환하는 메서드를 만들어보자.
리스트를 순회하기 위해서 내부적으로 generator를 구현할 것이다. generator를 구현하고 나면 앞서 언급했듯 print()를 이용해 리스트를 직접 찍어볼 수 있도록 만들 수 있다.

우선 우리가 구현하고자하는 search()의 형태는 다음과 같다.

    def search(self, element):
        for v in self:
            if v._element == element:
                return v
        return None

리스트를 순회하면서 각 요소를 변수 v로 가져온다. 하지만 지금은 이 메서드를 사용할 수 없다. self가 반복가능한 객체가 아니기 때문이다. 이를 위해 _iter_ 라는 특별한 메서드를 만들어주어야 한다. 내부에 이터레이터를 구현하면 반복가능한 객체로 활용할 수 있다.

    def __iter__(self):
        v = self._head
        while v is not None:
            yield v
            assert isinstance(v._next, object)
            v = v._next

이제 리스트를 순회할 수 있으므로 str 메서드도 구현할 수 있다.

    def __str__(self):
        return " -> ".join(str(v) for v in self)

 

전체 코드

class SinglyLinkedList:
    class _Node:
        def __init__(self, element=None, next=None):
            self._element = element
            self._next = next

        def __str__(self):
            return str(self._element)

    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def __str__(self):
        return " -> ".join(str(v) for v in self)

    def __iter__(self):
        v = self._head
        while v is not None:
            yield v
            assert isinstance(v._next, object)
            v = v._next

    def node_at(self, index):
        if not isinstance(index, int):
            raise TypeError('invalid index type')

        if index < 0 or index >= self._size:
            raise IndexError('index out of range')

        if not self._head:
            raise IndexError("index out of range")

        curr = self._head
        for _ in range(index):
            curr = curr._next
        return curr

    def add_first(self, element):
        newest = self._Node(element, self._head)  # 새 노드 생성 self._head = newest
        self._head = newest
        self._size += 1

    def add_last(self, element):
        newest = self._Node(element)
        if self._head is None:
            self.add_first(element)
        else:
            tail = self._head
            while tail._next is not None:
                tail = tail._next
            tail._next = newest
            self._size += 1

    def pop_first(self):
        if self._head is None:
            return None
        element = self._head
        self._head = self._head._next
        self._size -= 1
        return element

    def pop_last(self):
        if self._head is None:
            return None
        tail = self._head
        prev = None
        while tail._next is not None:
            prev = tail
            tail = tail._next
        # 루프를 탈출하면 tail은 마지막 노드, prev는 그 이전 노드를 가리킴
        # 만일 리스트의 요소가 하나라면 반복문을 수행하지 않음
        if prev is None:
            self._head = None
        else:
            prev._next = None
        self._size -= 1
        return tail._element

    def search(self, element):
        for v in self:
            if v._element == element:
                return v
        return None