순환 연결 목록 Java 구현

1. 소개

이 튜토리얼에서는 Java에서 순환 연결 목록의 구현을 살펴볼 것입니다.

2. 순환 연결 목록

순환 연결 목록은 마지막 노드가 첫 번째 노드를 가리키며 전체 노드 원을 완성하는 연결 목록의 변형입니다 . 즉, 연결 목록의이 변형은 끝에 null 요소 가 없습니다 .

이 간단한 변경으로 다음과 같은 이점이 있습니다.

  • 순환 연결 목록의 모든 노드가 시작점이 될 수 있습니다.
  • 결과적으로 전체 목록은 모든 노드에서 시작하여 순회 할 수 있습니다.
  • 순환 연결 목록의 마지막 노드에는 첫 번째 노드에 대한 포인터가 있으므로 대기열에 넣기 및 대기열에서 빼기 작업을 수행하기 쉽습니다.

대체로 이것은 큐 데이터 구조의 구현에 매우 유용합니다.

성능 측면에서는 한 가지를 제외하고는 다른 연결 목록 구현과 동일 합니다. 마지막 노드에서 헤드 노드로의 순회는 일정한 시간에 수행 될 수 있습니다 . 기존의 연결 목록을 사용하면 이것은 선형 작업입니다.

3. 자바 구현

int 값과 다음 노드에 대한 포인터를 저장할 보조 노드 클래스를 생성하는 것으로 시작하겠습니다 .

class Node { int value; Node nextNode; public Node(int value) { this.value = value; } }

이제 일반적으로 머리꼬리 라고하는 순환 연결 목록에 첫 번째와 마지막 노드를 만들어 보겠습니다 .

public class CircularLinkedList { private Node head = null; private Node tail = null; // .... }

다음 하위 섹션에서는 순환 연결 목록에서 수행 할 수있는 가장 일반적인 작업을 살펴 ​​보겠습니다.

3.1. 요소 삽입

우리가 다룰 첫 번째 작업은 새 노드의 삽입입니다. 새 요소를 삽입하는 동안 두 가지 경우를 처리해야합니다.

  • 헤드 노드가 null의 경우 이미 추가에 요소가없는된다. 이 경우에는 노드가 하나뿐이므로 목록 의 헤드테일 모두로 추가 한 새 노드를 만듭니다.
  • 헤드 노드는 null가 아닌 이미 목록에 추가 하나 개 이상의 요소가 말을하는 것입니다. 이 경우 기존 꼬리 는 새 노드를 가리켜 야하며 새로 추가 된 노드는 꼬리가됩니다.

위의 두 경우 모두 꼬리nextNode머리 를 가리 킵니다.

매개 변수로 삽입 할 을 취하는 addNode 메서드를 만들어 보겠습니다 .

public void addNode(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; } else { tail.nextNode = newNode; } tail = newNode; tail.nextNode = head; }

이제 순환 연결 목록에 몇 가지 숫자를 추가 할 수 있습니다.

private CircularLinkedList createCircularLinkedList() { CircularLinkedList cll = new CircularLinkedList(); cll.addNode(13); cll.addNode(7); cll.addNode(24); cll.addNode(1); cll.addNode(8); cll.addNode(37); cll.addNode(46); return cll; }

3.2. 요소 찾기

다음으로 살펴볼 작업은 요소가 목록에 있는지 확인하기 위해 검색하는 것입니다.

이를 위해 목록의 노드 (일반적으로 head )를 currentNode로 수정 하고 필요한 요소를 찾을 때 까지이 노드 nextNode사용하여 전체 목록을 순회 합니다.

searchValue 를 매개 변수로 사용하는 새 메소드 containsNode 를 추가해 보겠습니다 .

public boolean containsNode(int searchValue) { Node currentNode = head; if (head == null) { return false; } else { do { if (currentNode.value == searchValue) { return true; } currentNode = currentNode.nextNode; } while (currentNode != head); return false; } }

이제 위에서 만든 목록에 우리가 추가 한 요소와 새로운 요소가 없는지 확인하기 위해 몇 가지 테스트를 추가해 보겠습니다.

@Test public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(8)); assertTrue(cll.containsNode(37)); } @Test public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse() { CircularLinkedList cll = createCircularLinkedList(); assertFalse(cll.containsNode(11)); }

3.3. 요소 삭제

다음으로 삭제 작업을 살펴 ​​보겠습니다. 삽입과 유사하게 살펴 봐야 할 몇 가지 사례 (목록 자체가 비어있는 경우 제외)가 있습니다.

  • 삭제할 요소는 헤드 자체 입니다. 이 경우, 우리는 업데이트해야 머리 현재 헤드의 다음 노드로 , 그리고의 다음 노드 꼬리 새로운 머리 등을
  • 삭제할 요소는 head 이외의 요소 입니다. 이 경우 삭제해야하는 노드의 다음 노드로 이전 노드의 다음 노드를 업데이트하면됩니다.

이제 valueToDelete 를 매개 변수로 사용하는 새 메소드 deleteNode 를 추가합니다 .

public void deleteNode(int valueToDelete) { Node currentNode = head; if (head != null) { if (currentNode.value == valueToDelete) { head = head.nextNode; tail.nextNode = head; } else { do { Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) { currentNode.nextNode = nextNode.nextNode; break; } currentNode = currentNode.nextNode; } while (currentNode != head); } } }

이제 모든 경우에 대해 삭제가 예상대로 작동하는지 확인하는 간단한 테스트를 추가해 보겠습니다.

@Test public void givenACircularLinkedList_WhenDeletingElements_ThenListDoesNotContainThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(13)); cll.deleteNode(13); assertFalse(cll.containsNode(13)); assertTrue(cll.containsNode(1)); cll.deleteNode(1); assertFalse(cll.containsNode(1)); assertTrue(cll.containsNode(46)); cll.deleteNode(46); assertFalse(cll.containsNode(46)); }

3.4. 목록 순회

이 마지막 섹션에서 순환 연결 목록의 순회를 살펴 보겠습니다 . 검색 및 삭제 작업과 유사하게 순회를 위해 currentNode헤드 로 수정 하고이 노드 의 nextNode 를 사용하여 전체 목록을 순회 합니다.

목록에 추가 된 요소를 인쇄 하는 새 메서드 traverseList 를 추가해 보겠습니다 .

public void traverseList() { Node currentNode = head; if (head != null) { do { LOGGER.info(currentNode.value + " "); currentNode = currentNode.nextNode; } while (currentNode != head); } } 

위의 예에서 볼 수 있듯이 순회하는 동안 헤드 노드로 돌아갈 때까지 각 노드의 값을 간단히 인쇄합니다.

4. 결론

이 자습서에서는 Java에서 순환 연결 목록을 구현하는 방법과 가장 일반적인 작업 중 일부를 살펴 보았습니다.

먼저, 순환 연결 목록이 기존 연결 목록과의 가장 일반적인 기능 및 차이점을 포함하는 것이 정확히 무엇인지 배웠습니다. 그런 다음 순환 연결 목록 구현에서 항목을 삽입, 검색, 삭제 및 탐색하는 방법을 보았습니다.

평소처럼이 기사에서 사용 된 모든 예제는 GitHub에서 사용할 수 있습니다.