예제를 사용하여 Python에서 연결 목록 만들기

게시물Building a Linked List in Python with Examples은 Qvault에 처음 등장했습니다.

연결된 목록은 요소가 메모리에 서로 옆에 저장되지 않는 선형 데이터 구조입니다. 연결된 목록의 요소는 포인터 또는 참조를 사용하여 연결됩니다. 연결된 목록은 일반 목록과 유사한 순서가 지정된 객체 모음입니다. 연결된 목록은 요소를 메모리에 저장하는 방식에서 목록과 다릅니다. 일반 목록(배열 또는 슬라이스)은 연속적인 메모리 블록을 사용하여 데이터에 대한 참조를 저장하는 반면 연결 목록은 각 요소의 일부로 참조(포인터)를 저장합니다.

source

일반 목록은 목록의 첫 번째 요소에 대한 포인터일 뿐이며 메모리 오프셋을 제공하여 특정 항목을 검색할 수 있습니다.

연결된 목록도 목록의 첫 번째 요소에 대한 포인터일 뿐이지만 메모리 오프셋은 아무 소용이 없습니다. 첫 번째 요소next의 포인터를 검사하여 다음 항목이 어디에 있는지 확인한 다음 탐색할 수 있습니다. 거기에서 목록 아래로 다음 항목 등을 찾을 수 있습니다.

파이썬 연결 리스트 예제

노드 클래스

먼저 Node 클래스를 빌드합니다. 우리가 결국 구축하는 LinkedList 클래스는 Node 의 목록이 될 것입니다.

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

    def set_next(self, node):
        self.next = node

    def  __repr__ (self):
        return self.val

각 노드에는 val 데이터 구성원(저장하는 정보)과 next 데이터 구성원이 있습니다. next 데이터 멤버는 목록에 있는 경우 다음Node을 가리키고, 그렇지 않으면 None입니다.

연결된 목록 클래스 생성자

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

생성자는 간단합니다. 빈head 포인터를 초기화하기만 하면 됩니다. 이는 이제 빈 목록이 있음을 나타냅니다.

목록 반복

파이썬for _ in _ 구문을 사용하여 목록의 각 항목을 쉽게 반복하도록 합시다.

def  __iter__ (self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

Python__iter__ 메서드를 구현하여 이제 반복 구문을 사용할 수 있습니다. 예: for item in linked_list: .

목록에 추가

목록의 끝에 항목을 추가하는 방법인 add_to_tail 메서드를 만들어 봅시다. 노드를 입력으로 사용하고 전체 목록을 반복한 다음 지정된 노드를 끝에 추가합니다.

def add_to_tail(self, node):
        if self.head == None:
            self.head = node
            return
        for current_node in self:
            pass
        current_node.set_next(node)

목록에서 제거

목록에서 항목을 제거하는 다른 방법이 있지만 지금은 예를 들어 remove from head 메서드를 작성해 보겠습니다.

def remove_from_head(self):
        if self.head == None:
            return None
        temp = self.head
        self.head = self.head.next
        return temp

remove_from_head 목록에서 첫 번째 항목이 있다고 가정하고 제거하고 반환합니다.

연결된 목록 인쇄

마지막으로 Python의 __repr__ () 메서드를 구현하여 목록에서 직접 print()를 호출하고 출력 내용을 제어할 수 있습니다. 내가 좋아하는 표현은 다음과 같습니다.

def  __repr__ (self):
        nodes = []
        for node in self:
            nodes.append(node.val)
        return " -> ".join(nodes)

이 메서드는 각 노드의 값을 순서대로 인쇄하고 사이에 화살표를 표시합니다. 예: hello -> this -> is -> my -> list .

용법

linked_list = LinkedList()
linked_list.add_to_tail(Node('john'))
linked_list.add_to_tail(Node('sally'))
linked_list.add_to_tail(Node('jimmy'))
print("ll:", linked_list)
first = linked_list.remove_from_head()
print("removed:", first)
print("ll:", linked_list)

전체 연결 목록 코드 예제

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

    def  __iter__ (self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

    def  __repr__ (self):
        nodes = []
        for node in self:
            nodes.append(node.val)
        return " -> ".join(nodes)

    def add_to_tail(self, node):
        if self.head == None:
            self.head = node
            return
        for current_node in self:
            pass
        current_node.set_next(node)

    def remove_from_head(self):
        if self.head == None:
            return None
        temp = self.head
        self.head = self.head.next
        return temp

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

    def set_next(self, node):
        self.next = node

    def  __repr__ (self):
        return self.val

읽어 주셔서 감사합니다!

테이크computer science courses on our new platform

질문이나 의견이 있으면 Twitter를 팔로우하고 연락하십시오.

Subscribe 더 많은 프로그래밍 기사를 보려면 뉴스레터로