1. 소개
이 사용방법(예제)에서는 Java에서 두 개의 연결 List 반전 알고리즘 을 구현 합니다.
2. 연결 리스트 데이터 구조
연결 List은 각 요소의 포인터가 순서를 결정하는 선형 데이터 구조입니다. 연결 List의 각 요소에는 List 데이터를 저장하는 데이터 필드와 시퀀스의 다음 요소를 가리키는 포인터 필드가 있습니다. 또한 헤드 포인터를 사용 하여 연결 List의 시작 요소를 가리킬 수 있습니다 .
연결 List을 뒤집은 후 헤드 는 원래 연결 List의 마지막 요소를 가리키고 각 요소의 포인터는 원래 연결 List의 이전 요소를 가리킵니다.
Java 에는 List 및 Deque 인터페이스 의 이중 연결 List 구현을 제공 하는 LinkedList 클래스가 있습니다. 그러나 이 사용방법(예제)에서는 일반적인 단일 연결 List 데이터 구조를 사용합니다.
먼저 연결 List의 요소를 나타내는 ListNode 클래스부터 시작하겠습니다 .
public class ListNode {
private int data;
private ListNode next;
ListNode(int data) {
this.data = data;
this.next = null;
}
// standard getters and setters
}ListNode의 클래스는 두 개의 필드가 있습니다 :
- 요소의 데이터를 나타내는 정수 값
- 다음 요소에 대한 포인터/참조
연결 List에는 여러 ListNode 개체 가 포함될 수 있습니다 . 예를 들어 루프를 사용하여 위의 샘플 연결 List을 구성할 수 있습니다.
ListNode constructLinkedList() {
ListNode head = null;
ListNode tail = null;
for (int i = 1; i <= 5; i++) {
ListNode node = new ListNode(i);
if (head == null) {
head = node;
} else {
tail.setNext(node);
}
tail = node;
}
return head;
}3. 반복 알고리즘 구현
Java 에서 반복 알고리즘 을 구현해 보겠습니다 .
ListNode reverseList(ListNode head) {
ListNode previous = null;
ListNode current = head;
while (current != null) {
ListNode nextElement = current.getNext();
current.setNext(previous);
previous = current;
current = nextElement;
}
return previous;
}이 반복 알고리즘에서는 두 개의 ListNode 변수 이전 및 현재 를 사용하여 연결 List에서 두 개의 인접한 요소를 나타냅니다. 각 반복에 대해 이 두 요소를 뒤집고 다음 두 요소로 이동합니다.
결국 현재 포인터는 null이 되고 이전 포인터는 이전 연결 List의 마지막 요소가 됩니다. 따라서 이전 은 역방향 연결 List의 새로운 헤드 포인터이기도 하며 메서드에서 반환합니다.
간단한 단위 테스트를 통해 이 반복적인 구현을 확인할 수 있습니다.
@Test
public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {
ListNode head = constructLinkedList();
ListNode node = head;
for (int i = 1; i <= 5; i++) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
LinkedListReversal reversal = new LinkedListReversal();
node = reversal.reverseList(head);
for (int i = 5; i >= 1; i--) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
}이 단위 테스트에서는 먼저 5개의 노드가 있는 샘플 연결 List을 구성합니다. 또한 연결 List의 각 노드에 올바른 데이터 값이 포함되어 있는지 확인합니다. 그런 다음 연결 List을 뒤집기 위해 반복 함수를 호출합니다. 마지막으로 데이터가 예상대로 반전되었는지 확인하기 위해 반전 연결 List을 확인합니다.
4. 재귀 알고리즘 구현
이제 Java 에서 재귀 알고리즘 을 구현해 보겠습니다 .
ListNode reverseListRecursive(ListNode head) {
if (head == null) {
return null;
}
if (head.getNext() == null) {
return head;
}
ListNode node = reverseListRecursive(head.getNext());
head.getNext().setNext(head);
head.setNext(null);
return node;
}에서 reverseListRecursive 우리가 마지막에 도달 할 때까지 기능, 우리는 반복적으로 연결리스트의 각 요소를 방문하십시오. 이 마지막 요소는 역방향 연결 List의 새 헤드가 됩니다. 또한 부분적으로 반전된 연결 List의 끝에 방문된 요소를 추가합니다.
마찬가지로 간단한 단위 테스트로 이 재귀 구현을 확인할 수 있습니다.
@Test
public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {
ListNode head = constructLinkedList();
ListNode node = head;
for (int i = 1; i <= 5; i++) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
LinkedListReversal reversal = new LinkedListReversal();
node = reversal.reverseListRecursive(head);
for (int i = 5; i >= 1; i--) {
assertNotNull(node);
assertEquals(i, node.getData());
node = node.getNext();
}
}5. 결론
이 사용방법(예제)에서는 연결 List을 뒤집기 위해 두 가지 알고리즘을 구현했습니다. 항상 그렇듯이 기사의 소스 코드는 GitHub에서 사용할 수 있습니다 .
