Python 연결 리스트: 예제와 함께 배우는 튜토리얼

연결 리스트는 데이터 조직과 관리에서 중요한 역할을 하는 자료 구조입니다. 메모리의 임의 위치에 저장된 일련의 노드로 구성되어, 메모리를 효율적으로 사용할 수 있습니다. 연결 리스트의 각 노드는 데이터 부분과 다음 노드를 가리키는 참조라는 두 가지 주요 구성 요소를 포함합니다.

처음 보면 다소 어렵게 느껴질 수 있지만 걱정하지 마세요!

연결 리스트가 무엇인지, 왜 사용하는지, 그리고 어떤 고유한 장점이 있는지 핵심부터 차근차근 설명하겠습니다.

왜 연결 리스트를 사용할까요?

연결 리스트는 일반 리스트와 배열에 데이터를 저장할 때의 여러 단점을 보완하기 위해 고안되었습니다. 주요 내용은 다음과 같습니다.

삽입과 삭제의 용이성

리스트에서 끝이 아닌 임의 위치에 원소를 삽입하거나 삭제하려면 이후 모든 원소를 이동해야 합니다. 이 과정의 시간 복잡도는 O(n)이며, 특히 리스트가 커질수록 성능 저하가 큽니다. 리스트의 동작 방식이나 구현이 익숙하지 않다면 Python 리스트 튜토리얼을 참고하세요.

반면 연결 리스트는 다르게 동작합니다. 원소를 비연속적인 여러 메모리 위치에 저장하고, 다음 노드를 가리키는 포인터로 서로 연결합니다. 이 구조 덕분에 링크만 수정하면 임의 위치에 원소를 추가하거나 삭제할 수 있습니다.

삽입 또는 삭제 지점의 노드를 직접 참조할 수 있다면, 해당 연산 자체는 O(1)입니다. 다만 그 위치를 찾기 위한 순회에는 여전히 O(n)이 필요하므로, O(1) 이점은 관련 노드에 대한 포인터를 이미 가지고 있을 때(예: 리스트의 머리에서 작업할 때)에만 적용됩니다.

동적 크기

Python 리스트는 동적 배열이므로 크기를 수정할 수 있는 유연성을 제공합니다.

하지만 이 과정에는 더 큰 메모리 블록으로의 재할당 등 복잡한 작업이 수반됩니다. 재할당 시 원소를 새 블록으로 복사해야 하고, 당장 필요 이상으로 공간을 할당할 수도 있어 비효율적입니다.

반대로 연결 리스트는 재할당이나 리사이징 없이도 동적으로 커지거나 작아질 수 있습니다. 높은 유연성이 필요한 작업에 더 적합한 선택이 됩니다.

메모리 효율성

리스트는 모든 원소에 대해 연속된 블록의 메모리를 할당합니다. 초기 크기를 넘어 확장이 필요하면 더 큰 연속 메모리 블록을 새로 할당하고 기존 원소를 모두 복사해야 합니다. 이 과정은 특히 큰 리스트에서 시간도 많이 들고 비효율적입니다. 반대로 초기 크기를 과도하게 잡으면 사용되지 않는 메모리가 낭비됩니다.

이에 비해 연결 리스트는 각 원소에 대해 별도로 메모리를 할당합니다. 원소를 추가할 때마다 필요한 만큼만 메모리를 할당하므로 메모리 활용이 더 효율적입니다.

언제 연결 리스트를 사용해야 할까요?

연결 리스트는 동적 크기와 메모리 효율성 등 일반 리스트와 배열 대비 장점이 있지만, 한계도 있습니다. 각 원소가 다음 노드를 참조하기 위한 포인터를 저장해야 하므로, 원소당 메모리 사용량이 더 큽니다. 또한 이 자료 구조는 데이터에 대한 직접 접근을 허용하지 않습니다. 특정 원소에 접근하려면 리스트의 시작부터 순차적으로 순회해야 하므로 탐색 시간 복잡도는 O(n)입니다.

연결 리스트와 배열 중 무엇을 선택할지는 애플리케이션의 요구 사항에 달려 있습니다. 다음과 같은 경우 연결 리스트가 특히 유용합니다.

• 많은 원소를 자주 삽입하고 삭제해야 할 때
• 데이터 크기를 예측하기 어렵거나 자주 변할 때
• 원소에 대한 직접 접근이 필수가 아닐 때
• 데이터셋의 원소나 구조가 큰 경우

연결 리스트의 종류

연결 리스트는 세 가지 종류가 있으며, 각각 다른 상황에서 고유한 장점을 제공합니다. 다음과 같습니다.

단일 연결 리스트

단일 연결 리스트

단일 연결 리스트는 가장 단순한 형태로, 각 노드가 데이터와 다음 노드에 대한 참조를 가집니다. 머리(첫 번째 노드)에서 꼬리(마지막 노드)까지 한 방향으로만 순회할 수 있습니다.

단일 연결 리스트의 각 노드는 보통 두 부분으로 구성됩니다.

• 데이터: 노드에 저장되는 실제 정보
• 다음 포인터: 다음 노드에 대한 참조. 마지막 노드의 다음 포인터는 보통 null로 설정됩니다.

이 자료 구조는 한 방향으로만 순회할 수 있으므로, 값이나 인덱스로 특정 원소에 접근하려면 머리부터 원하는 노드를 찾을 때까지 순차적으로 이동해야 합니다. 이 연산의 시간 복잡도는 O(n)이며, 큰 리스트에서는 비효율적입니다.

반면 리스트의 시작 부분에서 노드를 삽입하거나 삭제하는 작업은 매우 효율적이며 시간 복잡도는 O(1)입니다. 그러나 중간이나 끝에서의 삽입/삭제는 해당 지점까지 리스트를 순회해야 하므로 O(n)의 시간 복잡도를 가집니다.

이러한 특성 때문에 단일 연결 리스트는 리스트의 시작 부분에서 자주 연산을 수행할 때 유용합니다.

이중 연결 리스트

이중 연결 리스트

단일 연결 리스트의 단점 중 하나는 한 방향으로만 순회할 수 있어 필요할 때 이전 노드로 되돌아갈 수 없다는 점입니다. 이 제약은 양방향 탐색이 필요한 연산을 제한합니다.

이중 연결 리스트는 각 노드에 추가 포인터를 포함해 리스트를 양방향으로 순회할 수 있도록 합니다. 이중 연결 리스트의 각 노드는 데이터, 다음 노드를 가리키는 포인터, 이전 노드를 가리키는 포인터의 세 요소를 가집니다.

원형 연결 리스트

원형 연결 리스트

원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리켜 원형 구조를 이루는 특수한 형태입니다. 지금까지 본 단일/이중 연결 리스트와 달리 끝이 없고 반복해서 순환합니다.

이러한 순환적 특성은 마지막 플레이어에서 첫 플레이어로 이어지는 보드게임이나 라운드로빈 스케줄링 같은 알고리즘 등, 연속적으로 반복 순회해야 하는 상황에 적합합니다.

시간 복잡도 요약

연결 리스트와 Python 리스트를 한눈에 비교하면 다음과 같습니다.

핵심 요점: 연결 리스트는 머리(head)에서의 삽입과 삭제(O(1))에 강하지만, 그 외에는 불리합니다. 자료 구조의 시작 부분에서 원소를 자주 추가하거나 제거하지 않는다면, 일반 Python 리스트가 더 나은 선택일 가능성이 큽니다.

Python에서 연결 리스트를 만드는 방법

이제 연결 리스트의 개념, 사용 이유, 변형을 이해했으니 Python으로 구현해 보겠습니다. 이 튜토리얼에서 사용하는 노트북은 이 DataLab 워크북에서도 확인할 수 있습니다. 복사본을 만들면 코드를 직접 수정하고 실행할 수 있습니다. 로컬 실행에서 문제가 생길 때 특히 유용합니다!

노드 초기화

앞서 배웠듯, 노드는 연결 리스트의 요소로서 데이터와 다음 노드에 대한 참조를 저장합니다. Python에서 노드를 정의하는 방법은 다음과 같습니다.

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

    def __repr__(self):
        return f"Node({self.data})"제공

위 코드는 두 가지 주요 동작으로 노드를 초기화합니다. 노드의 “data” 속성에는 해당 노드가 담을 실제 정보가 할당됩니다. “next” 속성은 다음 노드의 주소를 나타내며, 현재는 None으로 설정되어 리스트의 다른 노드와 연결되어 있지 않음을 의미합니다. 연결 리스트에 새 노드를 추가해 나가면서 이 속성은 다음 노드를 가리키도록 업데이트됩니다.

연결 리스트 클래스 생성

다음으로 연결 리스트 클래스를 만듭니다. 이 클래스는 삽입과 삭제 등 노드 관리에 필요한 모든 연산을 캡슐화합니다. 우선 연결 리스트를 초기화하겠습니다.

class LinkedList:
    def __init__(self):
        self.head = None  # Initialize head as None제공

self.head를 None으로 설정함으로써, 초기에는 연결 리스트가 비어 있고 가리킬 노드가 없음을 명시합니다. 이제 새 노드를 삽입해 리스트를 채워 보겠습니다.

연결 리스트의 앞부분에 새 노드 삽입

LinkedList 클래스 안에 새 노드를 생성하여 리스트의 시작에 배치하는 메서드를 추가하겠습니다.

    def insertAtBeginning(self, new_data):
        new_node = Node(new_data)  # Create a new node 
        new_node.next = self.head  # Next for new node becomes the   current head
        self.head = new_node  # Head now points to the new node제공

이 메서드를 호출할 때마다 지정한 데이터로 새 노드가 생성됩니다. 새 노드의 next 포인터를 현재 머리로 설정하여 기존 노드들 앞에 배치합니다. 마지막으로 새로 만든 노드를 리스트의 머리로 지정합니다.

이제 삽입 연산의 작동 방식을 더 잘 이해하기 위해 단어들을 삽입해 보겠습니다. 먼저 리스트를 순회하며 내용을 출력하는 메서드를 만들어 봅시다.

    def printList(self):
        temp = self.head # Start from the head of the list
        while temp:
            print(temp.data,end=' ') # Print the data in the current node
            temp = temp.next # Move to the next node
        print()  # Ensures the output is followed by a new line제공

위 메서드는 연결 리스트의 내용을 출력합니다. 이제 정의한 메서드들을 사용해 “the quick brown fox”라는 단어들을 리스트에 채워 넣겠습니다.

if __name__ == '__main__':
    # Create a new LinkedList instance
    llist = LinkedList()

    # Insert each letter at the beginning using the method we created
    llist.insertAtBeginning('fox') 
    llist.insertAtBeginning('brown') 
    llist.insertAtBeginning('quick')  
    llist.insertAtBeginning('the')  

    # Now 'the' is the head of the list, followed by 'quick', then 'brown' and 'fox'

    # Print the list
    llist.printList()제공

위 코드는 다음과 같은 출력을 생성합니다.

"the quick brown fox"

연결 리스트의 끝부분에 새 노드 삽입

LinkedList 클래스에 insertAtEnd라는 메서드를 만들어 리스트의 끝에 새 노드를 추가하겠습니다. 리스트가 비어 있으면 새 노드가 머리가 됩니다. 그렇지 않다면 현재 마지막 노드 뒤에 새 노드를 이어 붙입니다. 동작 방식은 다음과 같습니다.

    def insertAtEnd(self, new_data):
        new_node = Node(new_data)
        if self.head is None:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node제공

이 메서드는 먼저 새 노드를 생성한 뒤, 리스트가 비어 있으면 머리로 지정합니다. 그렇지 않다면 리스트를 순회하여 마지막 노드를 찾고, 그 노드의 포인터를 새 노드로 설정합니다.

이제 이 메서드를 LinkedList 클래스에 포함하고, 리스트의 끝에 단어를 추가해 보겠습니다. 메인 함수를 다음과 같이 수정하세요.

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list
    llist.printList()제공

여기서는 insertAtEnd 메서드를 호출해 리스트의 끝에 “jumps”를 추가했습니다. 위 코드는 다음과 같은 출력을 생성합니다.

"the quick brown fox jumps"

연결 리스트의 앞부분에서 노드 삭제

연결 리스트의 첫 번째 노드를 삭제하는 작업은 간단합니다. 머리를 두 번째 노드로 가리키게 하면 첫 번째 노드는 더 이상 리스트의 일부가 아닙니다. 이를 구현하려면 LinkedList 클래스에 다음 메서드를 포함하세요.

def deleteFromBeginning(self):
    if self.head is None:
        return "The list is empty" # If the list is empty, return this string
    self.head = self.head.next  # Otherwise, remove the head by making the next node the new head제공

연결 리스트의 끝부분에서 노드 삭제

연결 리스트의 마지막 노드를 삭제하려면 리스트를 순회하여 끝에서 두 번째 노드를 찾고, 그 노드의 next 포인터를 None으로 바꿔야 합니다. 그러면 마지막 노드가 리스트에서 제거됩니다. 다음 메서드를 LinkedList 클래스에 추가하세요.

def deleteFromEnd(self):
    if self.head is None:
        return "The list is empty" 
    if self.head.next is None:
        self.head = None  # If there's only one node, remove the head by making it None
        return
    temp = self.head
    while temp.next.next:  # Otherwise, go to the second-last node
        temp = temp.next
    temp.next = None  # Remove the last node by setting the next pointer of the second-last node to None제공

위 메서드는 먼저 연결 리스트가 비어 있는지 확인하고, 비어 있다면 메시지를 반환합니다. 노드가 하나뿐이면 그 노드를 제거합니다. 노드가 여러 개라면 끝에서 두 번째 노드를 찾아 그 노드의 다음 참조를 None으로 업데이트합니다.

이제 메인 함수를 수정해 연결 리스트의 앞과 끝에서 원소를 삭제해 봅시다.

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

    # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from the beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()제공

위 코드는 삭제 전후의 리스트를 출력하여 연결 리스트에서의 삽입 및 삭제 연산이 어떻게 동작하는지 보여 줍니다. 실행하면 다음과 같은 출력이 나타납니다.

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox제공

특정 값을 연결 리스트에서 검색하기

마지막으로 학습할 연산은 연결 리스트에서 특정 값을 찾는 방법입니다. 이를 위해 메서드는 리스트의 머리에서 시작해 각 노드를 순회하며 노드의 데이터가 찾는 값과 일치하는지 확인해야 합니다. 구현 예시는 다음과 같습니다.

def search(self, value):
    current = self.head  # Start with the head of the list
    position = 0  # Counter to keep track of the position
    while current: # Traverse the list
        if current.data == value: # Compare the list's data to the search value
            return f"Value '{value}' found at position {position}" # Print the value if a match is found
        current = current.next
        position += 1
    return f"Value '{value}' not found in the list" 제공

앞서 만든 연결 리스트에서 특정 값을 찾으려면, 방금 만든 search 메서드를 메인 함수에 포함하세요.

if __name__ == '__main__':
    llist = LinkedList()

    # Insert words at the beginning
    llist.insertAtBeginning('fox')
    llist.insertAtBeginning('brown')
    llist.insertAtBeginning('quick')
    llist.insertAtBeginning('the')

    # Insert a word at the end
    llist.insertAtEnd('jumps')

   # Print the list before deletion
    print("List before deletion:")
    llist.printList()

    # Deleting nodes from beginning and end
    llist.deleteFromBeginning()
    llist.deleteFromEnd()

    # Print the list after deletion
    print("List after deletion:")
    llist.printList()
    
        # Search for 'quick' and 'lazy' in the list
    print(llist.search('quick'))  # Expected to find
    print(llist.search('lazy'))   # Expected not to find제공

위 코드는 다음과 같은 출력을 생성합니다.

List before deletion:
the quick brown fox jumps 
List after deletion:
quick brown fox 
Value 'quick' found at position 0
Value 'lazy' not found in the list제공

단어 “quick”은 리스트의 첫 번째 위치에 존재하므로 성공적으로 찾을 수 있습니다. 반면 “lazy”는 리스트에 없기 때문에 검색되지 않습니다.

마무리 생각

여기까지 오셨다면 축하합니다! 이제 연결 리스트의 기본 원리, 구조와 종류, 원소 추가/삭제 방법, 그리고 순회 방법까지 탄탄히 이해하셨습니다.

하지만 여기가 끝은 아닙니다. 연결 리스트는 자료 구조와 알고리즘 세계의 출발점일 뿐입니다. 이해를 더 깊게 할 수 있는 다음 단계를 소개합니다.

직접 프로젝트를 만들어 보세요

연결 리스트를 코딩 또는 데이터 사이언스 프로젝트에 통합해 실전에 적용해 보세요. 연결 리스트는 파일 시스템 개발, 해시 테이블 구성, GPS 내비게이션 시스템 및 보드게임 제작 등 다양한 곳에 활용됩니다. 직접 프로젝트를 시작해 보려면 Python, R, SQL로 실제 문제를 해결하는 방법을 알려 주는 무료 가이드형 데이터 사이언스 프로젝트를 확인하세요.

자료 구조와 알고리즘 학습

트리, 스택, 큐와 같은 다른 자료 구조를 배우는 것은 연결 리스트 이해를 바탕으로 한 자연스러운 확장입니다. 이 구조들은 연결 리스트의 원리를 토대로 더 다양한 계산 문제를 효율적으로 해결할 수 있게 해 줍니다. 예를 들어 트리와 이진 탐색 트리는 연결 리스트의 개념을 계층적 형태로 확장해 각 노드가 여러 요소에 연결될 수 있도록 합니다.

이 개념들이 낯설게 느껴지더라도 걱정하지 마세요! Datacamp에는 Python으로 배우는 자료 구조와 알고리즘 전용 강의가 있어 이러한 개념을 더 자세히 다룹니다. 스택, 트리, 해시 테이블, 큐, 그래프 같은 자료 구조부터 시작해, 점차 탐색 및 정렬 알고리즘을 이해하게 되어 더 효율적인 프로그래머이자 문제 해결자가 될 수 있습니다.

고급 연결 리스트 개념 탐구

이 튜토리얼에서는 단일 연결 리스트를 구현하며 삽입, 삭제, 순회 같은 연산을 다뤘습니다.

더 나아가 이중 연결 리스트와 원형 연결 리스트의 구현을 학습해 보세요. 스킵 리스트는 연결 리스트의 또 다른 확장으로, 원소에 더 빠르게 접근해 검색 속도를 높여 줍니다.

이러한 고급 자료 구조를 학습하면 기술 역량이 한 단계 도약하고, 프로그래밍 능력이 크게 향상되어 데이터 사이언스, 소프트웨어 개발, 머신러닝 엔지니어링 등에서 더 복잡한 과제에 대비할 수 있습니다.

이러한 고급 주제에 도전하기 전에 더 기초적인 프로그래밍 입문이 필요하다면, Python Programming 스킬 트랙을 살펴보세요. 언어의 기초를 익힐 수 있는 일련의 강의를 제공합니다.