Java의 데이터 구조 및 알고리즘, Part 4 : 단일 연결 목록

이 튜토리얼 시리즈의 Part 3에서 소개 된 배열과 마찬가지로 연결 목록은 더 복잡한 데이터 구조의 기반이 될 수있는 기본적인 데이터 구조 범주입니다. 그러나 일련의 요소와 달리 링크 된 목록 은 노드의 시퀀스이며 각 노드는 시퀀스의 이전 및 다음 노드에 링크됩니다. 호출이 있는지 노드 자체 참조 클래스로부터 생성 된 목적 및 자기 참조 클래스는 그 참조 타입 클래스 이름, 적어도 하나 개의 필드를 갖는다. 연결 목록의 노드는 노드 참조를 통해 연결됩니다. 예를 들면 다음과 같습니다.

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

이 예 Employee에서은 next필드에 유형 이 있으므로 자체 참조 클래스 Employee입니다. 이 필드는 클래스의 다른 개체 ( 이 경우 다른 개체)에 대한 참조를 저장할 수 있으므로 링크 필드 의 예입니다 Employee.

이 튜토리얼은 Java 프로그래밍에서 단일 연결 목록의 기능을 소개합니다. 단일 연결 목록 만들기, 단일 연결 목록에 노드 삽입, 단일 연결 목록에서 노드 삭제, 단일 연결 목록을 다른 단일 연결 목록에 연결, 단일 연결 목록 반전 작업을 학습합니다. 또한 단일 연결 목록을 정렬하는 데 가장 일반적으로 사용되는 알고리즘을 탐색하고 삽입 정렬 알고리즘을 보여주는 예제로 마무리합니다.

다운로드 코드 받기이 기사에 대한 세 가지 예제 애플리케이션을 다운로드하십시오. JavaWorld를 위해 Jeff Friesen이 만들었습니다.

단일 연결 목록이란 무엇입니까?

단일 연결리스트는 각 노드가 단일 링크 필드가 노드의 링크 된 목록입니다. 이 데이터 구조에서 참조 변수는 첫 번째 (또는 최상위) 노드에 대한 참조를 포함합니다. 각 노드 (마지막 또는 맨 아래 노드 제외)는 다음 노드에 연결됩니다. 마지막 노드의 링크 필드에는 목록의 끝을 나타내는 null 참조가 포함됩니다. 참조 변수의 이름은 일반적으로이지만 top원하는 이름을 선택할 수 있습니다.

그림 1은 3 개의 노드가있는 단일 연결 목록을 보여줍니다.

아래는 단일 연결 목록에 대한 의사 코드입니다.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

Nodename데이터 필드와 next링크 필드 가있는 자체 참조 클래스입니다 . 단일 연결 목록 의 첫 번째 개체에 대한 참조를 보유하는 top유형의 참조 변수입니다 . 목록이 아직 존재하지 않기 때문에 의 초기 값은 입니다.NodeNodetopNULL

Java에서 단일 연결 목록 만들기

단일 Node개체 를 연결하여 단일 연결 목록을 만듭니다. 다음 의사 코드는 Node객체를 만들고 참조를에 할당 top하고 데이터 필드를 초기화 NULL하고 링크 필드에 할당 합니다.

 top = NEW Node top.name = "A" top.next = NULL 

그림 2는이 의사 코드에서 나온 초기 단일 연결 목록을 보여줍니다.

이 연산의 시간 복잡도는 O (1) 상수입니다. O (1)은 "Big Oh of 1"로 발음됩니다. (시간 및 공간 복잡성 측정이 데이터 구조를 평가하는 데 사용되는 방법에 대한 알림은 1 부를 참조하십시오.)

단일 연결 목록에 노드 삽입

단일 연결 목록에 노드를 삽입하는 것은 고려해야 할 세 가지 경우가 있기 때문에 단일 연결 목록을 만드는 것보다 다소 복잡합니다.

  • 첫 번째 노드 앞에 삽입.
  • 마지막 노드 뒤에 삽입.
  • 두 노드 사이에 삽입.

첫 번째 노드 앞에 삽입

새 노드의 참조를 새 노드의 링크 필드에 할당하고 새 노드의 참조를 top변수 에 할당하여 첫 번째 노드 앞에 새 노드를 삽입 합니다. 이 작업은 다음 의사 코드로 설명됩니다.

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

결과 2 개 Node목록이 그림 3에 나와 있습니다.

이 연산의 시간 복잡도는 O (1)입니다.

마지막 노드 이후 삽입

새 노드는 새 노드의 링크 필드에 null 을 할당 하고, 단일 연결 목록을 통과하여 마지막 노드를 찾고, 새 노드의 참조를 마지막 노드의 링크 필드에 할당함으로써 마지막 노드 뒤에 삽입됩니다.

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

그림 4는 A 다음에 NodeC를 삽입 한 후의 목록을 보여줍니다 Node.

이 연산의 시간 복잡도는 O ( n )-선형입니다. 시간 복잡도는 마지막 노드에 대한 참조를 유지함으로써 O (1)로 개선 될 수 있습니다. 이 경우 마지막 노드를 검색 할 필요가 없습니다.

두 노드 사이에 삽입

두 노드 사이에 노드를 삽입하는 것은 가장 복잡한 경우입니다. 목록을 탐색하여 새 노드 앞에 오는 노드를 찾고, 찾은 노드의 링크 필드에있는 참조를 새 노드의 링크 필드에 할당하고, 새 노드의 참조를 찾은 노드의 링크에 할당하여 두 노드 사이에 새 노드를 삽입합니다. 들. 다음 의사 코드는 이러한 작업을 보여줍니다.

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

그림 5는 s A와 C Node사이 에 D를 삽입 한 후의 목록을 보여줍니다 Node.

이 연산의 시간 복잡도는 O ( n )입니다.

단일 연결 목록에서 노드 삭제

단일 연결 목록에서 노드를 삭제하는 것도 단일 연결 목록을 만드는 것보다 다소 복잡합니다. 그러나 고려해야 할 두 가지 경우 만 있습니다.

  • 첫 번째 노드 삭제.
  • 첫 번째 노드를 제외한 모든 노드 삭제.

첫 번째 노드 삭제

첫 번째 노드를 삭제하려면 첫 번째 노드를 참조하는 변수에 첫 번째 노드의 링크 필드에있는 링크를 할당해야하지만 첫 번째 노드가있는 경우에만 해당됩니다.

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

그림 6은 첫 번째 Node가 삭제 된 목록의 전후보기를 보여줍니다 . 노드가 B사라지고 NodeA가 첫 번째 Node.

이 연산의 시간 복잡도는 O (1)입니다.

첫 번째 노드를 제외한 모든 노드 삭제

첫 번째 노드를 제외한 모든 노드를 삭제하려면 삭제할 노드 이전의 노드를 찾고 삭제할 노드의 링크 필드에있는 참조를 이전 노드의 링크 필드에 할당해야합니다. 다음 의사 코드를 고려하십시오.

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

그림 7은 중간 Node이 삭제 된 목록의 전후보기를 보여줍니다 . NodeD가 사라집니다.

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I've created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application's source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Compile Listing 1 as follows:

 javac SLLDemo.java 

Run the resulting application as follows:

 java SLLDemo 

You should observe the following output:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

SLLDemo연결과 반전을 보여주는 두 번째 버전의 Java 애플리케이션을 만들었습니다 . 목록 2는이 애플리케이션의 소스 코드를 보여줍니다.