자바 이중 연결 목록

Java 이중 연결 목록은 데이터를 저장하는 노드 외에 각 노드에 두 개의 링크가 있는 연결 목록 유형입니다. 첫 번째 링크는 이전 노드를 가리키고 다른 링크는 목록의 다음 노드를 가리킵니다. 이중 연결 목록(Double Linked List, DLL이라고도 함)은 단일 연결 목록과 매우 유사합니다. 연결된 목록에는 모두 다음 노드에 대한 포인터와 노드에 저장될 실제 값을 나타내는 데이터 필드가 포함되어 있습니다. 주요 차이점은 DLL에 목록의 이전 노드에 대한 포인터가 포함되어 있다는 것입니다. 즉, DLL의 노드는 이전 노드와 다음 노드를 모두 인식합니다. 이 기사에서는 Java의 이중 연결 목록을 살펴보고 몇 가지 예를 살펴보고 구현에 대해 알아봅니다.

광고 이 카테고리에서 인기 있는 강좌 JAVA MASTERY - 전문 분야 | 78 코스 시리즈 | 15가지 모의고사

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

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

구문

Java에는 이중 연결 목록에 대한 특별한 구문이 없지만 Java에서 이중 연결 목록을 선언하는 방법을 살펴보겠습니다. 이중 연결 목록 선언을 살펴보기 전에 이중 연결 목록 구현의 개념을 살펴보겠습니다.

이중 연결 목록의 노드:

Prev Node

Data

Next Node

이전 노드 데이터 다음 노드

여기서 Prev Node와 Next Node는 각각 노드의 이전 요소와 다음 요소에 대한 포인터입니다. '데이터'는 데이터가 저장되는 실제 요소입니다.

다음은 우리가 이해해야 할 중요한 용어 중 일부입니다.

• Prev: 연결 리스트의 각 링크에는 Prev라는 이전 노드에 대한 링크가 있습니다.
• Next: 연결 리스트의 각 링크에는 Next라는 다음 노드에 대한 링크가 있습니다
• 링크: 연결 리스트의 각 링크는 요소라는 데이터를 저장할 수 있습니다.
• 링크됨 목록: 첫 번째 링크와 마지막 링크에 대한 연결 링크가 포함되어 있습니다.

알고리즘

• 연결된 목록의 노드를 나타내는 Node 클래스를 정의합니다. 이전 노드, 데이터, 다음 노드 등 3가지 속성이 있어야 합니다
• 머리와 꼬리라는 두 개의 노드가 있는 이중 연결 목록을 생성하려면 다른 클래스를 정의하세요. 처음에는 이 값이 null입니다.
• 연결리스트에 노드를 추가하는 함수를 만듭니다.
• 먼저 헤드가 null인지 확인한 다음 노드를 헤드로 삽입합니다.
• 머리와 꼬리가 모두 새 노드를 가리킵니다.
• 꼬리가 null이 아닌 경우 새 노드의 포인터가 꼬리를 가리키는 방식으로 새 노드가 목록 끝에 삽입됩니다.
• 따라서 새 노드는 새 꼬리가 됩니다.

Java의 이중 연결 목록에 대한 노드 선언:

class Node {
public int data;
public Node prev;
public Node next;
public void displayData() {
//content of the function}
}

보시다시피 이중 연결 목록의 경우 추가 선언이나 참조(노드 이전)가 있습니다.

이중 연결 리스트의 기본 동작

이중 연결 목록에서 사용할 수 있는 기본 작업은 다음과 같습니다.

• 삽입: 연결 목록 시작 부분에 요소 추가
• 삭제: 연결 목록 시작 부분의 요소 삭제
• 다음에 삽입: 연결 리스트 항목 뒤에 요소 추가
• 마지막 삽입: 연결 목록 끝에 요소 추가
• 마지막 삭제: 연결 목록 끝의 요소 삭제
• 삭제: 키를 사용하여 연결 목록에서 요소를 삭제합니다.
• 앞으로 표시: 앞으로 전체 목록 표시
• 뒤로 표시: 전체 목록을 뒤로 표시

Java 이중 연결 목록의 예

다음은 Java 이중 연결 목록의 다양한 예입니다.

예시 #1: 노드 선언 및 표시에 노드 추가

코드:

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
Node headNode, tailNode = null;
public void addDLLNode(int data) {
Node newDLLNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newDLLNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newDLLNode;
newDLLNode.prevNode = tailNode;
tailNode = newDLLNode;
tailNode.nextNode = null;
}
}
public void displayNode() {
Node currentNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
System.out.println("Nodes in Doubly Linked List: ");
while(currentNode != null) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.nextNode;
}
}
public static void main(String[] args) {
DLL dLinkedList = new DLL();
dLinkedList.addDLLNode(9);
dLinkedList.addDLLNode(7);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(1);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(7);
dLinkedList.displayNode();
}
}

출력:

여기에서는 이중 연결 목록을 선언하고 DLL 값을 표시하는 Node 클래스를 만듭니다.

예제 #2: 연결된 목록의 시작 부분을 삭제하고 표시

코드:

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
public void displayNode() {
Node tempNode = headNode;
while (tempNode != null) {
System.out.print(tempNode.data + "–>");
tempNode = tempNode.nextNode;
}
System.out.println("END");
}
Node headNode, tailNode = null;
public void addNode(int data) {
Node newNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newNode;
newNode.prevNode = tailNode;
tailNode = newNode;
tailNode.nextNode = null;
}
}
public void deleteInitialNode() {
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
else {
if(headNode != tailNode) {
headNode = headNode.nextNode;
}
else {
headNode = tailNode = null;
}
}
}
void printNode() {
Node currNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
while(currNode != null)
{
System.out.print(currNode.data + " ");
currNode = currNode.nextNode;
}
System.out.println();
}
public static void main(String[] args) {
DLL doublyLL = new DLL();
doublyLL.addNode(3);
doublyLL.addNode(5);
doublyLL.addNode(7);
doublyLL.addNode(9);
doublyLL.addNode(11);
System.out.println("Doubly linked list: ");
doublyLL.printNode();
doublyLL.addNode(15);
doublyLL.addNode(17);
doublyLL.addNode(19);
doublyLL.deleteInitialNode();
doublyLL.addNode(21);
System.out.println("Doubly Linked List after deleting at the beginning: ");
doublyLL.printNode();
}
}

출력:

여기서는 연결리스트의 시작 부분에서 노드가 삭제됩니다. 즉, 노드 3이 삭제/제거됩니다.

DLL은 정방향 및 역방향으로 탐색할 수 있습니다. 삭제할 노드 포인터가 주어지면 DLL에서의 삭제 작업이 더 효율적일 수 있습니다. DLL의 모든 노드에는 이전 포인터를 위한 추가 공간이 필요합니다. 모든 작업에는 유지 관리를 위한 추가 포인터가 필요합니다.

이것으로 "Java 이중 연결 목록" 주제를 마치겠습니다. 우리는 Java 이중 연결 목록이 무엇인지, 몇 가지 예를 통해 Java 프로그래밍에서 어떻게 구현되는지 살펴보았습니다. 또한 이중 연결 목록에 대한 알고리즘을 살펴보고 DLL에 적용할 수 있는 몇 가지 작업을 나열했습니다. 첫 번째 작업에서 삽입 및 삭제를 구현했으며 마찬가지로 작업할 수 있는 다른 작업도 사용할 수 있습니다.

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