Python에서 이중 연결 목록 만들기

이 기사에서는 Python 프로그래밍 언어로 이중 연결 목록을 만드는 방법을 보여줍니다.

Python에서 이중 연결 목록 만들기

이중 연결 목록은 노드라고 하는 순차적으로 연결된 레코드 집합으로 구성된 연결된 데이터 구조를 나타냅니다. 각 노드에는 이전 포인터, 다음 포인터 및 데이터 필드가 포함됩니다.

이전 및 다음 포인터는 이전 및 다음 노드를 가리킵니다. 첫 번째 노드의 이전 포인터와 마지막 노드의 다음 포인터는 없음을 가리킵니다.

이중 연결 리스트에서 주어진 노드 앞과 뒤에 새 노드를 삽입할 수 있습니다. 또한 이중 연결 리스트를 앞뒤로 탐색할 수 있습니다.

그러나 모든 이중 연결 리스트 노드에는 이전 포인터를 위한 추가 공간이 필요합니다.

다음과 같이 노드 클래스가 생성됩니다. 포인터와 데이터 값은 기본적으로 없음입니다.

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

그런 다음 이중 연결 목록에 사용되는 클래스가 생성됩니다. self.head는 목록의 헤드를 나타내며 처음에는 None입니다.

add_to_end 기능을 사용하여 이중 연결 목록 끝에 새 노드를 추가합니다. 먼저 new_node 변수를 사용하여 Node 클래스 인스턴스를 만듭니다.

new_node가 목록의 마지막 값이 되므로 다음 포인터를 None으로 설정합니다. new_node를 추가할 노드를 찾기 위해 last 변수를 정의합니다.

첫째, 이 변수는 이중 연결 목록의 헤드입니다(처음 추가된 노드의 경우 이 헤드는 None이 됨).

if 블록에서 self.head가 None인지 확인합니다. 그렇다면 목록에 노드가 없으며 이제 목록의 헤드는 새로 추가된 노드가 됩니다.

while 블록에서 목록의 마지막 값을 찾기 위해 last 변수의 next 포인터를 확인합니다. None이 될 때까지 last 변수를 last.next로 대체합니다.

last.next 값이 None인 노드를 찾으면 목록을 종료합니다.

찾은 last 노드 값의 next 포인터가 new_node를 가리키도록 설정합니다. 마지막으로 new_node 변수의 previous 포인터를 last 변수로 설정합니다.

따라서 이중 연결 리스트의 끝에 new_node 노드가 추가됩니다.

아래 코드를 참조하십시오.

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

    def add_to_end(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = None
        last = self.head

        if self.head is None:
            new_node.previous = None
            self.head = new_node
            return

        while last.next is not None:
            last = last.next

        last.next = new_node
        new_node.previous = last

add_to_beginning 기능을 사용하여 이중 연결 목록의 시작 부분에 노드를 추가할 수 있습니다. 이 프로세스는 더 간단합니다.

먼저 new_node 변수의 next 포인터를 self.head로 설정하고 previous 포인터를 None으로 설정합니다. 따라서 이전 목록의 첫 번째 값인 헤드 값은 new_node가 가리키는 다음 값이 됩니다.

if 블록에서 목록이 비어 있으면 self.head 값이 None인지 확인합니다. 이 값이 정의되어 있거나 헤드에 해당하는 노드가 있는 경우 이 노드의 previous 포인터를 new_node로 변경합니다.

마지막으로 self.head를 new_node로 변경합니다. 따라서 new_node가 이중 연결 목록의 시작 부분에 추가됩니다.

아래 코드 데모를 참조하십시오.

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

    def add_to_end(self, new_node):
        # previous function
        pass

    def add_to_beginning(self, new_node):

        new_node = Node(data=new_node)
        new_node.next = self.head
        new_node.previous = None

        if self.head is not None:
            self.head.previous = new_node

        self.head = new_node

아래 예에서는 doubly_linked_list 변수가 먼저 생성됩니다. 이 변수는 DoublyLinkedList 클래스의 인스턴스입니다.

그런 다음 각각 목록 끝에 1과 3을 추가하고 처음에 5를 추가합니다. 목록의 최종 상태는 5 -> 1 -> 3 -> 없음입니다.

doubly_linked_list = DoublyLinkedList()
doubly_linked_list.add_to_end(1)
doubly_linked_list.add_to_end(3)
doubly_linked_list.add_to_beginning(5)