โปรแกรมหาขนาดของ Doubly Linked List ใน C++

ในปัญหานี้ เราได้รับ doubly linked list งานของเราคือสร้าง โปรแกรมหาขนาดของ Doubly Linked List ใน C++

Doubly Linked List เป็นประเภทพิเศษของ linked list ที่สามารถนำทางได้ทั้งสองทิศทาง คือ ไปข้างหน้าและถอยหลังได้ง่ายกว่า singly linked list ต่อไปนี้คือคำสำคัญในการเข้าใจแนวคิดของ doubly linked list

• Link – แต่ละลิงก์ของ linked list สามารถเก็บข้อมูลที่เรียกว่า element
• Next – แต่ละลิงก์มีลิงก์ไปยังลิงก์ถัดไปเรียกว่า Next
• Prev – แต่ละลิงก์มีลิงก์ไปยังลิงก์ก่อนหน้าเรียกว่า Prev
• LinkedList – Linked List มีการเชื่อมต่อไปยังลิงก์แรกเรียกว่า First และลิงก์สุดท้ายเรียกว่า Last

การแสดงภาพของ Doubly Linked List –

คำอธิบายปัญหา – เราจะได้รับ doubly linked list ประเภทข้างต้น และเราจะหาขนาด (ความยาว) ของมัน

ตัวอย่างเพื่อความเข้าใจ

อินพุต

linked list ด้านบน A <-> B <-> C.

เอาต์พุต

3

วิธีแก้ปัญหา

เพื่อหาขนาดของ doubly linked list เราต้องเดินทาง (traverse) ผ่าน doubly linked list และนับความยาวด้วยตัวแปร length

อัลกอริทึม

Initialise – length = 0, *temp = head

• ขั้นตอนที่ 1 – วนลูปผ่านรายการ คือทำจนกว่า temp != NULL
  • ขั้นตอนที่ 1.1 – เพิ่ม length, length++
  • ขั้นตอนที่ 1.2 – อัปเดตพอยน์เตอร์, temp = temp -> next
• ขั้นตอนที่ 2 – แสดง length

โปรแกรมตัวอย่างการทำงานของวิธีแก้

ตัวอย่าง

#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