#include <stdio.h>
#include <stdlib.h>

// 定義節點結構
typedef struct Node {
    int value;
    struct Node* next;
} Node;

// 定義鏈結串列結構
typedef struct {
    Node* head;
    int length;
    size_t memoryUsed;  // 新增：追蹤記憶體使用
} LinkedList;

int i;

// 函數原型
Node* createNode(int value);
void initLinkedList(LinkedList* list);
void push(LinkedList* list, int value);
Node* pop(LinkedList* list);
void unshift(LinkedList* list, int value);
Node* shift(LinkedList* list);
void insert(LinkedList* list, int index, int value);
Node* removeNode(LinkedList* list, int index);
void get(LinkedList* list, int index);
void printAll(LinkedList* list);
void freeLinkedList(LinkedList* list);

// 主函數
int main() {
    LinkedList list;
    initLinkedList(&list);
    int choice, value, index;

    while (1) {
        printf("\n鏈結串列操作菜單:\n");
        printf("1. Push (從尾部新增節點)\n");
        printf("2. Pop (從尾部移除節點)\n");
        printf("3. Unshift (從頭部新增節點)\n");
        printf("4. Shift (從頭部移除節點)\n");
        printf("5. Insert (在指定位置插入節點)\n");
        printf("6. Remove (移除指定位置的節點)\n");
        printf("7. Get (獲取指定位置的節點值)\n");
        printf("8. Print All (顯示所有節點)\n");
        printf("0. 退出\n");
        printf("請輸入你的選擇: ");
        scanf("%d", &choice);

        switch (choice) {
            case 0:
                printf("程式結束\n");
                freeLinkedList(&list);
                return 0;
            case 1:
                printf("輸入要新增的值: ");
                scanf("%d", &value);
                push(&list, value);
                break;
            case 2:
                {
                    Node* popped = pop(&list);
                    if (popped) {
                        printf("彈出的值: %d\n", popped->value);
                        free(popped);
                        list.memoryUsed -= sizeof(Node);
                    } else {
                        printf("串列為空\n");
                    }
                }
                break;
            case 3:
                printf("輸入要新增的值: ");
                scanf("%d", &value);
                unshift(&list, value);
                break;
            case 4:
                {
                    Node* shifted = shift(&list);
                    if (shifted) {
                        printf("移除的值: %d\n", shifted->value);
                        free(shifted);
                    } else {
                        printf("串列為空\n");
                    }
                }
                break;
            case 5:
                printf("輸入插入位置: ");
                scanf("%d", &index);
                printf("輸入要插入的值: ");
                scanf("%d", &value);
                insert(&list, index, value);
                break;
            case 6:
                printf("輸入要移除的位置: ");
                scanf("%d", &index);
                {
                    Node* removed = removeNode(&list, index);
                    if (removed) {
                        printf("移除的值: %d\n", removed->value);
                        free(removed);
                        list.memoryUsed -= sizeof(Node);
                    } else {
                        printf("無效的位置\n");
                    }
                }
                break;
            case 7:
                printf("輸入要獲取的位置: ");
                scanf("%d", &index);
                get(&list, index);
                break;
            case 8:
                printAll(&list);
                break;
            default:
                printf("無效的選擇,請重新輸入\n");
        }
    }

    return 0;
}

// 創建新節點
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("記憶體分配失敗\n");
        exit(1);
    }
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// 初始化鏈結串列
void initLinkedList(LinkedList* list) {
    list->head = NULL;
    list->length = 0;
    list->memoryUsed = 0;
}

// 從尾新增節點
void push(LinkedList* list, int value) {
    Node* newNode = createNode(value);
    if (list->length == 0) {
        list->head = newNode;
    } else {
        Node* currentNode = list->head;
        while (currentNode->next != NULL) {
            currentNode = currentNode->next;
        }
        currentNode->next = newNode;
    }
    list->length++;
    list->memoryUsed += sizeof(Node);
}

// 從尾移除節點
Node* pop(LinkedList* list) {
	
    if (list->length == 0) {
        return NULL;
    } else if (list->length == 1) {
        Node* temp = list->head;
        list->head = NULL;
        list->length = 0;
        return temp;
    } else {
        Node* currentNode = list->head;
        for (i = 1; i <= list->length - 2; i++) {
            currentNode = currentNode->next;
        }
        Node* temp = currentNode->next;
        currentNode->next = NULL;
        list->length--;
        return temp;
    }
}

// 從頭新增節點
void unshift(LinkedList* list, int value) {
    Node* newNode = createNode(value);
    if (list->length == 0) {
        list->head = newNode;
    } else {
        newNode->next = list->head;
        list->head = newNode;
    }
    list->length++;
    list->memoryUsed += sizeof(Node);
}

// 從頭移除節點
Node* shift(LinkedList* list) {
    if (list->length == 0) {
        return NULL;
    } else {
        Node* temp = list->head;
        list->head = list->head->next;
        list->length--;
        return temp;
    }
}

// 從中間新增節點
void insert(LinkedList* list, int index, int value) {
    if (index < 0 || index > list->length) {
        return;
    } else if (index == 0) {
        unshift(list, value);
    } else if (index == list->length) {
        push(list, value);
    } else {
        Node* newNode = createNode(value);
        Node* currentNode = list->head;
        for ( i = 0; i < index - 1; i++) {
            currentNode = currentNode->next;
        }
        newNode->next = currentNode->next;
        currentNode->next = newNode;
        list->length++;
    }
}

// 從中間移除節點
Node* removeNode(LinkedList* list, int index) {
    if (index < 0 || index >= list->length) {
        return NULL;
    } else if (index == 0) {
        return shift(list);
    } else if (index == list->length - 1) {
        return pop(list);
    } else {
        Node* currentNode = list->head;
        for ( i = 0; i < index - 1; i++) {
            currentNode = currentNode->next;
        }
        Node* temp = currentNode->next;
        currentNode->next = currentNode->next->next;
        list->length--;
        return temp;
    }
}

// 取得節點資訊
void get(LinkedList* list, int index) {
    if (index < 0 || index >= list->length) {
        printf("索引超出範圍\n");
    } else {
        Node* currentNode = list->head;
        for ( i = 0; i < index; i++) {
            currentNode = currentNode->next;
        }
        printf("索引 %d 的值: %d\n", index, currentNode->value);
    }
}

// 顯示鏈結串列完整資訊
void printAll(LinkedList* list) {
	

    if (list->length == 0) {
        printf("鏈結串列為空\n");
    } else {
        Node* currentNode = list->head;
        while (currentNode != NULL) {
            printf("%d ", currentNode->value);
            currentNode = currentNode->next;
        }
        printf("\n");
    }
}

// 新增：釋放整個鏈結串列
void freeLinkedList(LinkedList* list) {
    Node* current = list->head;
    while (current != NULL) {
        Node* temp = current;
        current = current->next;
        free(temp);
    }
    list->head = NULL;
    list->length = 0;
    list->memoryUsed = 0;
    printf("所有記憶體已釋放\n");
}