지속적이고 불변적인 Java LinkedList

이 기사에서 우리는
를 사용하여 Java에서 LinkedList의 지속적이고 불변적인 변형을 구현할 것입니다. 시간과 공간 효율성 향상을 위한 부분적 구조 공유.

소개

LinkedList 란 무엇입니까?

연결된 목록은 각 노드가 값과 시퀀스의 다음 노드에 대한 참조를 포함하는 노드 모음으로 구성된 데이터 구조입니다. 목록의 헤드에 요소를 추가하거나 헤드에서 요소를 제거하는 것과 같은 작업은 O(1) 작업입니다. 그러나 목록 끝에 요소를 추가하거나 끝에서 요소를 제거하는 것과 같은 작업은 O(n) 작업입니다. 여기서 n은 목록에 있는 요소 수입니다.

불변의 LinkedList가 필요한 이유

함수형 프로그래밍에서는 불변성이 핵심 개념입니다. 불변성은 일단 데이터 구조가 생성되면, 수정할 수 없습니다. 대신 수정 사항이 포함된 새로운 데이터 구조가 생성되며 원본은 변경되지 않은 상태로 유지됩니다.

이 속성은 다음과 같은 여러 가지 이점을 제공합니다.

1. 스레드 안전성: 데이터 구조는 변경할 수 없으므로 동기화할 필요 없이 여러 스레드에서 공유할 수 있습니다.
2. 예측 가능성: 데이터 구조는 불변이므로 언제든지 데이터 구조의 상태를 추론할 수 있습니다.
3. Undo: 데이터 구조는 변경할 수 없으므로 이전 버전의 데이터 구조를 사용하여 언제든지 이전 상태로 되돌릴 수 있습니다.
4. 디버깅: 불변성은 데이터 구조를 수정할 수 없기 때문에 디버깅을 더 쉽게 만듭니다.

그러나 이 기사의 초점은 LinkedList에 있으므로 Java의 컬렉션은 기본적으로 변경 가능합니다. 이유는 다양할 수 있습니다

컬렉션을 디자인할 때 나중에 고려하지 않는 것부터
에 내재된 성능상의 이유까지 다양합니다. 불변의 데이터 구조.

수정 불가능한 JDK 컬렉션과 이 LinkedList의 차이점

JDK는 원본 컬렉션을 감싸는 수정 불가능한 컬렉션을 제공합니다. 불변성을 지원하지만 지속성이 없으며 진정한 유형의 안전한 방법을 제공하지도 않습니다. 그것들은 원래 컬렉션의 포장지이며

수정 작업이 호출되면 예외가 발생합니다. 이는 런타임에 UnsupportedOperationException을 발생시키기 어렵게 하면서 데이터 구조를 전혀 수정할 수 없는 불변성과는 다릅니다.

지속성 대 불변성

영속성과 불변성이라는 용어는 종종 같은 의미로 사용되지만 의미는 다릅니다. 불변성은 데이터 구조의 수정을 허용하지 않는 반면, 지속성은 수정 시 데이터 구조의 공유를 허용합니다. 이는 데이터 구조가 수정되면(즉, 새 버전이 생성됨) 이전 데이터 구조의 일부를 새 데이터 구조와 공유하여 시간 및 공간 효율성을 높일 수 있음을 의미합니다. 이 기술을

구조적 공유라고 합니다.

데이터 구조의 지속성을 달성하는 방법에는 여러 가지가 있습니다. 데이터 구조는 AVL 또는 Red-Black 트리와 같은 균형 트리를 사용하는 간단한 것부터 핑거 트리 및 기수 기반 균형 트리와 같은 더 복잡한 것까지 다양합니다.

이 기사에서는 부분적인 구조 공유를 통해 지속적이고 불변적인 LinkedList의 더 간단한 버전을 구현할 것입니다. 그 이유는 LinkedList가 간단한 데이터 구조이고 불변성과 지속성의 개념을 더 잘 이해하는 데 도움이 되며 일반적으로 더 복잡한 데이터 구조의 구현은 본질적으로 어려운 작업이기 때문입니다.

구현

아래에서는 단계별 접근 방식을 사용하여 Java에서 지속적이고 불변적인 단일 LinkedList를 구현하겠습니다.

Java에 대한 함수형 프로그래밍 둘러보기에 도움이 되는 완전한 구현과 추가 모나드 및 유틸리티를 보려면 이 멋진 작은 라이브러리 FunctionalUtils를 확인하세요.

LinkedList에 지정할 이름은 SeqList가 될 것이며 일반 클래스가 될 것입니다.

먼저 목록에서 지원할 작업에 대해 생각해야 합니다.

O(1) 작업이 될 목록의 선두에 추가됩니다.
요소가 끝에 있는 경우 최악의 경우 O(n) 연산이 발생하는 목록에서 요소를 제거합니다.
목록의 임의 위치에 추가됩니다.
조건어에 따라 요소를 필터링/필터링하는 필터링 작업
Map 및 FlatMap 작업을 통해 목록을 모나드로 변환하여 더 쉽게 함수를 구성할 수 있습니다.

LinkedList는 각 노드가 다음으로 구성된 노드로 구성된 구조로 생각할 수 있습니다.

1. head 가치를 담고 있습니다.
2. tail 나머지 목록은 목록 끝까지 머리와 꼬리로 구성된 LinkedList입니다.
3. 목록의 끝은 빈 LinkedList로 표시됩니다. 이는 머리와 꼬리가 모두 null임을 의미합니다.

전체 구현은 여기에서 확인할 수 있습니다

목록의 마지막 요소가 빈 LinkedList이고 각 요소가 머리와 꼬리가 있는 노드라는 점을 고려하면 LinkedList를 두 클래스로 구성된 재귀 데이터 구조로 나타낼 수 있습니다.

으아악

Cons는 Construct라는 함수형 프로그래밍 용어로 Lisp 프로그래밍 언어로 거슬러 올라갑니다.

위 내용을 바탕으로 다음과 같이 SeqList 인터페이스를 구현할 수 있습니다.

으아악

위에 쓴 내용을 분석해 보겠습니다.

1. LinkedList의 인터페이스가 될 봉인된 인터페이스 SeqList를 만들었습니다.
2. empty() 메소드는 빈 클래스의 인스턴스인 빈 목록을 생성합니다.
3. add() 메소드는 요소를 목록 앞에 추가합니다. 주어진 요소와 현재 목록을 사용하여 새 노드를 생성하기 때문에 이 방법의 복잡성은 O(1)입니다. 이 방법은 새 목록이 현재 목록의 꼬리를 공유하므로 구조적 공유를 사용합니다.
4. () 메서드는 주어진 요소로 새 목록을 만듭니다. 이 방법의 복잡도는 O(n)입니다. 여기서 n은 요소 수입니다. 분명한 것처럼 마지막 요소부터 시작하여 목록에 추가합니다. 이는 요소의 순서를 유지하고 싶기 때문입니다.

남은 운영을 구현해야 합니다. 제거 작업부터 시작하겠습니다:

으아악

또한 하위 클래스에 tail() 메서드와 기타 유용한 메서드를 추가로 구현합니다.

으아악

remove 메소드의 구현을 검토할 수 있듯이 재귀 호출을 사용하여 요소를 제거합니다
목록. 이는 재귀를 사용하여 목록을 탐색하고
요소를 제거하십시오. 목록이 무한할 경우 스택 오버플로를 방지하도록 주의해야 합니다. 향후 개선 사항은 Java에서는 지원되지 않지만 트램폴린을 사용하여 달성할 수 있는 꼬리 재귀 최적화를 사용하는 것입니다.

마지막으로, 목록을 모나드로 변환하기 위해 map 및 flatMap 작업을 구현해 보겠습니다.

으아악

map 및 flatMap 메소드의 구현에서 볼 수 있듯이 우리는 재귀 호출을 사용하여 목록을 탐색하고 각 요소에 함수를 적용합니다. flatMap 메소드는 목록의 나머지 부분과 연결해야 하는 새 목록을 반환하는 함수가 필요하기 때문에 조금 더 복잡합니다. 두 방법 모두 악명 높은 어려움과 고급 데이터 구조 사용의 중요성으로 인해 구조적 공유를 사용하지 않습니다. 향후 개선 사항은 향후 기사에서 검토할 예정입니다.

사용 예

SeqList의 몇 가지 사용 예를 살펴보겠습니다.

• 정수 목록이 있고 짝수를 필터링한 다음 불변성과 지속성을 유지하면서 2의 거듭제곱으로 곱하고 싶다고 상상해 보세요.

으아악

• 문자열 목록이 있고 이를 접두사와 접미사로 연결하려고 한다고 상상해 보세요.

으아악

• 목록 목록이 있고 이를 평면화하고 싶다고 상상해 보세요.

으아악

• 또 다른 예는 JDK 21 스위치 표현식을 사용하고 컴파일러 검사를 활용하는 패턴 일치입니다.

으아악

단점

1. 성능: 목록이 목록의 선두에서 요소를 가져오는 요소를 앞에 추가하는 데 주로 사용되는 경우 성능이 좋습니다. 다른 모든 경우에는 최소한 이 구현에서는 O(n)이 필요합니다.
2. 복잡성: 지속적이고 불변인 LinkedList의 구현은 변경 가능한 것보다 더 복잡합니다.
3. 메모리: 지속적이고 불변인 LinkedList를 구현하려면 각 작업에 대한 새 목록이 생성되기 때문에 변경 가능한 것보다 더 많은 메모리가 필요합니다. 구조적 공유를 통해 이는 완화되지만 제거되지는 않습니다.

결론

이 기사에서는 부분 구조 공유를 통해 Java에서 지속적이고 불변적인 LinkedList를 구현했습니다. 불변성과 지속성의 이점과 Java에서 이를 달성할 수 있는 방법을 시연했습니다. 또한 더 쉬운 함수 구성을 위해 LinkedList를 Monad로 변환하는 방법도 보여주었습니다. 지속성 및 불변 데이터 구조의 장점과 단점, 그리고 실제로 사용하는 방법에 대해 논의했습니다.

위 내용은 지속적이고 불변적인 Java LinkedList의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!