Python에서 연결 목록을 사용하여 사전 목록 모방
- DDD원래의
- 2024-11-07 18:56:03686검색
이 글은 저의 사고 과정과 시각화로 시작하겠습니다. 연결된 목록이 무엇인지에 대해 더 명확하게 알 수 있도록 눈을 뜨게 한 실험(그렇게 부르도록 선택할 수 있음)입니다. 항상 설명되는 진부한 방식(데이터 및 다음)을 따르지 않고 추상적으로 보지 않게 되었습니다.
사고 과정과 시각화
최근에는 좀 더 물리적인 관점(일반적으로 OOP라고 함)에서 코드를 보기 시작했습니다. 그러나 내 것은 클래스와 속성을 뛰어 넘습니다. 나는 매 while과 for-loop 이전에 단계와 알고리즘을 작성하기 시작했습니다. 단지 목적을 위해 추상화에 뛰어드는 것에 지쳤습니다. 이로 인해 몇 가지를 더 시도하게 되었고 이 기사에서 공유할 몇 가지 사항을 더 배울 수 있게 되었습니다.
더 자세히 알아보기 전에 세 가지 주요 질문과 답변:
- 연결리스트는 어떻게 구성되나요?
- 노드는 어떻게 생겼나요?
- 연결 목록은 처음에는 어떤 모습인가요?
먼저 대답하자면; 노드는 연결리스트를 구성합니다.
두 번째 질문입니다. 다른 차를 견인하는 자동차와 같은 연결 리스트의 노드를 생각해 보세요. 이 시나리오에서는 두 차량 모두에 상품이 포함되어 있다고 가정합니다. 두 번째 차량은 첫 번째 차량의 뒤쪽에 체인으로 연결되어 있습니다. 노드는 자동차에 있는 상품 또는 승객과 같은 데이터를 보유하여 연결 목록에서 이를 수행합니다. 이 데이터 유형은 정수나 문자열처럼 단순할 수도 있고 더 복잡한 데이터 구조일 수도 있습니다. 동시에 각 차량에는 도로의 다음 차량과 연결하는 커넥터(체인)가 있습니다. 연결 리스트에서 이것은 다음 노드 또는 이전 노드(이중 연결 리스트에서)의 메모리 주소를 가리키는 다음 속성입니다. 목록은 다음 속성이 없으면 연결 목록이 아닙니다.
각 자동차는 바로 앞이나 뒤에 있는 자동차에 대해서만 알고 있습니다(링크된 목록의 유형에 따라 다름). 마지막 차에는 체인이 없습니다. 즉, 아무 것도 가리키지 않습니다. 연결 목록에서는 None으로 표시되는 경우가 많습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
세 번째 질문에 답하자면, 첫 번째 자동차가 견인을 시작하는 것처럼 헤드 노드는 연결 목록을 시작합니다.
class LinkedList:
def __init__(self):
self.head = None
지금까지 연결리스트의 기본을 살펴보았습니다. 이제 제가 이 글을 쓴 주요 이유에 대해 알아보겠습니다.
소개
목록 및 사전과 같은 Python에 내장된 데이터 구조는 데이터를 저장하고 관리하는 유연한 방법을 제공합니다. 목록을 사용하면 순서가 지정된 시퀀스를 저장할 수 있고 사전을 사용하면 쉽게 액세스할 수 있도록 키와 값을 쌍으로 연결할 수 있습니다.
이 기사에서는 구성을 사용하여 사전과 같은 연결 목록을 만드는 방법을 살펴보겠습니다. 우리는 사전과 같은 연결 목록과 사전 목록 사이의 메모리 사용에 있어서 차이를 보게 될 것입니다. 또한 노드 인스턴스를 실제 사전으로 만들기 위해 노드가 dict에서 상속을 얻는 방법도 살펴보겠습니다. 이 모든 것은 연결 목록을 이해하는 데 더 많은 관점을 제공하기 위한 것입니다.
연결 목록 만들기
앞서 살펴본 것처럼 연결 목록은 노드로 구성됩니다. 이러한 노드에는 각각 데이터 세그먼트와 다음 세그먼트가 있습니다. 데이터는 문자열이나 정수처럼 단순할 수도 있고, 복잡한 것일 수도 있습니다.
간단함:
class Node:
def __init__(self, data):
self.data = data
self.next = None
My_Int로 표현되는 Node 클래스에는 데이터와 다음 속성이 있습니다.
class LinkedList:
def __init__(self):
self.head = None
이 기사에서는 복잡한 사건을 다룰 예정입니다:
복합:
class My_Int:
def __init__(self, data):
self.data=data
self.next=None
My_Dict로 표시되는 노드 클래스는 사용자 이름, 안색 및 다음과 같은 여러 속성을 보유합니다. **kwargs를 인수로 사용하면 메소드가 각 키워드 인수를 명시적으로 정의하지 않고도 원하는 수의 키워드 인수를 허용할 수 있습니다.
각 노드는 단지 단일 데이터 조각을 저장하는 것이 아니라 여러 조각(사용자 이름 및 안색)을 하나로 결합하므로 정수나 문자열과 같은 기본 데이터 구조보다 더 복잡합니다.
이제 My_Dict 인스턴스의 연결 목록을 관리하는 My_List 클래스를 생성하겠습니다. 헤드 속성을 사용합니다. 이 헤드는 일반적으로 연결 목록을 초기화하는 첫 번째 노드입니다.
class My_Int:
def __init__(self, data):
self.data=data
self.next=None
class LinkedList:
def __init__(self):
self.head=None
def insert(self, node):
if self.head==None:
self.head = node
return
last_node = self.head
while(last_node.next):
last_node =last_node.next
last_node.next = node
def traverse(self):
current_node = self.head
while(current_node):
print(current_node.data, end="->")
current_node = current_node.next
print("None")
node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)
linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()
이 클래스는 마지막에 새 노드 항목을 추가하기 위한 삽입 메소드도 제공합니다.
또한 여기(노드)에 My_Dict 인스턴스를 생성합니다. My_List는 연결된 목록 구조에서 My_Dict 개체에 대한 컨테이너 역할을 합니다. 각 My_Dict 인스턴스는 My_List가 My_Dict 인스턴스의 순회 및 삽입을 동적으로 관리할 수 있도록 하는 다음 참조로 연결됩니다. 이는 기본적으로 구성의 예시입니다.
My_Dict 인스턴스를 생성한 후 헤드가 있는지 확인하여 목록이 비어 있지 않은지 확인합니다. 헤드가 없으면 목록이 비어 있다는 의미이므로 self.head를 새 노드(my_dict)로 초기화합니다. 그런 다음 반환은 즉시 함수를 종료합니다. 더 이상 실행할 필요가 없습니다.
class My_Dict: #dict keys as attributes
def __init__(self, **kwargs):
self.username = kwargs['username']
self.complexion = kwargs['complexion']
self.next = None
return 뒤의 줄은 목록에 이전에 노드가 있었고 새 노드를 삽입하려고 할 때 실행됩니다. 해당 노드 last_dict를 head로 초기화하고 이는 새 노드가 추가될 수 있도록 마지막 노드(목록의 끝)를 찾는 데 사용됩니다. while 루프는 마지막 노드에 도달할 때까지 목록을 반복합니다. last_dict.next가 None이 아닌 한 last_dict = lastdict.next를 설정하여 다음 노드로 이동합니다.
마지막으로 last_dict.next = my_dict는 삽입을 완료하는 목록 끝에 my_dict를 추가합니다. last_dict.next가 None이라는 것을 알게 되면(즉, 마지막 노드에 있음) 거기에 my_dict를 연결합니다.
이제 횡단 기능을 다룹니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
traverse 함수는 연결된 목록의 각 노드를 반복하고 각 노드에서 헤드부터 끝까지 작업(이 경우 인쇄)을 수행합니다. 이 방법은 목록의 모든 노드에 대한 순차적 보기를 제공합니다.
아래에서 전체 코드를 살펴보세요.
class LinkedList:
def __init__(self):
self.head = None
class My_Int:
def __init__(self, data):
self.data=data
self.next=None
위의 구현은 사전과 같은 객체의 사용자 지정 연결 목록으로 생각할 수 있지만 표준 Python의 일반적인 사전 목록과 구조가 다릅니다. 주의할 점은 다음과 같습니다.
- My_Dict 클래스: 각 인스턴스는 속성(사용자 이름 및 안색)과 다음 포인터가 있는 사전과 같은 개체 역할을 하여 다른 My_Dict 인스턴스에 연결할 수 있습니다.
- My_List 클래스: 이 클래스는 My_Dict 인스턴스의 연결된 목록을 관리하고 헤드를 유지하며 끝에 새 항목을 추가하는 삽입 메서드를 제공합니다. 각 노드는 다음 포인터를 통해 다음 노드에 연결되어 연결리스트 구조를 시뮬레이션합니다.
알고리즘
코드를 작성할 때 알고리즘을 사용하는 것은 항상 좋습니다. 이는 취해진 조치로 알려져 있습니다. 어쩌면 위의 코드보다 먼저 작성했어야 했을 수도 있습니다. 하지만 저는 단지 일상적인 진부한 연결 목록과 더 복잡한 유형의 차이점을 먼저 보여주고 싶었습니다. 더 이상 고민하지 말고 다음 단계를 따르세요.
- 노드 구조의 속성을 갖는 클래스를 생성합니다.
- LinkedList(또는 무엇이든)라는 또 다른 클래스를 만듭니다. 헤드를 유일한 속성으로 추가합니다. 머리를 없음으로 설정하세요.
- 노드를 생성하고 삽입하려면:
- Node 인스턴스를 만듭니다.
- 목록이 비어 있으면 노드 인스턴스를 head 값으로 둡니다.
- 목록이 비어 있지 않으면 이전 노드의 값을 head로 설정하세요.
- 상태 확인은 다음과 같습니다. 이전 노드의 다음 속성이 None이 아니면 목록을 반복합니다.
- 마지막으로 이전 노드의 다음 노드가 새 노드를 가리키도록 설정합니다.
- 목록을 탐색하려면:
- 임시 노드를 생성하고 head를 시작 값으로 설정합니다.
- 임시 노드가 None이 아닌 경우를 조건으로 반복합니다.
- 임시 노드에 데이터를 인쇄합니다.
- 임시 노드를 다음 노드로 이동
- 마지막으로 다음은 None이므로 None을 인쇄하세요.
- 필요에 따라 클래스 인스턴스를 생성하세요.
사전 목록과 비교
이제 몇 가지 사항을 살펴봄으로써 위에 있는 내용을 Python 사전 목록과 비교할 것입니다.
- 구조 및 저장:
사전 목록: Python에서 사전 목록은 각 사전을 연속 목록 구조의 요소로 저장하므로 인덱스를 통해 각 사전에 액세스할 수 있습니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
사전의 연결 목록: 우리 코드는 각 노드(사전과 유사한 My_Dict 인스턴스)가 연속 메모리 저장소를 사용하는 대신 다음 노드에 대한 참조를 보유하는 연결 목록 구조를 사용합니다. 이는 요소가 자주 변경되는 대규모 목록의 경우 메모리 효율적이지만 위치별 액세스에는 속도가 느립니다.
- 액세스 및 삽입: 사전 목록: 표준 Python 목록에서 색인으로 요소에 액세스하는 것은 O(1)(상수 시간)입니다. 왜냐하면 Python 목록은 내부적으로 배열이기 때문입니다. 끝에 새 사전을 추가하는 것은 일반적으로 O(1)이지만 크기 조정이 필요한 경우 O(n)이 됩니다.
사전의 연결 목록: 연결 목록에서 요소에 액세스하려면 노드별로 반복해야 하므로 순회(O(n) 시간)가 필요합니다. 마지막에 삽입하는 것도 매번 마지막 노드를 찾아야 하기 때문에 O(n)입니다. 그러나 새 노드를 헤드로 설정할 수 있으므로 시작 부분에 삽입하는 것은 O(1)이 될 수 있습니다.
- 메모리 사용량:
사전 목록: Python 목록은 각 항목이 순차적으로 저장되므로 연속 블록에 사전을 저장하는 데 더 많은 메모리를 사용합니다. 메모리는 Python 목록에 대해 동적으로 할당되며 때로는 목록이 커지면 크기를 조정하고 복사합니다. sys 모듈을 사용하여 코드에서 이를 증명할 수 있습니다:
class LinkedList:
def __init__(self):
self.head = None
class My_Int:
def __init__(self, data):
self.data=data
self.next=None
사전의 연결 목록: 연결 목록은 필요한 만큼만 메모리를 할당하므로 각 노드에 대해 메모리를 효율적으로 사용합니다. 그러나 각 노드에서 다음 참조를 위해 추가 공간이 필요합니다.
class My_Int:
def __init__(self, data):
self.data=data
self.next=None
class LinkedList:
def __init__(self):
self.head=None
def insert(self, node):
if self.head==None:
self.head = node
return
last_node = self.head
while(last_node.next):
last_node =last_node.next
last_node.next = node
def traverse(self):
current_node = self.head
while(current_node):
print(current_node.data, end="->")
current_node = current_node.next
print("None")
node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)
linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()
class My_Dict: #dict keys as attributes
def __init__(self, **kwargs):
self.username = kwargs['username']
self.complexion = kwargs['complexion']
self.next = None
위에서 바이트 단위의 차이를 확인할 수 있습니다. 776과 192.
기술적으로 사전이 아님
우리 코드에서 My_Dict 인스턴스는 실제 사전이 아니라 사전과 유사한 객체입니다.
그 이유는 다음과 같습니다.
-
다음 속성은 My_Dict 인스턴스를 함께 연결하여 독립형 사전보다는 연결 목록의 노드와 더 유사하게 만듭니다. 다음 속성은 일반 사전에서 찾을 수 있는 기능이 아닙니다.
- 방법 및 동작: My_Dict 인스턴스와 같은 사전과 유사한 개체는 사전과 유사하지만 기술적으로는 사전이 아닌 메서드와 동작을 가질 수 있습니다. .keys(), .values(), .items()와 같은 메서드와 해싱과 같은 사전 관련 작업이 부족합니다. My_Dict 개체가 사전처럼 작동하도록 하려면 Python의 내장 dict에서 상속하여 사전 기능을 제공하는 메서드를 구현하면 됩니다. 그러나 현재 상태로는 이러한 객체는 키-값 스타일로 데이터를 저장하지만 Python 사전에서 상속받지 않거나 정확하게 동작하지 않기 때문에 사전과 유사합니다.
다음은 dict 클래스에서 상속하는 방법을 보여줍니다.
class My_List: #manager
def __init__(self):
self.head=None
def insert(self, **kwargs):
my_dict = My_Dict(**kwargs) #instantiate dict
#check if list is empty
if self.head==None:
self.head=my_dict
return
last_dict = self.head
while(last_dict.next):
last_dict = last_dict.next
last_dict.next = my_dict #makes the insertion dynamic
첫 번째 줄은 Python의 타이핑 모듈에서 Dict를 가져옵니다. 이는 My_Dict가 전문 사전임을 나타냅니다.
class Node:
def __init__(self, data):
self.data = data
self.next = None
My_Dict 클래스는 dict에서 상속됩니다. 즉, 사전의 속성을 가지지만 사용자 정의할 수 있습니다.
class LinkedList:
def __init__(self):
self.head = None
생성자를 살펴보겠습니다.
class My_Int:
def __init__(self, data):
self.data=data
self.next=None
__init__은 사용자 이름 및 안색 속성을 사용하여 My_Dict의 인스턴스를 초기화합니다. super().__init_()는 상위 Dict 클래스 생성자를 호출합니다. self['username'] = 사용자 이름 및 self['complexion'] = complexion 사용자 이름과 피부색을 사전 항목으로 저장하여 My_Dict 인스턴스에 사전처럼 액세스할 수 있도록 합니다(예: new_dict['username']).
도 있습니다
다음 속성은 None으로 초기화되어 각 My_Dict 인스턴스가 다른 인스턴스에 연결되도록 허용하여 연결된 목록 구조를 설정합니다.
class My_Int:
def __init__(self, data):
self.data=data
self.next=None
class LinkedList:
def __init__(self):
self.head=None
def insert(self, node):
if self.head==None:
self.head = node
return
last_node = self.head
while(last_node.next):
last_node =last_node.next
last_node.next = node
def traverse(self):
current_node = self.head
while(current_node):
print(current_node.data, end="->")
current_node = current_node.next
print("None")
node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)
linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()
위 메서드는 dict의 키 메서드를 재정의하여 My_Dict의 모든 키를 반환할 수 있도록 합니다. super().keys()를 사용하면 상위 호출
key() 메서드를 사용하여 표준 사전 동작을 보장합니다.
class My_Dict: #dict keys as attributes
def __init__(self, **kwargs):
self.username = kwargs['username']
self.complexion = kwargs['complexion']
self.next = None
MyList 클래스 삽입 메소드에서 생성된 사전 인스턴스가 사전 동작을 나타내도록 만드는 방법을 확인할 수 있습니다. 우리는 여기에 key() 메소드를 연결하고 이를 통해 사용자 이름 키도 평가합니다. if 및 else 블록에서 이 작업을 수행합니다. if 블록에서는 헤드 노드의 키와 사용자 이름을 인쇄합니다. else 블록에서는 다른 노드의 키와 다른 노드의 사용자 이름을 인쇄합니다.
class My_List: #manager
def __init__(self):
self.head=None
위의 사전 이해 내부 탐색 방법에서:
def insert(self, **kwargs):
my_dict = My_Dict(**kwargs) #instantiate dict
#check if list is empty
if self.head==None:
self.head=my_dict
return
last_dict = self.head
while(last_dict.next):
last_dict = last_dict.next
last_dict.next = my_dict #makes the insertion dynamic
current_dict의 각 키-값 쌍으로 사전을 구성합니다. current_dict = getattr(current_dict, 'next', None)은 current_dict가 None이 될 때까지 계속해서 다음 노드로 이동합니다.
참고: 메모리 사용과 관련하여 클래스를 dict에서 상속하도록 하면 메모리 사용이 더 많아집니다. 앞서 만든 사전형 노드의 연결 리스트와는 다릅니다.
결론
이 기사의 목적은 연결 목록이 무엇인지에 대해 제가 일반적으로 설명하는 것 이상으로 더 많은 관점과 통찰력을 제공하는 것입니다. 나는 혁신적이지 않았습니다. 나는 코드가 너무 추상적이라고 생각하는 사람들에게 더 많은 통찰력을 제공하기 위해 코드를 실험하고 있었습니다. 그러나 더 많은 선배 프로그래머들로부터 사용하거나 과거에 사용했을 때의 단점이 무엇인지 알고 싶습니다.
위 내용은 Python에서 연결 목록을 사용하여 사전 목록 모방의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!