자바의 역방향 연결리스트

모든 노드에 데이터와 포인터가 존재하고 포인터가 다음 노드를 가리키는 노드로 구성된 데이터 구조를 연결 리스트(Linked list)라고 하며, 배열과 달리 이러한 연결 리스트를 거꾸로 하면 역방향 연결 리스트라고 합니다. 리스트를 리스트의 첫 번째 노드와 나머지 연결 리스트라고 하는 두 부분으로 나누고, 그 중 나머지 연결 리스트에 대해서는 역함수를 호출하고 나머지 연결 리스트는 첫 번째 노드에 연결하는 방식입니다. , 헤드 포인터는 고정되어 있습니다. 이번 주제에서는 자바의 역연결리스트(Reverse Linked List)에 대해 알아보겠습니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

Java의 역방향 연결리스트 작업

자바에서는 두 가지 알고리즘을 사용하여 연결 목록을 되돌릴 수 있습니다. 그들은:

1. 반복 알고리즘

아래 단계에서는 반복 알고리즘의 작동 방식을 설명합니다.

• ptrA, ptrB, ptrC라는 세 개의 포인터를 초기화해야 합니다.
• ptrA가 애초에 가리키고 있습니다. 이것이 ptrA의 임무이다. ptrB는 ptrA를 다시 가리키는 참조로 사용합니다. 역방향 목록의 마지막 노드가 null이므로 처음에는 이 포인터도 null이 됩니다.
• ptrB는 2위를 가리키고 있습니다. 이것이 주요 포인터입니다. ptrB의 다음은 ptrA를 가리키며, 이것이 기존 포인터 링크가 반전되는 방식입니다.
• 3위는 ptrC가 지목하고 있는 곳입니다. 이 포인터를 사용하는 것은 ptrB보다 먼저 목록이 손실되지 않도록 백업하는 것입니다. 그렇지 않으면 ptrB보다 먼저 참조가 손실됩니다.
• 연결된 목록의 역전은 ptrA를 Null로 초기화하는 것으로 시작됩니다. ptrA는 연결리스트를 뒤집은 후 꼬리 노드가 되므로 null로 설정해야 합니다.
• 첫 번째 노드를 가리키는 ptrB가 역방향 리스트에서 꼬리 노드가 되므로 ptrB의 다음 노드가 ptrA에 연결됩니다.
• 단 하나의 노드로 구성된 목록을 반전해야 하는 경우 위의 두 단계에 따라 작업을 완료할 수 있습니다.
• ptrB의 다음 목록이 ptrA를 가리키게 되면 ptrB 앞의 목록에 대한 참조가 손실됩니다. 따라서 ptrA 옆에 ptrB를 지정하기 전에 ptrB의 앞선 목록에 대한 백업으로 ptrC를 사용합니다.
• 위 단계는 ptrB가 null을 가리킬 때까지 반복됩니다. 즉, 원래 목록 노드가 모두 반전됩니다.

2. 재귀 알고리즘

아래 단계에서는 재귀 알고리즘의 작동 방식을 설명합니다.

• 알고리즘은 헤드의 노드 전류를 고려하여 시작됩니다.
• 노드 전류가 null이면 반환됩니다.
• 현재 노드의 다음 요소가 null이면 목록의 마지막 노드임을 나타냅니다. 역방향 리스트의 선두가 마지막 노드가 되어야 하므로 마지막 노드를 선두로 만든 후 반환해야 합니다.
• 목록은 재귀적으로 탐색됩니다.
• 현재는 current.next.next로 설정되어 있습니다.
• current.next에 Null이 설정되어 있습니다.

Java의 역방향 연결리스트 예시

아래에 언급된 예시는 다음과 같습니다

예시 #1

반복 알고리즘을 사용하여 단일 연결 목록을 역전시키는 Java 프로그램

코드:

class List
{
static Node head1;
static class Node
{
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
//The linked list is reversed using this function
Node reverselist(Node node1)
{
Node previous = null;
Node curr = node1;
Node nex = null;
while (curr != null)
{
nex = curr.nex;
curr.nex = previous;
previous = curr;
curr = nex;
}
node1 = previous;
return node1;
}
// The contents of linked list are printed
void printL(Node node1)
{
while (node1 != null)
{
System.out.print(node1.data1 + " ");
node1 = node1.nex;
}
}
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List l = new List();
l.head1 = new Node(30);
l.head1.nex = new Node(40);
l.head1.nex.nex = new Node(50);
l.head1.nex.nex.nex = new Node(60);
System.out.println("The items in the linked list that needs to be reversed are");
l.printL(head1);
//Function to reverse the list is called here
head1 = l.reverselist(head1);
System.out.println("");
System.out.println("The items in the reversed linked list are");
l.printL(head1);
}
}

출력:

예시 #2

반복 알고리즘을 사용하여 단일 연결 목록을 역전시키는 Java 프로그램

코드:

class List {
static Node head1;
static class Node {
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
// A recursive function to reverse the linked list
Node reverse(Node current, Node previous)
{
//Last node is marked as head
if (current.nex == null) {
head1 = current;
//previous node is updated with next
current.nex = previous;
return head1;
}
//current.nex node is saved for the recursive call
Node nex1 = current.nex;
//nex is updated
current.nex = previous;
reverse(nex1, current);
return head1;
}
// Content of the reversed linked list are printed
void printL(Node node)
{
while (node != null) {
System.out.print(node.data1 + " ");
node = node.nex;
}
}
//Main method is called which prints the reversed linked list by calling the function
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List list = new List();
list.head1 = new Node(20);
list.head1.nex = new Node(30);
list.head1.nex.nex = new Node(40);
list.head1.nex.nex.nex = new Node(50);
System.out.println("The items in the linked list that needs to be reversed are");
list.printL(head1);
//Function to reverse the list is called here
Node result = list.reverse(head1, null);
System.out.println("");
System.out.println("");
System.out.println("The items in the reversed linked list are");
list.printL(result);
}
}

출력:

결론

이 튜토리얼에서는 연결리스트의 역전 개념을 정의를 통해 이해하고, 연결리스트가 역전되는 논리를 설명합니다. 연결리스트를 역전시키는 두 가지 알고리즘인 반복 알고리즘을 설명하고, 재귀 알고리즘을 자바에서 구현하기 위한 프로그래밍 예제도 함께 설명합니다.

위 내용은 자바의 역방향 연결리스트의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!