// 9. hét – Egyirányú (egyszerű) láncolt lista
// Futtatás: java SinglyLinkedList.java
public class SinglyLinkedList {

    // Listaelem: érték + mutató (referencia) a következő elemre
    static class Node {
        int value;
        Node next;

        Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    Node head = null; // üres lista: a fej null (Fej ← Nil)

    // Bejárás (feldolgozás) – O(n)
    //   P ← Fej ; Ciklus amíg P ≠ Nil : Feldolgoz(Elem[P].Érték) ; P ← Elem[P].Köv
    void print() {
        System.out.print("[");
        for (Node p = head; p != null; p = p.next) System.out.print(p.value + (p.next != null ? " -> " : ""));
        System.out.println("]");
    }

    int size() {
        int c = 0;
        for (Node p = head; p != null; p = p.next) c++;
        return c;
    }

    // Keresés – O(n). Az első x értékű elemet adja vissza, vagy null-t.
    Node find(int x) {
        Node p = head;
        while (p != null && p.value != x) p = p.next;
        return p;
    }

    // Beszúrás az elejére – O(1)
    void insertFirst(int x) {
        head = new Node(x, head); // új elem, amely a régi fejre mutat; a fej az új elem lesz
    }

    // Törlés az elejéről – O(1). A törölt értéket adja vissza.
    int removeFirst() {
        if (head == null) throw new IllegalStateException("üres lista");
        int x = head.value;
        head = head.next; // a régi első elemet a szemétgyűjtő (GC) szabadítja fel
        return x;
    }

    // Beszúrás a q elem mögé – O(1)
    void insertAfter(Node q, int x) {
        q.next = new Node(x, q.next); // 1. az új elem q régi rákövetkezőjére mutat; 2. q az új elemre
    }

    // Törlés a q elem mögül – O(1)
    void removeAfter(Node q) {
        if (q.next == null) throw new IllegalStateException("q mögött nincs elem");
        q.next = q.next.next;
    }

    // Beszúrás a végére – O(n), mert el kell jutni az utolsó elemig
    void insertLast(int x) {
        Node n = new Node(x, null);
        if (head == null) {
            head = n;
            return;
        }
        Node p = head;
        while (p.next != null) p = p.next;
        p.next = n;
    }

    // Törlés a végéről – O(n): az UTOLSÓ ELŐTTI elemet kell megtalálni
    int removeLast() {
        if (head == null) throw new IllegalStateException("üres lista");
        if (head.next == null) {
            int x = head.value;
            head = null;
            return x;
        }
        Node p = head;
        while (p.next.next != null) p = p.next;
        int x = p.next.value;
        p.next = null;
        return x;
    }

    // Adott értékű elem törlése – O(n): a keresés közben az előzőt is meg kell jegyezni
    boolean remove(int x) {
        Node prev = null, p = head;
        while (p != null && p.value != x) {
            prev = p;
            p = p.next;
        }
        if (p == null) return false;          // nincs ilyen elem
        if (prev == null) head = p.next;      // az első elemet töröljük
        else prev.next = p.next;
        return true;
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.print();
        list.insertFirst(31);
        list.insertFirst(7);
        list.insertFirst(12);
        System.out.print("3 × insertFirst:     ");
        list.print();

        list.insertLast(5);
        System.out.print("insertLast(5):       ");
        list.print();

        Node q = list.find(7);
        list.insertAfter(q, 99);
        System.out.print("insertAfter(7, 99):  ");
        list.print();

        list.removeAfter(q);
        System.out.print("removeAfter(7):      ");
        list.print();

        System.out.println("removeFirst() = " + list.removeFirst() + ", removeLast() = " + list.removeLast());
        list.print();
        System.out.println("find(31) = " + (list.find(31) != null) + ", find(100) = " + (list.find(100) != null) + ", size = " + list.size());
        list.remove(7);
        System.out.print("remove(7):           ");
        list.print();
    }
}