이중 연결리스트와 파이썬 3에서 그것들을 구현하는 방법

연결된 목록은 데이터를 저장하는 선형 방식입니다. 데이터를 포함하는 노드와 다음 데이터를 얻는 방법에 대한 포인터로 구성됩니다. 노드를 체인의 구성원으로 생각하십시오. 각 체인은 서로 강한 유대 관계를 유지하기 위해 서로 의존합니다. 예를 들어, 중간 링크에 실패한 후 모든 것이 누락 된 경우. 더 이상 완전한 체인이 아닙니다! 이것이 링크 된 목록으로 어떻게 변환됩니까? 포인터 중 하나가 없거나 올바르지 않은 경우 나머지 데이터를 더 이상 읽을 수 없습니다.

유효한 체인이 아닙니다! 연결리스트가 끊어집니다!

그러나이 기사의 주제는 다목적 버전의 연결 목록 (이중 연결 목록)에 있습니다. 일반 (또는 단독으로) 연결된 목록과 비교하여 이중 연결 목록에는 이전이라는 다른 포인터가 포함됩니다. 짐작할 수 있듯이 이전 노드의 위치를 ​​노드가 알 수 있습니다. 이에 비해, 단일 링크리스트는 동일한 포인트에 도달하기 위해 전체리스트를 이전리스트로 다시 이동해야합니다.

단독으로 연결된 목록에 대한 정보는 다음 반 친구의 기사를 방문하십시오.

앞에서 언급했듯이 노드는 메모리의 다른 위치를 가리 킵니다. 그게 무슨 뜻이야? 인접한 위치에 저장된 배열과 달리 연결된 목록에는 포인터가 있습니다. 아래 다이어그램에서 각 메모리 블록 (빨간색)에는 두 개의 포인터가 있습니다. 다음 포인터 (검은 색)를보고 해당 정보에 액세스합니다. 이전 블록을 찾으려면 이전 포인터 (흰색)를 봅니다.

그렇다면 이중 연결 목록은 어떻게 구현합니까? 파이썬 3의 사용법은 다음과 같습니다.

Node 클래스에 .prev를 추가하기 만하면됩니다. 이제 구현을 시작할 준비가되었습니다!

장점 — Python 3 코드 사용!

단일 연결 목록에 비해 이중 연결 목록의 장점은 무엇입니까? 이중으로 연결된 목록을 사용하면 노드간에 앞뒤로 이동할 수 있습니다. 이렇게하면 삽입이 정말 쉬워집니다. 이중 연결 목록을 사용하면 연결 목록을 원하는 노드로 이동 한 다음 이전 노드를 호출하면됩니다.

단점

링크 된 목록에 대한 좋은 점이 있지만 모든 것을 해결할 수있는 솔루션은 아닙니다. 많은 데이터 구조 및 알고리즘과 마찬가지로이 도구는 무기고의 도구 여야합니다. 단일 연결 목록의 단점 중 하나는 이중 연결 목록의 각 링크가 이전 포인터를 추적해야하므로 메모리 소비가 더 많다는 것입니다. 또한, 상기 포인터를 추적하는 것은 어렵다.

실제로는 여전히 구현을 구현하고 있습니다. 이것은이 기사 (2019 년 4 월)를 쓰는 시점에서 두 번째로 성공적으로 구현되었을 것입니다. 매번 약간 쉬워 지지만 여전히 이전 포인터가 다른 모든 함수와 상호 작용하는 방식에 대한 다이어그램을 그려야합니다.

그러나 이것은 무엇을 위해 사용됩니까?

당신이 묻는 소리가 들립니다. 이전과 다음을 본 적이 있다면 생각해보십시오. 그들이 구현할 수있는 명백하고 미묘한 방법이 있습니다.

출처 : https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

뮤직 플레이어와 같은 경우는 어떻습니까? 매우 명백한 다음 및 이전 버튼이 있습니다. 이중 링크 된 목록을 사용하여 두 노래 사이를 순환 할 수 있습니다.

아니면 브라우저는 어떻습니까? 여기에는 방문한 웹 페이지간에 앞뒤로 이동할 수있는 명시적인 방법이 있습니다.

이제 워드 프로세싱 소프트웨어 또는 선택한 사진 편집기에 대해 생각해보십시오. 실수를 할 때마다 CTRL (Mac의 경우 CMD) + Z를 눌러 마지막 작업을 취소 할 수 있습니다. 마찬가지로 CTRL (Mac 용 CMD) + Y로 실행 취소 한 항목을 다시 실행할 수 있습니다. 이제이 소리가 익숙한 이유는 무엇입니까? 이중 연결 목록으로 구현할 수도 있습니다! 이전 포인터는 너무 많이 실행 취소하면 작업을 다시 실행할 수있는 동안 수행 된 작업을 가리 킵니다.

출처 : https://gfycat.com/brilliantbeautifuldassie출처 : https://www.solitairecardgames.com/how-to-play-solitaire

내가 생각했던 덜 명백한 구현은 게임 솔리테어였습니다. 옆에는 나의 요점을 설명하는 데 도움이되는 솔리테어 용어의 이미지가 있습니다.

이 게임은 tableau 또는 폐기물 더미에 있든 이전 및 다음 카드를 지속적으로 볼 수 있어야하는 빛나는 예입니다. 폐기물 더미에서 탁자까지 카드를 재생하면 폐기물 더미가 이전 카드로 업데이트됩니다.

이중 연결 목록에 대한 사용에 대해보다 활발하게 토론하려면 stackoverflow에서이 토론을 살펴 보는 것이 좋습니다.

다음에 링크 된 목록을 구현할 때 이중 링크 된 목록을 사용해보십시오. 링크 된 목록 위에는 더 많은 코드가 아니며 많은 이점이 있습니다!

추가 자료

이중 연결 목록의 Python 3 구현에 대한 전체 링크는 Github 저장소에서 찾을 수 있습니다.

이중 연결 목록의 3D 인쇄 가능한 체인을 원한다면 Thingiverse에 업로드했습니다.

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ