이 문제에서는 이중 연결 목록이 제공됩니다. 우리의 임무는 C++에서 이중 연결 목록의 크기를 찾는 프로그램을 만드는 것입니다.
이중 연결 목록은 단일 연결 목록에 비해 쉽게 앞뒤로 탐색이 가능한 특수한 유형의 연결 목록입니다. 다음은 이중 연결 목록의 개념을 이해하는 데 중요한 용어입니다.
-
링크 - 링크드 리스트의 각 링크는 요소라는 데이터를 저장할 수 있습니다.
-
다음 - 연결 목록의 각 링크는 다음이라는 다음 링크에 대한 링크를 포함합니다.
-
Prev - 연결 목록의 각 링크에는 Prev라는 이전 링크에 대한 링크가 포함되어 있습니다.
-
LinkedList - Linked List는 First라는 첫 번째 링크와 Last라는 마지막 링크에 대한 연결 링크를 포함합니다.
이중 연결 목록의 표현 -
문제 설명 − 위와 같은 유형의 이중 연결 목록이 제공됩니다. 그리고 우리는 그것의 크기(길이)를 찾을 것입니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
the above linked list A <-> B <-> C.
출력
3
해결 방법
이중 연결 목록의 크기를 찾으려면 이중 연결 목록을 순회하고 길이가 유효한 길이를 추적해야 합니다.
알고리즘
초기화 - 길이 =0, *temp =헤드
- 1단계 − 목록을 순회합니다. 즉, temp !=NULL까지 수행합니다.
- 1.1단계 − 길이 증가, 길이++
- 1.2단계 − 포인터 업데이트, temp =temp -> next.
- 2단계 - 인쇄 길이.
우리 솔루션의 작동을 설명하는 프로그램
예
#include <iostream> using namespace std; struct doublyLL { char val; struct doublyLL *next; struct doublyLL *prev; }; void insertNode(struct doublyLL** head_ref, int value){ struct doublyLL* new_node = new doublyLL; new_node->val = value; new_node->next = (*head_ref); new_node->prev = NULL; if ((*head_ref) != NULL) (*head_ref)->prev = new_node ; (*head_ref) = new_node; } int calcDLLSize(struct doublyLL *temp) { int length = 0; while (temp != NULL){ temp = temp->next; length++; } return length; } int main(){ struct doublyLL* head = NULL; insertNode(&head, 'A'); insertNode(&head, 'H'); insertNode(&head, 'E'); insertNode(&head, 'K'); insertNode(&head, 'M'); insertNode(&head, 'S'); cout<<"The size of Doubly Linked List is "<<calcDLLSize(head); return 0; }
출력
The size of Doubly Linked List is 6