Trong vấn đề này, chúng tôi được cung cấp một danh sách liên kết kép. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm kích thước của Danh sách được liên kết gấp đôi trong C ++.
Danh sách được liên kết đôi là một loại danh sách được liên kết đặc biệt trong đó có thể điều hướng theo cả hai cách, chuyển tiếp và lùi lại một cách dễ dàng so với Danh sách được liên kết đơn lẻ. Sau đây là các thuật ngữ quan trọng để hiểu khái niệm danh sách được liên kết kép.
-
Liên kết - Mỗi liên kết của danh sách được liên kết có thể lưu trữ một phần tử được gọi là dữ liệu.
-
Tiếp theo - Mỗi liên kết của danh sách được liên kết chứa một liên kết đến liên kết tiếp theo được gọi là Tiếp theo.
-
Trước đó - Mỗi liên kết của danh sách được liên kết chứa một liên kết đến liên kết trước đó được gọi là Trước đó.
-
LinkedList - Danh sách được liên kết chứa liên kết đến liên kết đầu tiên được gọi là First và đến liên kết cuối cùng được gọi là Last.
Trình bày danh sách được liên kết kép -
Mô tả sự cố - Chúng ta sẽ được cung cấp một danh sách liên kết kép thuộc loại trên. Và chúng tôi sẽ tìm kích thước (chiều dài) của nó.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
the above linked list A <-> B <-> C.
Đầu ra
3
Phương pháp tiếp cận giải pháp
Để tìm kích thước của danh sách được liên kết đôi, chúng ta cần xem qua danh sách được liên kết đôi và theo dõi độ dài với độ dài có thể định giá được.
Thuật toán
Khởi tạo - length =0, * temp =head
- Bước 1 - Duyệt qua danh sách, tức là làm cho đến khi tạm thời! =NULL.
- Bước 1.1 - Tăng chiều dài, chiều dài ++
- Bước 1.2 - Cập nhật con trỏ, temp =temp -> tiếp theo.
- Bước 2 - độ dài in.
Chương trình minh họa hoạt động của giải pháp của chúng tôi
Ví dụ
#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;
} Đầu ra
The size of Doubly Linked List is 6