#include <iostream>

#include <conio.h>

#include <iomanip>   //digunakan untuk mengatur lebar tampilan --> setw()

#include <math.h>     //operasi matematik dasar

#include <stdlib.h>   //pemanggilan fungsi malloc --> memberikan batsan memori dalam byte

using namespace std;

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

node * head;
node * tail;
node * curr;
node * curr2;
node * curr3;
node * curr4;
node * entry;
node * del;
node * simpan_pos1;
node * simpan_pos2;
node * simpan_pos3;
node * mm1;

void inisialisasi() {
    head = NULL;
    tail = NULL;
}

void input(int dt) {
    entry = (node * ) malloc(sizeof(node));
    entry -> data = dt;
    entry -> next = NULL;
    if (head == NULL) {
        head = entry;
        tail = head;
    } else {
        tail -> next = entry;
        tail = entry;
    }
}

void cetak() {
    curr = head;
    if (head == NULL)
        cout << "\nData kosong" << endl;
    else {
        cout << "\nData dalam linked list adalah" << endl;
        cout << setw(6);
        while (curr != NULL) {
            cout << curr -> data << "->";
            curr = curr -> next;
        }
        cout << "NULL";
        cout << endl;
    }
}

int hitung_node() {
    int jumlah = 0;
    curr = head;
    while (curr != NULL) {
        jumlah++;
        curr = curr -> next;
    }

    return (jumlah);
}

void hapus() {
    int simpan;
    if (head == NULL) {
        cout << "\nData kosong" << endl;
    } else {
        simpan = head -> data;
        cout << "\nData yang dihapus adalah " << simpan << endl;

        del = head;
        head = head -> next;
        delete del;
    }
}

void hapus_data_tengah() {
    float posisi_tengah;

    posisi_tengah = floor(hitung_node() / 2); //floor data dibulatkan kebawah

    int simpan, simpan2;
    if (head == NULL) {
        cout << "\nTidak ada data yang bisa dihapus" << endl;
    } else {
        if (hitung_node() <= 2) {
            hapus();
        } else if (hitung_node() == 3) {
            curr2 = head;
            simpan_pos1 = curr2 -> next;
            curr2 -> next = curr2 -> next -> next;

            simpan2 = simpan_pos1 -> data;
            cout << "\nData yang dihapus adalah " << simpan2 << endl;

            simpan_pos1 -> next = NULL;
            delete simpan_pos1;
        } else if (hitung_node() > 3) {
            curr3 = head;
            for (float i = 0; i < posisi_tengah - 1; i++) {
                curr3 = curr3 -> next;
                simpan_pos2 = curr3;
            }

            curr4 = head;
            for (float i = 0; i < posisi_tengah; i++) {
                curr4 = curr4 -> next;
                simpan_pos3 = curr4;
            }

            simpan = simpan_pos3 -> data;
            cout << "\ndata yang dihapus adalah " << simpan << endl;

            simpan_pos2 -> next = simpan_pos3 -> next;

            //hapus node
            simpan_pos3 -> next = NULL; //memutus hubungan node sebelum dihapus
            del = simpan_pos3;
            delete del;
        }
    }
}
void tambah_data_tengah(int num){
    float posisi_tengah;
    posisi_tengah = floor(hitung_node() / 2); //floor data dibulatkan kebawah
    int i = 0;

    // reset
    mm1 = tail;
    curr = head;
    head = NULL;

    while (curr != NULL) {
        input(curr -> data);
        i++;
        if(i == posisi_tengah){
            input(num);
        }
        curr = curr -> next;
    }
}
void menu() {
    char pilih, ulang;
    int data;

    do {
        system("cls");
        cout << "SINGLE LINKED LIST by Sulis" << endl;
        cout << "-------------------------------" << endl;
        cout << "Menu : " << endl;
        cout << "1. Input data depan" << endl;
        cout << "2. Cetak data" << endl;
        cout << "3. Hapus data tengah" << endl;
        cout << "4. Tambah data tengah" << endl;
        cout << "5. Exit" << endl;
        cout << "Masukkan pilihan Anda : ";
        cin >> pilih;

        switch (pilih) {
        case '1':
            cout << "\nMasukkan data : ";
            cin >> data;
            input(data);
            break;
        case '2':
            cetak();
            break;
        case '3':
            hapus_data_tengah();
            break;
        case '4':
            cout << "\nMasukkan data yg akan ditambahkan ke data tengah : ";
            cin >> data;
            tambah_data_tengah(data);
            break;
        case '5':
            exit(0);
            break;
        default:
            cout << "\nPilih ulang" << endl;
        }
        cout << "\nKembali ke menu?(y/n)";
        cin >> ulang;
    } while (ulang == 'y' || ulang == 'Y');
}

int main() {
    inisialisasi();
//    input(81);
//    input(82);
//    input(83);
//    input(84);
//    input(85);
//    input(86);
//    input(87);
//    input(88);
    menu();

    return EXIT_SUCCESS;
}