Java의 데이터 구조 및 알고리즘, Part 5 : 이중 연결 목록

단일 연결 목록에는 많은 용도가 있지만 몇 가지 제한 사항도 있습니다. 우선, 단일 연결 목록은 노드 탐색을 단일 방향으로 제한합니다. 먼저 노드 연결을 되 돌리지 않는 한 단일 연결 목록을 뒤로 탐색 할 수 없습니다.이 경우 시간이 걸립니다. 역 순회를 수행하고 노드 순회를 원래 방향으로 복원해야하는 경우 반전을 반복해야하므로 시간이 더 걸립니다. 단일 연결 목록도 노드 삭제를 제한합니다. 이 유형의 목록에서는 노드의 선행 노드에 액세스하지 않고 임의의 노드를 삭제할 수 없습니다.

다행히 Java는 Java 프로그램에 저장된 데이터를 검색하고 정렬하는 데 사용할 수있는 여러 유형의 목록을 제공합니다. 데이터 구조 및 알고리즘 시리즈 의이 마지막 자습서에서는 이중 연결 목록 및 순환 연결 목록을 사용한 검색 및 정렬을 소개합니다. 보시다시피이 두 데이터 구조 범주는 단일 링크 목록을 기반으로 구축되어 Java 프로그램에서보다 광범위한 검색 및 정렬 동작을 제공합니다.

이중 연결 목록

이중 연결리스트는 각 노드가 링크 필드의 한 쌍의 노드 링크 된 목록입니다. 하나의 링크 필드를 사용하면 목록을 정방향으로 순회 할 수 있고 다른 노드를 사용하면 목록을 역방향으로 순회 할 수 있습니다. 순방향의 경우 참조 변수는 첫 번째 노드에 대한 참조를 보유합니다. 각 노드는 "다음"링크 필드를 통해 다음 노드에 링크합니다. 마지막 노드는 "다음"링크 필드에 목록의 끝을 나타내는 널 참조 (정방향)를 포함합니다. 역방향도 비슷하게 작동합니다. 참조 변수는 첫 번째 노드로 해석되는 순방향의 마지막 노드에 대한 참조를 보유합니다. 각 노드는 "이전"링크 필드를 통해 이전 노드에 링크됩니다. 첫 번째 노드의 "이전"링크 필드에는 목록의 끝을 나타내는 null이 포함됩니다.

이중으로 연결된 목록을 각각 동일한 노드를 상호 연결하는 단일 연결 목록 쌍으로 생각하십시오. 그림 1의 다이어그램은 topForward-참조 및 topBackward-참조 된 단일 링크 목록을 보여줍니다.

이중 연결 목록의 CRUD 작업

노드 생성, 삽입 및 삭제는 모두 이중 연결 목록에서 일반적인 작업입니다. 단일 연결 목록에 대해 배운 작업과 유사합니다. (이중 연결 목록은 동일한 노드를 상호 연결하는 단일 연결 목록의 쌍일뿐입니다.) 다음 의사 코드는 노드를 생성하고 그림 1에 표시된 이중 연결 목록에 삽입하는 방법을 보여줍니다. 의사 코드는 또한 노드를 보여줍니다. 삭제:

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

예제 애플리케이션 : 이중 연결 목록의 CRUD

예제 Java 애플리케이션 DLLDemo은 이중 링크 목록에서 노드를 작성, 삽입 및 삭제하는 방법을 보여줍니다. 애플리케이션의 소스 코드는 목록 1에 나와 있습니다.

목록 1. 이중 링크 목록에서 CRUD를 보여주는 Java 애플리케이션

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

다음과 같이 목록 4를 컴파일하십시오.

 javac DLLDemo.java 

결과 애플리케이션을 다음과 같이 실행하십시오.

 java DLLDemo 

다음 출력을 관찰해야합니다.

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

이중 연결 목록에서 섞기

Java Collections Framework에는 패키지의 Collections일부인 유틸리티 메서드 클래스가 포함되어 java.util있습니다. 이 클래스에는 void shuffle(List list)" 임의의 기본 소스를 사용하여 지정된 목록을 임의로 순열 " 하는 메소드가 포함되어 있습니다 . 예를 들어,이 방법을 사용하여 이중 연결 목록으로 표현 된 카드 더미를 섞을 수 있습니다 ( java.util.LinkedList클래스는 예입니다). 아래 의사 코드에서 Shuffle 알고리즘 이 이중 연결 목록을 섞는 방법을 볼 수 있습니다 .

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

Shuffle 알고리즘은 임의의 소스를 얻은 다음 마지막 노드에서 두 번째 노드까지 목록을 역방향으로 탐색합니다. 무작위로 선택된 노드 (실제로는 이름 필드)를 "현재 위치"로 반복적으로 교체합니다. 노드는 첫 번째 노드에서 현재 위치 (포함)까지 실행되는 목록 부분에서 무작위로 선택됩니다. 이 알고리즘은 void shuffle(List list)의 소스 코드 에서 대략 발췌 한 것 입니다.

Shuffle 알고리즘 의사 코드는 순회 단일 링크 목록에만 초점을 맞추기 때문에 지연됩니다. 합리적인 설계 결정이지만 시간 복잡성으로 인해 비용을 지불합니다. 시간 복잡도는 O ( n 2)입니다. 먼저 를 호출 하는 O ( n ) 루프가 swap()있습니다. 둘째, swap()에는 두 개의 순차적 인 O ( n ) 루프가 있습니다. 1 부에서 다음 규칙을 상기하십시오.

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

Part (a)는 순차 알고리즘을 다룹니다. 여기에 두 개의 O ( n ) 루프가 있습니다. 규칙에 따르면 결과 시간 복잡도는 O ( n )입니다. Part (b)는 중첩 알고리즘을 다룹니다. 이 경우, 우리는 O (이 N O (승산) N을 O (결과) N 2).

Note that Shuffle's space complexity is O(1), resulting from the helper variables that are declared.

Example application: Shuffling in a doubly-linked list

The Shuffle application in Listing 2 is a demonstration of the Shuffle algorithm.

Listing 2. The Shuffle algorithm in Java

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

Compile Listing 5 as follows:

 javac Shuffle.java 

Run the resulting application as follows:

 java Shuffle 

You should observe the following output from one run:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

Circular linked lists

The link field in the last node of a singly-linked list contains a null link. This is also true in a doubly-linked list, which contains the link fields in the last nodes of the forward and backward singly-linked lists. Suppose, instead, that the last nodes contained links to the first nodes. In this situation, you would end up with a circular-linked list, which is shown in Figure 2.

Circular-linked lists, also known as circular buffers or circular queues, have many uses. For example, they're used by operating system interrupt handlers to buffer keystrokes. Multimedia applications use circular-linked lists to buffer data (for example, buffering data being written to a sound card). This technique is also used by the LZ77 family of lossless data compression algorithms.

Linked lists versus arrays

Throughout this series on data structures and algorithms, we've considered the strengths and weaknesses of different data structures. Since we've focused on arrays and linked lists, you might have questions about these types specifically. What advantages and disadvantages do linked lists and arrays offer? When do you use a linked list and when do you use an array? Can data structures from both categories be integrated into a useful hybrid data structure? I'll try to answer these questions below.

Linked lists offer the following advantages over arrays:

  • They don't require extra memory to support expansion. In contrast, arrays require extra memory when expansion is necessary. (Once all elements contain data items, no new data items can be appended to an array.)
  • 동등한 어레이 기반 작업보다 빠른 노드 삽입 / 삭제를 제공합니다. 삽입 / 삭제 위치를 확인한 후 링크 만 업데이트하면됩니다. 배열 관점에서 데이터 항목을 삽입하려면 다른 모든 데이터 항목을 이동하여 빈 요소를 만들어야합니다. 마찬가지로 기존 데이터 항목을 삭제하려면 다른 모든 데이터 항목을 이동하여 빈 요소를 제거해야합니다. 모든 데이터 항목 이동에는 시간이 걸립니다.

반대로 배열은 연결 목록에 비해 다음과 같은 이점을 제공합니다.

  • 요소에는 링크 필드가 필요하지 않기 때문에 배열 요소는 노드보다 적은 메모리를 차지합니다.
  • 배열은 정수 기반 인덱스를 통해 데이터 항목에 대한 빠른 액세스를 제공합니다.