doubly linked list java implementation code examples
이 자습서에서는 이중 연결 목록 구현, 순환 이중 연결 목록 Java 코드 및 예제와 함께 Java의 이중 연결 목록을 설명합니다.
연결 목록은 요소의 순차적 표현입니다. 연결 목록의 각 요소를 '노드'라고합니다. 연결 목록의 한 유형은 '단일 연결 목록'이라고합니다.
여기에서 각 노드에는 실제 데이터를 저장하는 데이터 부분과 목록의 다음 노드에 대한 포인터를 저장하는 두 번째 부분이 포함됩니다. 이전 자습서에서 단일 연결 목록의 세부 사항을 이미 배웠습니다.
학습 내용 :
Java의 이중 연결 목록
연결 목록에는 '이중 연결 목록'이라는 또 다른 변형이 있습니다. 이중 연결 목록에는 단일 연결 목록에서와 같이 데이터 부분과 다음 포인터와는 별도로 해당 노드의 이전 포인터라고하는 추가 포인터가 있습니다.
이중 연결 목록의 노드는 다음과 같습니다.
라우터에서 네트워크 키를 찾는 방법
여기에서 'Prev'와 'Next'는 각각 노드의 이전 및 다음 요소에 대한 포인터입니다. '데이터'는 노드에 저장되는 실제 요소입니다.
다음 그림은 이중 연결 목록을 보여줍니다.
위의 다이어그램은 이중 연결 목록을 보여줍니다. 이 목록에는 4 개의 노드가 있습니다. 보시다시피 첫 번째 노드의 이전 포인터와 마지막 노드의 다음 포인터는 null로 설정됩니다. null로 설정된 이전 포인터는이 노드가 이중 연결 목록의 첫 번째 노드임을 나타내고 다음 포인터가 null로 설정된 것은 노드가 마지막 노드임을 나타냅니다.
장점
- 각 노드에는 이전 노드와 다음 노드를 가리키는 포인터가 있으므로 이중 연결 목록을 앞뒤로 쉽게 순회 할 수 있습니다.
- 포인터를 변경하여 새 노드를 빠르게 추가 할 수 있습니다.
- 마찬가지로, 이전 포인터와 다음 포인터가 있으므로 삭제 작업의 경우 삭제가 더 쉽고 단일 연결 목록의 경우처럼 이전 노드를 찾기 위해 전체 목록을 탐색 할 필요가 없습니다.
단점
- 이중 연결 목록, 즉 이전 포인터에 추가 포인터가 있으므로이 포인터를 다음 포인터 및 데이터 항목과 함께 저장하려면 추가 메모리 공간이 필요합니다.
- 추가, 삭제 등과 같은 모든 작업은 이전 포인터와 다음 포인터를 모두 조작해야하므로 작업 오버 헤드가 부과됩니다.
자바 구현
Java에서 이중 연결 목록의 구현은 이중 연결 목록 클래스, 노드 클래스 생성 및 이중 연결 목록에 노드 추가로 구성됩니다.
새 노드 추가는 일반적으로 목록의 끝에서 수행됩니다. 아래 다이어그램은 이중 연결 목록 끝에 새 노드가 추가 된 것을 보여줍니다.
위의 다이어그램에서 볼 수 있듯이 목록 끝에 새 노드를 추가하려면 마지막 노드의 다음 포인터가 이제 null 대신 새 노드를 가리 킵니다. 새 노드의 이전 포인터는 마지막 노드를 가리 킵니다. 또한 새 노드의 다음 포인터는 null을 가리 키므로 새 노드가됩니다.
아래 프로그램은 목록 끝에 새 노드가 추가 된 이중 링크 목록의 Java 구현을 보여줍니다.
class DoublyLinkedList { //A node class for doubly linked list class Node{ int item; Node previous; Node next; public Node(int item) { this.item = item; } } //Initially, heade and tail is set to null Node head, tail = null; //add a node to the list public void addNode(int item) { //Create a new node Node newNode = new Node(item); //if list is empty, head and tail points to newNode if(head == null) { head = tail = newNode; //head's previous will be null head.previous = null; //tail's next will be null tail.next = null; } else { //add newNode to the end of list. tail->next set to newNode tail.next = newNode; //newNode->previous set to tail newNode.previous = tail; //newNode becomes new tail tail = newNode; //tail's next point to null tail.next = null; } } //print all the nodes of doubly linked list public void printNodes() { //Node current will point to head Node current = head; if(head == null) { System.out.println('Doubly linked list is empty'); return; } System.out.println('Nodes of doubly linked list: '); while(current != null) { //Print each node and then go to next. System.out.print(current.item + ' '); current = current.next; } } } class Main{ public static void main(String() args) { //create a DoublyLinkedList object DoublyLinkedList dl_List = new DoublyLinkedList(); //Add nodes to the list dl_List.addNode(10); dl_List.addNode(20); dl_List.addNode(30); dl_List.addNode(40); dl_List.addNode(50); //print the nodes of DoublyLinkedList dl_List.printNodes(); } }
산출:
이중 연결 목록의 노드 :
10 20 30 40 50
목록 끝에 새 노드를 추가하는 것 외에도 목록 시작 부분이나 목록 사이에 새 노드를 추가 할 수도 있습니다. 독자가 작업을 더 잘 이해할 수 있도록이 구현을 독자에게 맡기십시오.
자바의 순환 이중 연결 목록
순환 이중 연결 목록은 복잡한 구조 중 하나입니다. 이 목록에서 이중 연결 목록의 마지막 노드에는 첫 번째 노드의 주소가 포함되고 첫 번째 노드에는 마지막 노드의 주소가 포함됩니다. 따라서 순환 이중 연결 목록에는 순환이 있고 노드 포인터가 null로 설정되지 않습니다.
다음 다이어그램은 순환 이중 연결 목록을 보여줍니다.
위의 다이어그램에서 볼 수 있듯이 마지막 노드의 다음 포인터는 첫 번째 노드를 가리 킵니다. 첫 번째 노드의 이전 포인터는 마지막 노드를 가리 킵니다.
순환 이중 연결 목록은 소프트웨어 산업에서 광범위하게 적용됩니다. 이러한 응용 프로그램 중 하나는 재생 목록이있는 음악 앱입니다. 재생 목록에서 모든 노래 재생을 마친 다음 마지막 노래가 끝날 때 자동으로 첫 번째 노래로 돌아갑니다. 이것은 순환 목록을 사용하여 수행됩니다.
순환 이중 연결 목록의 장점 :
- 순환 이중 연결 목록은 머리에서 꼬리로 또는 꼬리에서 머리로 순회 할 수 있습니다.
- 머리에서 꼬리로 또는 꼬리에서 머리로 이동하는 것은 효율적이며 일정한 시간 O 만 걸립니다 (1).
- 피보나치 힙을 포함한 고급 데이터 구조를 구현하는 데 사용할 수 있습니다.
단점 :
- 각 노드는 이전 포인터를위한 공간을 확보해야하므로 추가 메모리가 필요합니다.
- 순환 이중 연결 목록에서 작업을 수행하는 동안 많은 포인터를 처리해야합니다. 포인터가 제대로 처리되지 않으면 구현이 중단 될 수 있습니다.
아래 Java 프로그램은 순환 이중 링크 목록의 구현을 보여줍니다.
import java.util.*; class Main{ static Node head; // Doubly linked list node definition static class Node{ int data; Node next; Node prev; }; // Function to insert node in the list static void addNode(int value) { // List is empty so create a single node furst if (head == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; head = new_node; return; } // find last node in the list if list is not empty Node last = (head).prev; //previous of head is the last node // create a new node Node new_node = new Node(); new_node.data = value; // next of new_node will point to head since list is circular new_node.next = head; // similarly previous of head will be new_node (head).prev = new_node; // change new_node=>prev to last new_node.prev = last; // Make new node next of old last last.next = new_node; } static void printNodes() { Node temp = head; //traverse in forward direction starting from head to print the list while (temp.next != head) { System.out.printf('%d ', temp.data); temp = temp.next; } System.out.printf('%d ', temp.data); //traverse in backward direction starting from last node System.out.printf('
Circular doubly linked list travesed backward:
'); Node last = head.prev; temp = last; while (temp.prev != last) { System.out.printf('%d ', temp.data); temp = temp.prev; } System.out.printf('%d ', temp.data); } public static void main(String() args) { //the empty list Node l_list = null; // add nodes to the list addNode(40); addNode(50); addNode(60); addNode(70); addNode(80); //print the list System.out.printf('Circular doubly linked list: '); printNodes(); } }
산출:
순환 이중 연결 목록 : 40 50 60 70 80
역방향 순환 이중 연결 목록 :
80 70 60 50 40
위의 프로그램에서 목록 끝에 노드를 추가했습니다. 목록이 원형이므로 새 노드가 추가되면 새 노드의 다음 포인터가 첫 번째 노드를 가리키고 첫 번째 노드의 이전 포인터가 새 노드를 가리 킵니다.
마찬가지로 새 노드의 이전 포인터는 이제 두 번째 마지막 노드가 될 현재 마지막 노드를 가리 킵니다. 목록의 시작 부분과 독자의 노드 사이에 새 노드를 추가하는 구현은 그대로 둡니다.
자주 묻는 질문
Q # 1) 이중 연결 목록이 순환 될 수 있습니까?
대답: 예. 더 복잡한 데이터 구조입니다. 순환 이중 연결 목록에서 첫 번째 노드의 이전 포인터에는 마지막 노드의 주소가 포함되고 마지막 노드의 다음 포인터에는 첫 번째 노드의 주소가 포함됩니다.
Q # 2) 이중 순환 연결 목록은 어떻게 만드나요?
대답: 이중 순환 연결 목록에 대한 클래스를 만들 수 있습니다. 이 클래스 안에는 노드를 나타내는 정적 클래스가 있습니다. 각 노드에는 두 개의 포인터 (이전 및 다음 및 데이터 항목)가 포함됩니다. 그런 다음 목록에 노드를 추가하고 목록을 순회하는 작업을 할 수 있습니다.
Q # 3) 이중 연결 목록은 선형입니까, 원형입니까?
대답: 이중 연결 목록은 선형 구조이지만 꼬리가 머리를 가리키고 머리가 꼬리를 가리키는 원형 이중 연결 목록입니다. 따라서 그것은 순환 목록입니다.
Q # 4) 이중 연결 목록과 순환 연결 목록의 차이점은 무엇입니까?
대답: 이중 연결 목록에는 각각 이전 및 다음 포인터를 사용하여 이전 및 다음 노드에 대한 정보를 유지하는 노드가 있습니다. 또한 이중 연결 목록에서 첫 번째 노드의 이전 포인터와 마지막 노드의 다음 포인터가 null로 설정됩니다.
순환 연결 목록에는 시작 또는 끝 노드가 없으며 노드가 순환을 형성합니다. 또한 순환 연결 목록에서 포인터가 null로 설정되지 않았습니다.
Q # 5) 이중 연결 목록의 장점은 무엇입니까?
대답: 이중 연결 목록의 장점은 다음과 같습니다.
- 전진 및 후진 방향으로 이동할 수 있습니다.
- 이전 요소를 찾기 위해 전체 목록을 탐색 할 필요가 없기 때문에 삽입 작업이 더 쉽습니다.
- 이전 및 다음 노드와 조작이 더 쉽기 때문에 삭제가 효율적입니다.
결론
이 자습서에서는 Java의 이중 연결 목록에 대해 자세히 설명했습니다. 이중 연결 목록은 각 노드가 이전 노드와 다음 노드에 대한 포인터를 포함하는 복잡한 구조입니다. 이러한 링크의 관리는 때때로 어렵고 제대로 처리되지 않으면 코드가 손상 될 수 있습니다.
전반적으로 이중 연결 목록의 작업은 이전 및 다음 포인터를 모두 얻었으므로 목록을 순회하는 시간을 절약 할 수 있으므로 더 효율적입니다.
순환 이중 연결 목록은 더 복잡하며 첫 번째 노드의 이전 포인터가 마지막 노드를 가리키고 마지막 노드의 다음 포인터가 첫 번째 노드를 가리키는 원형 패턴을 형성합니다. 이 경우에도 작업이 효율적입니다.
이것으로 우리는 자바에서 연결 목록을 완성했습니다. Java의 검색 및 정렬 기술에 대한 더 많은 자습서를 계속 지켜봐주십시오.
숙련 된 사람을위한 인터뷰 질문 및 답변 테스트
=> 독점적 인 Java 교육 자습서 시리즈를 보려면 여기를 방문하십시오.