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

  /* Vezane liste - Primjer 2.
     Slozenije operacije s vezanom listom:
     - trazenje elementa u listi,
     - kreiranje i brisanje elemenata bilo gdje (iza nekog).
  */

/* ======================================================================== */

    /* Tip za pokazivac na element liste. */

typedef struct _element *lista;

    /* Tip za element liste. */

typedef struct _element {
    int broj;            /* Sadrzaj je broj. */
    lista sljed;         /* Pokazivac na sljedeci element u listi. */
} element;

/* ======================================================================== */

lista kreiraj_novi(int broj)
{
    lista novi = NULL;
/*
    if ((novi = (lista) malloc(sizeof(element))) == NULL)
*/
    novi = (lista) malloc(sizeof(element));
    if (novi == NULL) {
        printf("Alokacija nije uspjela.\n");
        exit(EXIT_FAILURE);    /* exit(1); */
    }

    novi->broj = broj;
    novi->sljed = NULL;

    return novi;
}

/* ======================================================================== */

lista kreiraj_sprijeda(lista prvi, int broj)
{
    lista novi = NULL;
/*
    if ((novi = (lista) malloc(sizeof(element))) == NULL)
*/
    novi = (lista) malloc(sizeof(element));
    if (novi == NULL) {
        printf("Alokacija nije uspjela.\n");
        exit(EXIT_FAILURE);    /* exit(1); */
    }

    novi->broj = broj;
    novi->sljed = prvi;

        /* Ne treba prvi = novi, vec samo ovo: */
    return novi;
}

/* ======================================================================== */

lista obrisi_listu(lista prvi)
{
    lista pom;
/*
    while (prvi != NULL)
        prvi = obrisi_prvog(prvi);
*/
    while (prvi != NULL) {
        pom = prvi;
        prvi = prvi->sljed;
        free(pom);
    }

    return NULL;    /* <=> return prvi; */
}

/* ======================================================================== */

int broj_elemenata(lista prvi)
{
    lista pom;
    int brojac = 0;

    for (pom = prvi; pom != NULL; pom = pom->sljed)
        ++brojac;

    return brojac;
}

/* ======================================================================== */

void ispisi_listu(lista prvi)
{
    lista pom;
    int brojac = 0;

    for (pom = prvi; pom != NULL; pom = pom->sljed) {
        printf(" Element %2d, broj = %2d\n",
               ++brojac, pom->broj);
    }

    return;
}

/* ======================================================================== */

lista trazi_broj(lista prvi, int broj)
{
    lista pom = prvi;

    while (pom != NULL && pom->broj != broj)
        pom = pom->sljed;

    return pom;
}

/* ======================================================================== */

lista trazi_zadnji(lista prvi)
{
    lista pom;

    if (prvi == NULL) return NULL;

    for (pom = prvi; pom->sljed != NULL; pom = pom->sljed);

    return pom;
}

/* ======================================================================== */

lista ubaci_iza(lista prvi, lista preth, lista novi)
{
        /* Ne provjerava novi != NULL. */

        /* Ako je preth == NULL, ubacujemo na pocetak. */
    if (preth == NULL) {
        novi->sljed = prvi;
        prvi = novi;
    }
    else {
        novi->sljed = preth->sljed;
        preth->sljed = novi;
    }

    return prvi;
}

/* ======================================================================== */

lista obrisi_iza(lista prvi, lista preth)
{
    lista pom;

        /* Ako je preth == NULL, brisemo prvi element. */
    if (preth == NULL) {
        pom = prvi;
        prvi = prvi->sljed;
    }
    else {
        pom = preth->sljed;
        preth->sljed = pom->sljed;
    }
    free(pom);

    return prvi;
}

/* ======================================================================== */

int main(void)
{
    lista prvi = NULL;    /* Prazna lista! */
    int broj;
    lista trazeni, novi;

        /* Punjenje liste sprijeda. */

        /* Citanje niza brojeva za listu, do broj = 0.
           To je oznaka kraj niza, ali nije clan niza. */
        /* Poredak brojeva u listi je obratan od redoslijeda
           citanja, jer dodajemo na pocetak liste. */

    printf("Upisite niz cijelih brojeva (0 = kraj).\n");
    do {
        printf("Sljedeci broj:\n");
        scanf("%d", &broj);
        if (broj != 0)
            prvi = kreiraj_sprijeda(prvi, broj);
    } while (broj != 0);

        /* Ispis broja elemenata i cijele liste. */

    printf("\n");
    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata(prvi));
    ispisi_listu(prvi);


        /* Trazenje po listi. */

    printf("\n");

        /* Trazi broj u listi. */

    trazeni = trazi_broj(prvi, 7);
    if (trazeni == NULL)
        printf(" Broj nije u listi.\n");
    else
        printf(" Nasli broj %d u listi.\n",
               trazeni->broj);


        /* Ubacivanje u listu. */

    printf("\n");

        /* Ubaci novi element sa zadanim brojem
           iza zadanog mjesta u listi. */

    novi = kreiraj_novi(11);
    prvi = ubaci_iza(prvi, trazeni, novi);
    printf(" Ubacen 11 iza 7.\n");

        /* Ubaci novi element sa zadanim brojem
           na prvo mjesto u listi. */

    novi = kreiraj_novi(12);
    prvi = ubaci_iza(prvi, NULL, novi);
    printf(" Ubacen 12 kao prvi.\n");

        /* Ubaci novi element sa zadanim brojem
           iza zadnjeg mjesta u listi. */

    novi = kreiraj_novi(20);
    trazeni = trazi_zadnji(prvi);
    prvi = ubaci_iza(prvi, trazeni, novi);
    printf(" Ubacen 20 kao zadnji.\n");

    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata(prvi));
    ispisi_listu(prvi);


        /* Izbacivanje (brisanje) iz liste. */

    printf("\n");

        /* Obrisi element iza elementa sa
           zadanim brojem u listi. */

    trazeni = trazi_broj(prvi, 11);
    prvi = obrisi_iza(prvi, trazeni);
    printf(" Obrisan element iza 11.\n");

        /* Obrisi prvi element u listi. */

    prvi = obrisi_iza(prvi, NULL);
    printf(" Obrisan prvi element.\n");

    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata(prvi));
    ispisi_listu(prvi);

        /* Obrisi cijelu listu. */

    prvi = obrisi_listu(prvi);

    return 0;
}