โปรแกรมหาผลรวมโหนดใน Circular Linked List ด้วย C++

ภาพรวมปัญหา

โปรแกรมนี้คำนวณผลรวมของค่าข้อมูล (data) ทุกโหนดใน Circular Linked List ซึ่งเป็น Linked List ที่โหนดสุดท้ายชี้กลับไปหาโหนดแรก (Head)

โครงสร้างโหนด

struct Node {
    int data;
    Node* next;
};

ลักษณะ Circular Linked List

• ไม่มี NULL pointer ที่ปลาย (Last->next = Head)
• ต้องมีเงื่อนไขหยุดการวนลูป (Stop when back to Head)
• อาจมี Head Pointer ชี้ไปโหนดแรก

อัลกอริทึมการหาผลรวม

SUM_CIRCULAR_LIST(head):
    IF head == NULL: RETURN 0
    sum = 0
    current = head
    DO:
        sum += current->data
        current = current->next
    WHILE current != head
    RETURN sum

ใช้ Do-While Loop เพราะต้อง Process Head Node ก่อนตรวจสอบเงื่อนไข

ฟังก์ชันเพิ่มโหนด (Insert at Front)

void push(Node** headRef, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->next = *headRef;
    
    if (*headRef != NULL) {
        // หาโหนดสุดท้ายเพื่อเชื่อม Circular
        Node* temp = *headRef;
        while (temp->next != *headRef) {
            temp = temp->next;
        }
        temp->next = newNode;
    } else {
        // First Node: ชี้ตัวเอง
        newNode->next = newNode;
    }
    *headRef = newNode;
}

ตัวอย่างโค้ด C++ สมบูรณ์

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    
    Node(int val) : data(val), next(nullptr) {}
};

void push(Node** headRef, int data) {
    Node* newNode = new Node(data);
    newNode->next = *headRef;
    
    if (*headRef != nullptr) {
        Node* temp = *headRef;
        while (temp->next != *headRef) {
            temp = temp->next;
        }
        temp->next = newNode;
    } else {
        newNode->next = newNode;  // Point to itself
    }
    *headRef = newNode;
}

int sumCircularList(Node* head) {
    if (head == nullptr) return 0;
    
    int sum = 0;
    Node* current = head;
    
    do {
        sum += current->data;
        current = current->next;
    } while (current != head);
    
    return sum;
}

void printList(Node* head) {
    if (head == nullptr) {
        cout << "Empty List\n";
        return;
    }
    
    Node* current = head;
    cout << "Circular List: ";
    do {
        cout << current->data << " → ";
        current = current->next;
    } while (current != head);
    cout << "(back to head)\n";
}

int main() {
    Node* head = nullptr;
    
    // สร้างรายการ: 14 → 1 → 7 → 9 → 2 → 6 → (back to 14)
    // Push ทีละตัว จะได้ลำดับย้อนกลับ
    push(&head, 6);
    push(&head, 2);
    push(&head, 9);
    push(&head, 7);
    push(&head, 1);
    push(&head, 14);
    
    printList(head);
    
    int sum = sumCircularList(head);
    cout << "Sum of all nodes = " << sum << endl;
    // 14 + 1 + 7 + 9 + 2 + 6 = 39
    
    // ทดสอบรายการว่าง
    Node* emptyHead = nullptr;
    cout << "Empty list sum = " << sumCircularList(emptyHead) << endl;
    
    // ทดสอบรายการ 1 โหนด
    Node* single = nullptr;
    push(&single, 42);
    cout << "Single node list: ";
    printList(single);
    cout << "Sum = " << sumCircularList(single) << endl;
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Circular List: 14 → 1 → 7 → 9 → 2 → 6 → (back to head)
Sum of all nodes = 39
Empty list sum = 0
Single node list: 42 → (back to head)
Sum = 42

การ Insert แบบอื่นๆ

Insert at End (Append)

void append(Node** headRef, int data) {
    Node* newNode = new Node(data);
    if (*headRef == nullptr) {
        newNode->next = newNode;
        *headRef = newNode;
        return;
    }
    
    Node* last = *headRef;
    while (last->next != *headRef) {
        last = last->next;
    }
    last->next = newNode;
    newNode->next = *headRef;
}

Insert After Given Node

void insertAfter(Node* prevNode, int data) {
    if (prevNode == nullptr) return;
    
    Node* newNode = new Node(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

ความซับซ้อนของอัลกอริทึม

* Push Front ต้องหา Last Node ก่อน O(n) - สามารถปรับปรุงได้ด้วย Tail Pointer

การปรับปรุง: เก็บ Tail Pointer

struct CircularList {
    Node* head;
    Node* tail;  // เก็บ Tail ไว้
    
    void pushFront(int data) {
        Node* newNode = new Node(data);
        if (!head) {
            head = tail = newNode;
            newNode->next = newNode;
        } else {
            newNode->next = head;
            tail->next = newNode;
            head = newNode;
        }
    }
    // Push Front กลายเป็น O(1)
};

การประยุกต์ใช้

• Round Robin Scheduling - Process Queue
• Music Playlist - Repeat Playlist
• Token Ring Network - Network Protocol
• Game Turn Management - Player Rotation
• Resource Pooling - Connection Pool

ข้อควรระวัง

• Infinite Loop Risk - ต้องมีเงื่อนไขหยุดที่ชัดเจน (current != head)
• Memory Leak - ต้อง Delete โหนดทุกตัวเมื่อไม่ใช้
• Empty List - Head = NULL, ต้องตรวจสอบก่อนเข้าถึง
• Single Node - Next ชี้ตัวเอง, Logic ต้องรองรับ