콘텐츠로 건너뛰기
CodeMDD.io | Coding Tutorials

파이썬에서 링크드리스트 사용하기

[

파이썬에서 링크드 리스트 사용하기: 개요

링크드 리스트(linked list)는 리스트(list)의 잘 알려진 부족한 인지도를 가진 친척이다. 링크드 리스트는 그다지 인기가 없을 수도 있고, 알고리즘 수업에서도 기억에 남지 않을 수도 있다. 그러나 적절한 상황에서는 링크드 리스트가 매우 유용하게 사용될 수 있다.

이 글에서는 다음과 같은 내용을 배울 수 있다:

  • 링크드 리스트가 무엇이며 언제 사용해야 하는지
  • collections.deque를 사용하여 링크드 리스트를 모두 다루는 방법
  • 직접 링크드 리스트를 구현하는 방법
  • 다른 종류의 링크드 리스트와 그들이 어떻게 사용되는지

이 튜토리얼에서는 링크드 리스트에 대해 알아보기 위해 다음 링크에서 사용 가능한 소스 코드를 다운로드하여 예제를 따라할 수 있다:

링크드 리스트 이해하기

링크드 리스트는 순서대로 정렬된 객체의 컬렉션이다. 그렇다면 링크드 리스트가 일반적인 리스트와 어떻게 다른가? 링크드 리스트는 요소를 메모리에 저장하는 방식에서 리스트와 다르다. 리스트는 데이터에 대한 참조를 저장하는 인접한 메모리 블록을 사용하고, 링크드 리스트는 자체 요소의 일부로 참조를 저장한다.

주요 개념

링크드 리스트가 무엇이고 어떻게 사용되는지 더 깊이 들어가기 전에, 어떻게 구조화되는지 먼저 알아야 한다. 링크드 리스트의 각 요소는 노드(node) 라고 불리며, 각 노드는 두 가지 다른 필드를 가지고 있다:

  1. 데이터(data) 는 노드에 저장될 값을 포함한다.
  2. 다음(next) 은 리스트에서 다음 노드를 가리키는 참조를 포함한다.

일반적인 노드의 예시는 다음과 같다:

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

이제 링크드 리스트의 구조를 알았으니, 실제로 활용할 수 있는 몇 가지 실용적인 예시를 살펴보자.

실용적인 응용 사례

링크드 리스트는 실제 세계에서 여러 목적으로 사용될 수 있다. 링크드 리스트는 구현할 수 있으며, 여기에는 (스포일러 얼럿) 스택(Stacks), 큐(Queues), 그래프(Graphs) 등이 포함된다. 또한 메모리를 효율적으로 사용하고자 할 때 링크드 리스트는 매우 유용한 데이터 구조이다.

링크드 리스트는 여러 상황에서 다양한 장점을 가지고 있다:

  • 데이터를 동적으로 추가하고 삭제할 수 있다.
  • 요소의 순서를 일관되게 유지할 수 있다.
  • 요소에 대한 참조를 추가할 필요가 없다.

링크드 리스트는 다른 리스트와는 다른 유연한 데이터 구조이다. 개별 요소의 순서가 중요한 경우, 링크드 리스트는 유용한 선택이 될 수 있다.

collections.deque 소개

파이썬에서는 링크드 리스트를 구현하기 위해 collections.deque를 사용할 수 있다. collections.deque는 효율적인 큐와 스택의 구현을 제공한다. 이 모듈은 내부적으로 이중 연결 리스트(doubly linked list)로 작동한다. 그러나 이 모듈을 사용하면 단순한 방법으로 큐와 스택을 구현할 수 있다.

collections.deque 사용하기

collections.deque는 from collections import deque를 사용하여 임포트할 수 있다. 예를 들어, 다음과 같이 사용할 수 있다:

from collections import deque


# 빈 deque 생성
d = deque()


# deque에 요소 추가
d.append(1)
d.append(2)
d.append(3)

위의 코드에서는 deque 객체를 생성하고 append() 메서드를 사용하여 요소를 추가한다. deque는 리스트와 같은 일반적인 메서드(append(), pop(), remove(), count() 등)를 모두 지원한다. 이는 링크드 리스트와 마찬가지로 동적으로 요소를 추가하고 삭제할 수 있음을 의미한다.

이제 collections.deque를 사용하여 큐와 스택을 어떻게 구현하는지 알아보자.

큐와 스택 구현하기

collections.deque를 사용하여 큐와 스택을 구현하는 것은 매우 간단하다. 큐 구현의 경우, deque를 사용하여 요소를 추가하고 popleft() 메서드를 사용하여 첫 번째 요소를 제거할 수 있다. 스택 구현의 경우, deque를 사용하여 요소를 추가하고 pop() 메서드를 사용하여 마지막 요소를 제거할 수 있다.

다음은 collections.deque를 사용하여 큐와 스택을 구현하는 예시이다:

from collections import deque


# 큐 구현
queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
front = queue.popleft()
print(front)  # 출력: 1


# 스택 구현
stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
top = stack.pop()
print(top)  # 출력: 3

위 코드에서는 deque를 사용하여 큐와 스택을 간단히 구현한 예시이다. append() 메서드로 요소를 추가하고, popleft() 메서드로 첫 번째 요소를 제거하는 것으로 큐를 구현할 수 있다. stack은 스택을 구현하기 위해 사용되며 pop() 메서드로 마지막 요소를 제거한다.

직접 링크드 리스트 구현하기

파이썬에서는 collections.deque를 사용하여 링크드 리스트를 구현할 수 있지만, 직접 구현하는 방법도 알아두는 것이 유용할 수 있다. 직접 링크드 리스트를 구현하면 요소의 추가, 삭제, 검색 등을 더 세밀하게 제어할 수 있다.

링크드 리스트 생성하기

링크드 리스트를 구현하기 위해 먼저 Node 클래스를 만들어야 한다. Node 클래스는 데이터와 다음 노드를 저장하는 next 값을 가지며, 요소의 추가, 삭제, 검색 등의 작업이 가능한 메서드를 제공한다. 다음은 Node 클래스의 예시이다:

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

Node 클래스는 data와 next 필드를 가진다. data 필드는 노드에 저장할 값을 포함한다. next 필드는 리스트에서 다음 노드를 가리키는 참조를 가진다.

링크드 리스트를 구현하려면 LinkedList 클래스를 정의해야 한다. LinkedList 클래스는 노드들의 컬렉션을 가지며, 리스트에 추가, 삭제, 검색 등의 작업을 수행하는 메서드를 제공한다. 다음은 LinkedList 클래스의 예시이다:

class LinkedList:
    def __init__(self):
        self.head = None

위의 예시에서는 LinkedList 객체를 생성하고, head 필드를 초기화한다. head 필드는 리스트를 반복하는 데 사용되는 시작 지점으로 사용된다.

이제 링크드 리스트에 노드를 추가하고 삭제하고 검색하는 방법을 알아보자.

링크드 리스트의 노드 추가하기

링크드 리스트에 노드를 추가하는 방법을 알아보자. 예를 들어, 다음과 같은 링크드 리스트가 있다고 가정해보자:

위의 링크드 리스트에 노드를 추가하려면 다음과 같은 단계를 따라야 한다:

  1. 새로운 노드를 생성한다.
  2. 현재 리스트의 맨 마지막 노드를 찾는다.
  3. 맨 마지막 노드의 next 값으로 새로운 노드를 설정한다.

다음은 링크드 리스트에 노드를 추가하는 예시이다:

class LinkedList:
    def __init__(self):
        self.head = None


    # 노드 추가하기
    def append(self, data):
        new_node = Node(data)


        if self.head is None:
            self.head = new_node
        else:
            current_node = self.head
            while current_node.next:
                current_node = current_node.next
            current_node.next = new_node

위의 코드에서는 append() 메서드를 사용하여 노드를 추가한다. append() 메서드는 새로운 노드를 생성하고, self.head가 None인지 확인한 후, self.head가 None이라면 새로운 노드를 self.head로 설정한다. 그렇지 않으면 현재 노드를 찾고, 마지막 노드의 next 값을 새로운 노드로 설정한다.

이제 링크드 리스트의 노드를 탐색하는 방법을 알아보자.

링크드 리스트의 노드 탐색하기

링크드 리스트의 노드를 탐색하는 방법에 대해 알아보자. 예를 들어, 다음과 같은 링크드 리스트가 있다고 가정해보자:

위의 링크드 리스트에서 특정 데이터를 가진 노드를 찾는 방법은 다음과 같다:

  1. 리스트의 첫 번째 노드부터 시작한다.
  2. 각 노드를 확인하면서 데이터가 일치하는지 확인한다.
  3. 데이터가 일치하는 노드를 찾으면 반복을 종료하고 해당 노드를 리턴한다.

다음은 링크드 리스트에서 특정 데이터를 가진 노드를 탐색하는 예시이다:

class LinkedList:
    def __init__(self):
        self.head = None


    # 노드 탐색하기
    def find_node(self, data):
        current_node = self.head


        while current_node:
            if current_node.data == data:
                return current_node
            current_node = current_node.next


        return None

위의 코드에서는 find_node() 메서드를 사용하여 노드를 탐색한다. find_node() 메서드는 링크드 리스트의 첫 번째 노드부터 시작하여 각 노드를 확인하고, 데이터가 일치하는 노드를 찾으면 해당 노드를 리턴한다. 데이터가 일치하는 노드를 찾지 못하면 None을 리턴한다.

이제 링크드 리스트의 노드를 삭제하는 방법을 알아보자.

링크드 리스트의 노드 삭제하기

링크드 리스트의 노드를 삭제하는 방법에 대해 알아보자. 예를 들어, 다음과 같은 링크드 리스트가 있다고 가정해보자:

위의 링크드 리스트에서 특정 데이터를 가진 노드를 삭제하는 방법은 다음과 같다:

  1. 리스트의 첫 번째 노드부터 시작한다.
  2. 각 노드를 확인하면서 데이터가 일치하는지 확인한다.
  3. 데이터가 일치하는 노드를 찾으면 해당 노드의 이전 노드와 다음 노드를 연결한다.
  4. 데이터가 일치하는 노드를 찾으면 반복을 종료하고 해당 노드를 삭제한다.

다음은 링크드 리스트에서 특정 데이터를 가진 노드를 삭제하는 예시이다:

class LinkedList:
    def __init__(self):
        self.head = None


    # 노드 삭제하기
    def remove_node(self, data):
        current_node = self.head
        previous_node = None


        while current_node:
            if current_node.data == data:
                if previous_node:
                    previous_node.next = current_node.next
                else:
                    self.head = current_node.next
                return
            previous_node = current_node
            current_node = current_node.next

위의 코드에서는 remove_node() 메서드를 사용하여 노드를 삭제한다. remove_node() 메서드는 링크드 리스트의 첫 번째 노드부터 시작하여 각 노드를 확인하고, 데이터가 일치하는 노드를 찾으면 이전 노드와 다음 노드를 연결하여 해당 노드를 삭제한다. 이전 노드가 있는 경우 이전 노드의 next 값을 해당 노드의 next 값으로 설정하고, 그렇지 않으면 self.head 값을 해당 노드의 next 값으로 설정한다.

이제 다양한 유형의 링크드 리스트를 사용하는 방법을 알아보자.

고급 링크드 리스트 사용하기

collections.deque를 사용하여 기본 링크드 리스트를 구현할 수 있지만, 인접 리스트(doubly linked list)와 원형 링크드 리스트(circular linked list)와 같은 다른 유형의 링크드 리스트를 사용하는 것도 가능하다.

이중 연결 리스트 사용하기

이중 연결 리스트(doubly linked list)는 각 노드가 이전 노드와 다음 노드를 가리키고 있는 링크드 리스트이다. 이중 연결 리스트를 사용하면 양방향으로 노드에 접근할 수 있으며, 요소의 추가, 삭제 및 탐색을 더욱 용이하게 수행할 수 있다.

collections.deque를 사용하여 이중 연결 리스트를 구현하는 것은 간단하다. collections.deque는 내부적으로 이중 연결 리스트로 작동하기 때문이다. 예를 들어, 다음과 같이 이중 연결 리스트를 구현할 수 있다:

from collections import deque


# 이중 연결 리스트 구현
doubly_linked_list = deque()
doubly_linked_list.append(1)
doubly_linked_list.append(2)
doubly_linked_list.append(3)

위의 코드에서는 deque를 사용하여 이중 연결 리스트를 구현한다. append() 메서드를 사용하여 요소를 추가할 수 있으며, 리스트의 앞과 뒤에서 요소를 추가하거나 제거할 수도 있다.

원형 링크드 리스트 사용하기

원형 링크드 리스트(circular linked list)는 마지막 노드가 첫 번째 노드를 가리키고 있는 링크드 리스트이다. 이는 마지막 요소와 첫 번째 요소를 서로 연결하여 리스트를 무한히 반복 가능하게 만든다. 원형 링크드 리스트는 순환적인 구조를 필요로 하는 상황에서 유용하게 사용될 수 있다.

collections.deque를 사용하여 원형 링크드 리스트를 구현하는 것은 간단하다. 리스트의 첫 번째 요소와 마지막 요소를 연결하여 원형 구조를 만들 수 있다. 예를 들어, 다음과 같이 원형 링크드 리스트를 구현할 수 있다:

from collections import deque


# 원형 링크드 리스트 구현
circular_linked_list = deque()
circular_linked_list.append(1)
circular_linked_list.append(2)
circular_linked_list.append(3)


circular_linked_list[-1].next = circular_linked_list[0]

위의 코드에서는 deque를 사용하여 원형 링크드 리스트를 구현한다. append() 메서드를 사용하여 요소를 추가하고, 마지막 요소의 next 값을 첫 번째 요소로 설정하여 원형 구조를 만든다.

결론

링크드 리스트는 여러 가지 상황에서 다양한 장점을 가지고 있다. 데이터를 동적으로 추가하거나 삭제할 수 있으며, 요소의 순서를 일관되게 유지할 수 있다. 또한 요소에 대한 참조를 추가할 필요가 없다. 링크드 리스트는 다른 리스트와는 다른 유연한 데이터 구조이다. 개별 요소의 순서가 중요한 경우, 링크드 리스트는 유용한 선택이 될 수 있다.

파이썬에서는 collections.deque를 사용하여 링크드 리스트를 구현할 수 있지만, 직접 구현하는 방법도 유용하다. 직접 링크드 리스트를 구현하면 요소의 추가, 삭제, 검색 등을 더욱 세밀하게 제어할 수 있다. 이 기사는 링크드 리스트에 대한 입문을 제공하며, collections.deque를 사용해 보고 직접 구현하는 방법을 알려준다.