Python의 연결 목록 - Plato AiStream V2.1

플라톤에 의해 재발행

팔로워 : 0

개요

연결 목록은 일련의 노드로 구성된 데이터 구조이며, 각 노드에는 값과 시퀀스의 다음 노드에 대한 참조가 포함되어 있습니다. 배열과 달리 연결 목록은 연속적인 메모리 할당이 필요하지 않으므로 특정 작업에 더 유연하고 효율적입니다. 이번 글에서는 Linked List의 장점과 단점, Python에서 구현하는 방법에 대해 알아보겠습니다.

차례

연결리스트의 장점과 단점

연결 목록은 다른 데이터 구조에 비해 몇 가지 장점을 제공합니다. 첫째, 인접한 노드의 참조만 업데이트하면 되므로 요소를 효율적으로 삽입하고 삭제할 수 있습니다. 이로 인해 LinkedList는 자주 수정이 예상되는 시나리오에 이상적입니다. 또한 LinkedList는 크기가 고정된 배열과 달리 크기가 동적으로 늘어나거나 줄어들 수 있습니다.

그러나 연결 목록에는 몇 가지 단점도 있습니다. 배열과 달리 연결 목록은 요소에 대한 무작위 액세스를 지원하지 않습니다. 즉, 특정 인덱스의 요소에 액세스하려면 처음부터 목록을 순회해야 합니다. 이로 인해 특정 작업의 성능이 저하될 수 있습니다. 또한 연결된 목록에는 다음 노드에 대한 참조를 저장하기 위해 추가 메모리가 필요하므로 작은 데이터 세트에는 비효율적일 수 있습니다.

Python에서 연결 목록 구현

Python은 연결 목록을 구현하는 유연하고 직관적인 방법을 제공합니다. 연결 목록에는 단일 연결 목록, 이중 연결 목록, 순환 연결 목록의 세 가지 주요 유형이 있습니다. 각각을 자세히 살펴보겠습니다.

단일 연결 목록

단일 연결 목록은 각 노드가 값과 시퀀스의 다음 노드에 대한 참조를 포함하는 노드로 구성됩니다. Python에서 단일 연결 목록을 만드는 방법은 다음과 같습니다.

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

class Linked List:
    def __init__(self):
        self.head = None

단일 연결 목록 만들기

단일 연결 목록을 만들려면 목록의 각 노드를 나타내는 Node 클래스를 정의해야 합니다. 각 노드에는 값과 다음 노드에 대한 참조가 포함됩니다. Linked List 클래스는 목록의 첫 번째 노드를 가리키는 head 속성을 사용하여 노드의 컨테이너 역할을 합니다.

단일 연결 목록에 노드 삽입

단일 연결 목록에 노드를 삽입하려면 인접 노드의 참조를 업데이트해야 합니다. 다음은 목록 시작 부분에 노드를 삽입하는 예입니다.

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

단일 연결 목록에서 노드 삭제

단일 연결 목록에서 노드를 삭제하려면 인접 노드의 참조를 업데이트해야 합니다. 다음은 특정 값을 가진 노드를 삭제하는 예입니다.

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

단일 연결 목록에서 검색하기

단일 연결 목록에서 특정 값을 검색하려면 해당 값을 찾거나 목록 끝에 도달할 때까지 목록을 순회해야 합니다. 다음은 값을 검색하는 예입니다.

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

단일 연결 목록 뒤집기

단일 연결 목록을 되돌리려면 이전 노드를 가리키도록 각 노드의 참조를 업데이트해야 합니다. 다음은 단일 연결 목록을 뒤집는 예입니다.

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

이중 연결 목록

이중 연결 목록은 단일 연결 목록과 유사하지만 각 노드에는 시퀀스의 다음 노드와 이전 노드에 대한 참조가 모두 포함됩니다. 이를 통해 양방향으로 효율적인 탐색이 가능합니다. Python에서 이중 연결 목록을 만드는 방법은 다음과 같습니다.

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

class DoublyLinked List:
    def __init__(self):
        self.head = None

이중 연결 목록 만들기

이중 연결 목록을 만들기 위해 값, 다음 노드에 대한 참조 및 이전 노드에 대한 참조를 포함하는 Node 클래스를 정의합니다. DoublyLinked List 클래스는 목록의 첫 번째 노드를 가리키는 head 속성을 사용하여 노드의 컨테이너 역할을 합니다.

이중 연결 목록에 노드 삽입

이중 연결 목록에 노드를 삽입하려면 인접 노드의 참조를 업데이트해야 합니다. 다음은 목록 시작 부분에 노드를 삽입하는 예입니다.

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

이중 연결 목록에서 노드 삭제

이중 연결 목록에서 노드를 삭제하려면 인접 노드의 참조를 업데이트해야 합니다. 다음은 특정 값을 가진 노드를 삭제하는 예입니다.

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

이중 연결 목록에서 검색하기

이중 연결 목록에서 특정 값을 검색하려면 값을 찾거나 목록 끝에 도달할 때까지 목록을 어느 방향으로든 탐색해야 합니다. 다음은 값을 검색하는 예입니다.

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

이중 연결 목록 뒤집기

이중 연결 목록을 되돌리려면 다음 포인터와 이전 포인터를 교환하기 위해 각 노드의 참조를 업데이트해야 합니다. 이중 연결 목록을 뒤집는 예는 다음과 같습니다.

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

순환 연결 목록

순환 연결 목록은 마지막 노드가 첫 번째 노드를 다시 가리키며 순환 구조를 만드는 단일 연결 목록의 변형입니다. 이를 통해 목록의 모든 노드에서 효율적인 탐색이 가능합니다. Python에서 순환 연결 목록을 만드는 방법은 다음과 같습니다.

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

class CircularLinked List:
    def __init__(self):
        self.head = None

순환 연결 목록 만들기

순환 연결 목록을 만들기 위해 다음 노드에 대한 참조와 값을 포함하는 Node 클래스를 정의합니다. CircularLinked List 클래스는 목록의 첫 번째 노드를 가리키는 head 속성을 사용하여 노드의 컨테이너 역할을 합니다. 또한 마지막 노드의 다음 참조가 헤드로 설정되어 원형 구조를 만듭니다.

순환 연결 목록에 노드 삽입

순환 연결 목록에 노드를 삽입하려면 인접 노드의 참조를 업데이트해야 합니다. 다음은 목록 시작 부분에 노드를 삽입하는 예입니다.

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

순환 연결 목록에서 노드 삭제

순환 연결 목록에서 노드를 삭제하려면 인접 노드의 참조를 업데이트해야 합니다. 다음은 특정 값을 가진 노드를 삭제하는 예입니다.

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

순환 연결 목록에서 검색하기

순환 연결 목록에서 특정 값을 검색하려면 해당 값을 찾거나 전체 목록을 탐색할 때까지 목록을 탐색해야 합니다. 다음은 값을 검색하는 예입니다.

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

순환 연결 목록 뒤집기

순환 연결 목록을 반전하려면 순환 구조를 반전시키기 위해 각 노드의 참조를 업데이트해야 합니다. 순환 연결 목록을 뒤집는 예는 다음과 같습니다.

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

연결 목록의 일반적인 작업

연결 목록은 요소에 대해 수행할 수 있는 다양한 일반 작업을 지원합니다. 다음 작업 중 일부를 살펴보겠습니다.

연결리스트의 요소에 접근하기

Linked List의 요소에 액세스하려면 헤드 노드부터 시작하여 목록을 탐색하고 원하는 위치에 도달할 때까지 다음 노드로 이동할 수 있습니다. 다음은 특정 인덱스의 요소에 액세스하는 예입니다.

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

연결 목록의 요소 수정

연결 목록의 요소를 수정하려면 목록을 탐색하여 원하는 요소를 찾고 해당 값을 업데이트해야 합니다. 다음은 특정 인덱스의 요소를 수정하는 예입니다.

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

연결리스트의 길이 찾기

연결 목록의 길이를 확인하려면 목록을 탐색하고 노드 수를 계산할 수 있습니다. 다음은 연결 목록의 길이를 찾는 예입니다.

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

연결리스트가 비어 있는지 확인하기

Linked List가 비어 있는지 확인하려면 헤드 노드가 None인지 확인하면 됩니다. Linked List가 비어 있는지 확인하는 예는 다음과 같습니다.

def is_empty(self):
    return self.head is None

연결 목록 연결

두 개의 연결된 목록을 연결하려면 첫 번째 목록을 탐색하여 마지막 노드를 찾고 두 번째 목록의 헤드에 대한 다음 참조를 업데이트할 수 있습니다. 다음은 두 개의 연결 목록을 연결하는 예입니다.

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

연결리스트와 배열

연결된 목록과 배열은 모두 일반적으로 사용되는 데이터 구조이지만 서로 다른 시나리오에 적합하도록 서로 다른 특성을 가지고 있습니다. Linked List와 배열을 메모리 효율성, 삽입 및 삭제 효율성, Random Access 효율성 측면에서 비교해 보겠습니다.

메모리 효율성

연결된 목록은 연속적인 메모리 할당이 필요하지 않기 때문에 배열보다 메모리 효율적입니다. Linked List의 각 노드는 값과 다음 노드에 대한 참조만 저장하면 되는 반면, 배열은 사용되지 않더라도 모든 요소에 대해 메모리를 할당해야 합니다.

삽입 및 삭제 효율성

연결 목록은 삽입 및 삭제 작업에 탁월하며, 특히 목록 중간에 요소가 자주 추가되거나 제거되는 경우 더욱 그렇습니다. Linked List에서 요소를 삽입하거나 삭제하려면 인접 노드의 참조만 업데이트하면 되는 반면, 배열에서는 변경 사항을 수용하기 위해 요소를 이동해야 할 수 있습니다.

무작위 액세스 효율성

배열은 직접 메모리 주소 지정을 허용하므로 인덱스를 기반으로 요소에 대한 효율적인 무작위 액세스를 제공합니다. 대조적으로, 연결된 목록은 특정 인덱스의 요소에 액세스하기 위해 처음부터 목록을 순회해야 하므로 임의 액세스 작업의 성능이 저하됩니다.

올바른 데이터 구조 선택

연결된 목록과 배열 사이의 선택은 애플리케이션의 특정 요구 사항에 따라 달라집니다. 빈번한 수정과 동적 크기 조정이 예상되는 경우 연결 목록이 더 나은 선택입니다. 반면, 랜덤 액세스와 메모리 효율성이 중요하다면 어레이가 더 적합합니다.

연결리스트 애플리케이션

이제 연결 목록과 그 작동 방식을 잘 이해했으므로 연결 목록을 효과적으로 사용할 수 있는 몇 가지 실제 응용 프로그램을 살펴보겠습니다.

당신은 또한 우리의에 등록할 수 있습니다 무료 과정 오늘!

스택 및 대기열 구현

연결 목록의 가장 일반적인 응용 프로그램 중 하나는 스택과 대기열을 구현하는 것입니다. 스택과 큐는 모두 연결된 목록을 사용하여 쉽게 구현할 수 있는 추상 데이터 유형입니다.

스택은 LIFO(Last In First Out) 원칙을 따르는 데이터 구조입니다. 요소는 스택의 맨 위라고 알려진 동일한 끝에서 추가되고 제거됩니다. 연결된 목록은 목록의 헤드에서 요소를 쉽게 추가하거나 제거할 수 있으므로 스택을 구현하는 효율적인 방법을 제공합니다.

다음은 Python에서 연결 목록을 사용하여 스택을 구현하는 예입니다.

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

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

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

반면 대기열은 FIFO(선입선출) 원칙을 따릅니다. 요소는 후면이라고 하는 한쪽 끝에 추가되고 전면이라고 하는 다른 쪽 끝에서 제거됩니다. 연결된 목록을 사용하여 대기열을 효율적으로 구현할 수도 있습니다.

다음은 Python에서 연결 목록을 사용하여 대기열을 구현하는 예입니다.

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

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

대규모 데이터 세트 처리

연결된 목록은 대규모 데이터 세트를 처리할 때도 유용합니다. 배열과 달리 연결된 목록에는 연속적인 메모리 할당이 필요하지 않습니다. 이는 연결 목록이 크기 조정이나 재할당 없이 다양한 크기의 데이터 세트를 효율적으로 처리할 수 있음을 의미합니다.

예를 들어, 수백만 개의 레코드로 구성된 데이터 세트가 있고 삽입, 삭제 또는 순회와 같은 작업을 수행해야 한다고 가정해 보겠습니다. 이 작업에 배열을 사용하면 삽입하거나 삭제할 때 요소를 이동해야 하므로 비효율적일 수 있습니다. 그러나 연결된 목록을 사용하면 포인터를 업데이트하여 요소를 쉽게 삽입하거나 삭제할 수 있으므로 작업 속도가 빨라집니다.

그래프 순회 알고리즘

너비 우선 검색(BFS) 및 깊이 우선 검색(DFS)과 같은 그래프 순회 알고리즘도 연결 목록을 사용하여 구현할 수 있습니다. 그래프 순회에서는 그래프의 각 정점이나 노드를 특정 순서로 방문합니다.

연결된 목록은 그래프의 인접 목록을 나타내는 데 사용할 수 있습니다. 여기서 연결된 목록의 각 노드는 정점을 나타내고 인접한 정점은 연결된 목록 노드로 저장됩니다. 이 표현을 사용하면 그래프를 효율적으로 탐색하고 탐색할 수 있습니다.

다항식 표현

연결된 목록을 사용하면 다항식을 효율적으로 표현할 수 있습니다. 수학에서 다항식은 변수와 계수로 구성된 표현식입니다. 다항식의 각 항은 계수와 지수가 데이터로 저장되는 연결된 목록의 노드로 표시될 수 있습니다.

연결된 목록을 사용하면 덧셈, 뺄셈, 곱셈과 같은 다항식 연산을 쉽게 수행할 수 있습니다. 노드를 조작하여 이러한 작업을 수행할 수 있으므로 다항식을 간결하고 효율적으로 표현할 수 있습니다.

음악 및 비디오 재생 목록

연결 목록은 일반적으로 음악 및 비디오 플레이어에서 재생 목록을 구현하는 데 사용됩니다. 각 노래나 비디오는 연결된 목록의 노드로 표시될 수 있습니다. 여기서 데이터에는 미디어 파일에 대한 정보가 포함되어 있고 포인터는 재생 목록의 다음 노래나 비디오를 가리킵니다.

재생 목록에 연결된 목록을 사용하면 노래나 비디오 사이를 쉽게 탐색할 수 있습니다. 포인터를 업데이트하여 재생 목록에서 노래를 쉽게 추가하거나 제거할 수 있어 원활한 사용자 경험을 제공합니다.

결론

결론적으로 연결된 목록은 다양한 도메인에서 응용 프로그램을 찾는 다목적 데이터 구조입니다. 스택과 큐를 구현하고, 대규모 데이터 세트를 처리하고, 그래프 순회를 수행하고, 다항식을 표현하고, 재생 목록을 만드는 데 사용할 수 있습니다. 연결 목록은 동적 메모리 할당과 손쉬운 노드 조작을 활용하여 이러한 문제에 대한 효율적인 솔루션을 제공합니다.

연결 목록의 적용을 이해함으로써 프로그램의 데이터 구조를 선택할 때 정보에 입각한 결정을 내릴 수 있습니다. 데이터 관리, 알고리즘 구현, 사용자 친화적인 인터페이스 생성 등 연결 목록은 프로그래머의 툴킷에서 귀중한 도구를 제공합니다.

따라서 다음에 효율적인 삽입, 삭제 또는 순회가 필요한 문제가 발생하면 연결 목록을 사용하여 솔루션을 단순화하고 코드를 최적화하는 것이 좋습니다.

여기에서 Python 목록과 관련된 더 많은 기사를 읽을 수도 있습니다.