Tìm kích thước danh sách liên kết đôi trong C++

Cho danh sách liên kết đôi (Doubly Linked List). Tìm kích thước (số nút) của nó.

Danh sách liên kết đôi cho phép duyệt cả hai chiều nhờ có con trỏ next và prev.

Cấu trúc nút

• val: dữ liệu
• next: con trỏ nút sau
• prev: con trỏ nút trước

Giải thuật

Khởi tạo length = 0, temp = head. Duyệt khi temp != NULL: length++, temp = temp->next. Trả về length.

Ví dụ minh họa (C++)

#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