Python으로 연결리스트 (LinkedList) 구현하기

파이썬에 내장된 배열리스트는 사용자 경험에 최적화되어 있는 편이라, 연결리스트의 대부분의 기능들이 포함되어 있다. 

그러나 하부가 배열로 구성되어 있기 때문에, 우리에게 드러나진 않지만 시간 복잡도 및 작업 부담 측면에서 여러 가지 비효율이 존재한다. (ex. 배열 중간에 있는 원소의 삽입 및 삭제에서 원소들을 하나씩 옮겨줘야 하기 때문에 작업 부담이 커짐)

 

파이썬에서도 연결리스트를 구현할 수 있다. 우선 다음과 같이 class를 사용하여 연결리스트에 사용될 노드 객체를 정의한다.

 

class ListNode:
	def __init__(self, newItem, nextNode):
    	self.item = newItem
        self.next = nextNode

 

이후 이 ListNode 객체를 이용하여 연결리스트를 구현하였다. 이 과정에서 dummy head를 맨 첫 번째 노드로 사용하게 되면, 원소의 삽입,.삭제 등의 함수를 구현할 때 코드를 훨씬 쉽게 작성할 수 있다. 그 예는 다음과 같다.

 

1) dummy head가 없는 연결리스트의 i번째에 원소 x를 삽입하는 함수 insert(i, x)

 

def insert(i, x):
    if i == 0: 					# 맨 앞에 삽입하는 경우
        newNode.item = x
        newNode.next = __head 
        __head = newNode
        __numItems += 1
    else:
        newNode.item = x
        newNode.next = prev.next
        prev.next = newNode
        __numItems += 1

 

맨 처음에 삽입하는 경우와 나머지 경우를 나누어 조건문을 작성해 주어야 한다. 반면 dummy head가 있는 경우 그렇게 하지 않아도 된다.

 

2) dummy head가 없는 연결리스트의 i번째에 원소 newItem를 삽입하는 함수 insert(i, newItem)

 

def insert(self, i, newItem):
    prev = self.__getNode(i-1)
    newNode = ListNode(newItem, prev.next)
    prev.next = newNode
    self.__numItems += 1

 

훨씬 코드가 간단해진 것을 볼 수 있다.

 

다음은 dummy head를 이용한 연결리스트를 구현한 코드이다. 최대한 파이썬 내장 배열리스트에 포함된 pop, append 등의 기능들을 모두 포함하도록 작성해보았다. 

.

class LinkedList:
    def __init__(self):
        self.__head = ListNode('dummy', None)
        self.__numItems = 0

    # LinkedList의 i번째 노드 알려주는 클래스 내부 함수
    def __getNode(self, i) -> ListNode:
        curr = self.__head
        for index in range(i+1):
            curr = curr.next
        return curr

    # LinkedList가 비어있는지의 여부를 bool 형태로 반환하는 함수
    def isEmpty(self) -> bool:
        return self.__numItems == 0

    # LinkedList의 i번째 노드로 newItem을 삽입하는 함수
    def insert(self, i, newItem):
        if 0 <= i <= self.__numItems:
            prev = self.__getNode(i - 1)
            newNode = ListNode(newItem, prev.next)
            prev.next = newNode
            self.__numItems += 1
        else:
            print("Index out of range")             # 주어진 i 값이 연결리스트의 index 범위 밖에 있는 경우 오류메세지

    # LinkedList의 마지막에 newItem을 포함한 노드를 덧붙이는 함수
    def append(self, newItem):
        prev = self.__getNode(self.__numItems - 1)
        newNode = ListNode(newItem, prev.next)
        prev.next = newNode
        self.__numItems

    # LinkedList의 i번째 원소를 삭제 후 반환하는 함수
    def pop(self, i):
        if 0 <= i <= self.__numItems -1 :
            prev = self.__getNode(i - 1)
            curr = prev.next
            prev.next = curr.next
            ret_Item = curr.item
            self.__numItems -= 1
            return ret_Item
        else:
            return None

    # LinkedList의 i번째 원소를 반환하는 함수
    def get(self, i):
        if self.isEmpty():
            return None
        if 0<= i <= self.__numItems - 1:
            return self.__getNode(i).item
        else:
            return None

    # 입력값 x가 LinkedList의 몇 번째 원소인지 알려주는 함수
    def index(self, x):
        curr = self.__head.next
        for i in range(self.__numItems):
            if curr.item == x:
                return i
            else:
                curr = curr.next

    # LinkedList의 x번째 노드와 그 전 노드를 반환하는 클래스 내부 함수
    def __findNode(self, x) -> (ListNode, ListNode):
        prev = self.__head
        curr = prev.next
        while curr != None:
            if curr.item == x:
                return (prev, curr)
            else:
                prev = curr
                curr = curr.next

    # LinkedList의 원소 x를 삭제하는 함수
    def remove(self, x):
        prev, curr = self.__findNode(x)
        if curr == None:
            return None
        else:
            prev.next = curr.next
            self.__numItems -= 1
            return x

    # LinkedList의 길이를 반환하는 함수
    def size(self):
        return self.__numItems

    # LinkedList를 비우는 함수
    def clear(self):
        self.__head = ListNode('dummy', None)
        self.__numItems = 0

    # LinkedList 내에 입력값 x가 몇 번 나오는지 세는 함수
    def count(self, x):
        cnt = 0
        curr = self.__head.next
        while curr != None:
            if curr.item == x:
                cnt += 1
            curr = curr.next
        return cnt

    # LinkedList를 복사하여 반환하는 함수
    def copy(self):
        a = LinkedList()
        for i in range(self.__numItems):
            a.append(self.get(i))
        return a

 

이런 식으로 class를 사용하여 연결리스트를 정의할 수 있다. 

 

물론 내장 배열리스트를 활용하여 가능한 작업의 폭이 넓기 때문에, 간단한 코드를 작성할 시 연결리스트를 사용할 일은 드물 것이다.

연결리스트가 유용한 경우는

 

1) 큰 메모리를 쓰거나 작업 시간이 오래 걸리는 코드를 작성할 시 (원형 연결리스트 사용하면 훨씬 효율적)

2) 동적으로 리스트의 원소들을 삽입하거나 삭제하는 작업이 많은 코드를 작성할 시

3) 배열리스트에서 원소의 총 수를 알지 못해 낭비되는 공간을 줄이고 싶을 때

 

라고 정리할 수 있다. 앞으로 코드를 작성하면서, 배열리스트와 연결리스트의 장단점을 고려해 적절한 방법을 택하여야 할 것이다.