Strefa wyzwań - I_R_W13A_M03_JAVA Zaawansowane struktury danych

R1KSK8bTfIKoK

Już wiesz

Jakie są rodzaje struktur danych.
Jak scharakteryzować możliwości i przykładowe zastosowania podstawowych struktur danych.
Jaka jest terminologia związaną z podstawowymi strukturami danych.
Jak zapimplementować w języku Java dynamiczne struktury danych, takie jak lista, stos, kolejka.

Ćwiczenie 1

Zapisz metody zwrocGlowa() i zwrocOgon, które zwrócą wartości zapisane odpowiednio w pierwszym i ostatnim elemencie listy niecyklicznej jednokierunkowej bez ich usuwania. Jeżeli lista jest pusta, metody powinny zwrócić minimalną wartość całkowitą.

Działanie programu przetestuj dla listy, do której dodasz kolejno wartości 3, 5, 8.

Poprawny wynik działania programu:

Głowa: 3
Ogon: 8

RFIeJYJJenyOq

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. this kropka liczba znak równości liczba średnik. Linia 6. this kropka nastepny znak równości null średnik. Linia 7. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. class Lista otwórz nawias klamrowy. Linia 12. Wezel glowa średnik. Linia 13. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. glowa znak równości null średnik. Linia 15. zamknij nawias klamrowy. Linia 17. public void dodaj otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 20. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. glowa znak równości nowy średnik. Linia 22. return średnik. Linia 23. zamknij nawias klamrowy. Linia 24. Wezel pomocniczy znak równości glowa średnik. Linia 25. while otwórz nawias okrągły pomocniczy kropka nastepny wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 27. zamknij nawias klamrowy. Linia 28. pomocniczy kropka nastepny znak równości nowy średnik. Linia 29. zamknij nawias klamrowy. Linia 31. public int zwrocGlowa otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły return Integer kropka MIN podkreślnik VALUE średnik. Linia 33. return glowa kropka liczba średnik. Linia 34. zamknij nawias klamrowy. Linia 36. public int zwrocOgon otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły return Integer kropka MIN podkreślnik VALUE średnik. Linia 38. Wezel pomocniczy znak równości glowa średnik. Linia 39. while otwórz nawias okrągły pomocniczy kropka nastepny wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 41. zamknij nawias klamrowy. Linia 42. return pomocniczy kropka liczba średnik. Linia 43. zamknij nawias klamrowy. Linia 45. zamknij nawias klamrowy. Linia 47. public class Cwiczenie1 otwórz nawias klamrowy. Linia 48. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 50. lista kropka dodaj otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 51. lista kropka dodaj otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 52. lista kropka dodaj otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 53. System kropka out kropka println otwórz nawias okrągły cudzysłów Głowa dwukropek cudzysłów plus lista kropka zwrocGlowa otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 54. System kropka out kropka println otwórz nawias okrągły cudzysłów Ogon dwukropek cudzysłów plus lista kropka zwrocOgon otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 55. zamknij nawias klamrowy. Linia 56. zamknij nawias klamrowy.

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }

}

class Lista {
Wezel glowa;
    public Lista() {
        glowa = null;
    }
    
    public void dodaj(int liczba) {
        Wezel nowy = new Wezel(liczba);
    
        if (glowa == null) {
            glowa = nowy;
            return;
        }
        Wezel pomocniczy = glowa;
        while (pomocniczy.nastepny != null) {
            pomocniczy = pomocniczy.nastepny;
        }
        pomocniczy.nastepny = nowy;
    }
    
    public int zwrocGlowa() {
        if (glowa == null) return Integer.MIN_VALUE;
        return glowa.liczba;
    }
    
    public int zwrocOgon() {
        if (glowa == null) return Integer.MIN_VALUE;
        Wezel pomocniczy = glowa;
        while (pomocniczy.nastepny != null) {
            pomocniczy = pomocniczy.nastepny;
        }
        return pomocniczy.liczba;
    }

}

public class Cwiczenie1 {
    public static void main(String[] args) {
        Lista lista = new Lista();
        lista.dodaj(3);
        lista.dodaj(5);
        lista.dodaj(8);
        System.out.println("Głowa: " + lista.zwrocGlowa());
        System.out.println("Ogon: " + lista.zwrocOgon());
    }
}

Ćwiczenie 2

Zapisz metodę podajRozmiar(), która zwróci liczbę elementów zapisanych w liście niecyklicznej jednokierunkowej.

Działanie programu przetestuj dla listy jednokierunkowej, do której dodasz kolejno wartości 1, 2, 3.

Poprawny wynik działania programu:

Rozmiar: 3

R1SH8IpCqmNmB

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }

}

class Lista {
Wezel glowa;
    public Lista() {
        glowa = null;
    }
    
    public void dodaj(int liczba) {
        Wezel nowy = new Wezel(liczba);
    
        if (glowa == null) {
            glowa = nowy;
            return;
        }
        Wezel pomocniczy = glowa;
        while (pomocniczy.nastepny != null) {
            pomocniczy = pomocniczy.nastepny;
        }
        pomocniczy.nastepny = nowy;
    }
    
    public int podajRozmiar() {
        Wezel pomocniczy = glowa;
        int rozmiar = 0;
    
        if (glowa == null) return 0;
    
        while (pomocniczy != null) {
            pomocniczy = pomocniczy.nastepny;
            rozmiar++;
        }
        return rozmiar;
    }

}

public class Cwiczenie2 {
    public static void main(String[] args) {
        Lista lista = new Lista();
        lista.dodaj(1);
        lista.dodaj(2);
        lista.dodaj(3);
        System.out.println("Rozmiar: " + lista.podajRozmiar());
    }
}

Ćwiczenie 3

Zapisz metodę usunOstatni(), która usuwać będzie ostatni element listy niecyklicznej jednokierunkowej i zwróci zapisaną w nim wartość lub minimalną wartość całkowitą, jeżeli lista będzie pusta.

Działanie programu przetestuj dla listy, do której dodasz kolejno wartości 1, 2, 3, a następnie usuniesz dwa ostatnio dodane elementy.

Poprawny wynik działania programu:

Lista: 1

R8GjSNFjKnXpX

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. this kropka liczba znak równości liczba średnik. Linia 6. this kropka nastepny znak równości null średnik. Linia 7. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. class Lista otwórz nawias klamrowy. Linia 12. Wezel glowa średnik. Linia 13. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. glowa znak równości null średnik. Linia 15. zamknij nawias klamrowy. Linia 17. public void dodaj otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 20. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. glowa znak równości nowy średnik. Linia 22. return średnik. Linia 23. zamknij nawias klamrowy. Linia 24. Wezel pomocniczy znak równości glowa średnik. Linia 25. while otwórz nawias okrągły pomocniczy kropka nastepny wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 27. zamknij nawias klamrowy. Linia 28. pomocniczy kropka nastepny znak równości nowy średnik. Linia 29. zamknij nawias klamrowy. Linia 31. public void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. System kropka out kropka println otwórz nawias okrągły cudzysłów Lista jest pusta cudzysłów zamknij nawias okrągły średnik. Linia 34. return średnik. Linia 35. zamknij nawias klamrowy. Linia 37. System kropka out kropka print otwórz nawias okrągły cudzysłów Lista dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 38. Wezel pomocniczy znak równości glowa średnik. Linia 39. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. System kropka out kropka print otwórz nawias okrągły pomocniczy kropka liczba plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 41. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 42. zamknij nawias klamrowy. Linia 43. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 44. zamknij nawias klamrowy. Linia 46. public int usunOstatni otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 47. Wezel pomocniczy1 znak równości glowa przecinek pomocniczy2 znak równości null średnik. Linia 48. int liczba znak równości Integer kropka MIN podkreślnik VALUE średnik. Linia 50. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły return liczba średnik. Linia 52. if otwórz nawias okrągły pomocniczy1 kropka nastepny znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 53. liczba znak równości pomocniczy1 kropka liczba średnik. Linia 54. glowa znak równości null średnik. Linia 55. return liczba średnik. Linia 56. zamknij nawias klamrowy. Linia 57. while otwórz nawias okrągły pomocniczy1 kropka nastepny wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 58. pomocniczy2 znak równości pomocniczy1 średnik. Linia 59. pomocniczy1 znak równości pomocniczy1 kropka nastepny średnik. Linia 60. zamknij nawias klamrowy. Linia 61. pomocniczy2 kropka nastepny znak równości null średnik. Linia 62. liczba znak równości pomocniczy1 kropka liczba średnik. Linia 63. return liczba średnik. Linia 64. zamknij nawias klamrowy. Linia 66. zamknij nawias klamrowy. Linia 68. public class Main otwórz nawias klamrowy. Linia 69. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 70. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 71. lista kropka dodaj otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 72. lista kropka dodaj otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 73. lista kropka dodaj otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 74. lista kropka usunOstatni otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 75. lista kropka usunOstatni otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 76. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 77. zamknij nawias klamrowy. Linia 78. zamknij nawias klamrowy.

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }

}

class Lista {
Wezel glowa;
    public Lista() {
        glowa = null;
    }
    
    public void dodaj(int liczba) {
        Wezel nowy = new Wezel(liczba);
    
        if (glowa == null) {
            glowa = nowy;
            return;
        }
        Wezel pomocniczy = glowa;
        while (pomocniczy.nastepny != null) {
            pomocniczy = pomocniczy.nastepny;
        }
        pomocniczy.nastepny = nowy;
    }
    
    public void wypisz() {
        if (glowa == null) {
            System.out.println("Lista jest pusta");
            return;
        }
    
        System.out.print("Lista: ");
        Wezel pomocniczy = glowa;
        while (pomocniczy != null) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println();
    }
    
    public int usunOstatni() {
        Wezel pomocniczy1 = glowa, pomocniczy2 = null;
        int liczba = Integer.MIN_VALUE;
    
        if (glowa == null) return liczba;
    
        if (pomocniczy1.nastepny == null) {
            liczba = pomocniczy1.liczba;
            glowa = null;
            return liczba;
        }
        while (pomocniczy1.nastepny != null) {
            pomocniczy2 = pomocniczy1;
            pomocniczy1 = pomocniczy1.nastepny;
        }
        pomocniczy2.nastepny = null;
        liczba = pomocniczy1.liczba;
        return liczba;
    }

}

public class Main {
    public static void main(String[] args) {
        Lista lista = new Lista();
        lista.dodaj(1);
        lista.dodaj(2);
        lista.dodaj(3);
        lista.usunOstatni();
        lista.usunOstatni();
        lista.wypisz();
    }
}

Ćwiczenie 4

Zapisz metodę odwroc(), która odwróci kolejność elementów listy niecyklicznej jednokierunkowej.

Działanie programu przetestuj dla listy, do której dodasz kolejno wartości 3, 5, 8.

Poprawny wynik działania programu:

Lista: 8 5 3

R1VEqsyK5GQ2g

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. this kropka liczba znak równości liczba średnik. Linia 6. this kropka nastepny znak równości null średnik. Linia 7. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. class Lista otwórz nawias klamrowy. Linia 12. Wezel glowa średnik. Linia 13. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. glowa znak równości null średnik. Linia 15. zamknij nawias klamrowy. Linia 17. public void dodaj otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 20. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. glowa znak równości nowy średnik. Linia 22. return średnik. Linia 23. zamknij nawias klamrowy. Linia 24. Wezel pomocniczy znak równości glowa średnik. Linia 25. while otwórz nawias okrągły pomocniczy kropka nastepny wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 27. zamknij nawias klamrowy. Linia 28. pomocniczy kropka nastepny znak równości nowy średnik. Linia 29. zamknij nawias klamrowy. Linia 31. public void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. System kropka out kropka print otwórz nawias okrągły cudzysłów Lista dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 33. Wezel pomocniczy znak równości glowa średnik. Linia 34. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. System kropka out kropka print otwórz nawias okrągły pomocniczy kropka liczba plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 36. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 37. zamknij nawias klamrowy. Linia 38. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 39. zamknij nawias klamrowy. Linia 41. public void odwroc otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 42. Wezel aktualny znak równości glowa przecinek poprzedni znak równości null przecinek nastepny znak równości null średnik. Linia 43. while otwórz nawias okrągły aktualny wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. nastepny znak równości aktualny kropka nastepny średnik. Linia 45. aktualny kropka nastepny znak równości poprzedni średnik. Linia 46. poprzedni znak równości aktualny średnik. Linia 47. aktualny znak równości nastepny średnik. Linia 48. zamknij nawias klamrowy. Linia 49. glowa znak równości poprzedni średnik. Linia 50. zamknij nawias klamrowy. Linia 52. zamknij nawias klamrowy. Linia 54. public class Cwiczenie4 otwórz nawias klamrowy. Linia 55. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 56. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 57. lista kropka dodaj otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 58. lista kropka dodaj otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 59. lista kropka dodaj otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 60. lista kropka odwroc otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 61. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 62. zamknij nawias klamrowy. Linia 63. zamknij nawias klamrowy.

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }

}

class Lista {
Wezel glowa;
    public Lista() {
        glowa = null;
    }
    
    public void dodaj(int liczba) {
        Wezel nowy = new Wezel(liczba);
    
        if (glowa == null) {
            glowa = nowy;
            return;
        }
        Wezel pomocniczy = glowa;
        while (pomocniczy.nastepny != null) {
            pomocniczy = pomocniczy.nastepny;
        }
        pomocniczy.nastepny = nowy;
    }
    
    public void wypisz() {
        System.out.print("Lista: ");
        Wezel pomocniczy = glowa;
        while (pomocniczy != null) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println();
    }
    
    public void odwroc() {
        Wezel aktualny = glowa, poprzedni = null, nastepny = null;
        while (aktualny != null) {
            nastepny = aktualny.nastepny;
            aktualny.nastepny = poprzedni;
            poprzedni = aktualny;
            aktualny = nastepny;
        }
        glowa = poprzedni;
    }

}

public class Cwiczenie4 {
    public static void main(String[] args) {
        Lista lista = new Lista();
        lista.dodaj(3);
        lista.dodaj(5);
        lista.dodaj(8);
        lista.odwroc();
        lista.wypisz();
    }
}

Ćwiczenie 5

Zapisz metodę wypiszWstecz(), która wypisuje elementy listy niecyklicznej dwukierunkowej od końca.

Działanie programu przetestuj dla listy, do której dodasz kolejno wartości 13, 8, 5.

Poprawny wynik działania programu:

Lista: 5 8 13

ReGK6k0oN7WXC

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel poprzedni;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
        this.poprzedni = null;
    }

}

class Lista {
Wezel glowa;
Wezel ogon;
    public Lista() {
        glowa = ogon = null;
    }
    
    public void dodaj(int liczba) {
        Wezel nowy = new Wezel(liczba);
    
        if (glowa == null) {
            glowa = ogon = nowy;
            return;
        }
        ogon.nastepny = nowy;
        nowy.poprzedni = ogon;
        ogon = nowy;
    }
    
    public void wypiszWstecz() {
        Wezel pomocniczy = ogon;
        if (glowa == null) return;
        System.out.print("Lista: ");
        while (pomocniczy.poprzedni != null) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.poprzedni;
        }
        System.out.println(pomocniczy.liczba);
    }

}

public class Cwiczenie5 {
    public static void main(String[] args) {
        Lista lista = new Lista();
        lista.dodaj(13);
        lista.dodaj(8);
        lista.dodaj(5);
        lista.wypiszWstecz();
    }
}

Ćwiczenie 6

Zapisz metodę wypiszRekursywnie(), która wypisze elementy listy jednokierunkowej w odwrotnej kolejności, tj. od ogona do głowy. W rozwiązaniu wykorzystaj rekurencję i wywołaj napisaną metodę w metodzie głównej.

Działanie programu przetestuj dla listy, do której dodasz kolejno wartości 8, 13, 2.

Poprawny wynik działania programu:

21 13 8

Rz2ttZIROzixq

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }

}

class Lista {
Wezel glowa;
    public Lista() {
        glowa = null;
    }
    
    public void dodaj(int liczba) {
        Wezel nowy = new Wezel(liczba);
    
        if (glowa == null) {
            glowa = nowy;
            return;
        }
        Wezel pomocniczy = glowa;
        while (pomocniczy.nastepny != null) {
            pomocniczy = pomocniczy.nastepny;
        }
        pomocniczy.nastepny = nowy;
    }

}

public class Main {
    public static void wypiszRekursywnie(Wezel wezel) {
        if (wezel != null) {
            wypiszRekursywnie(wezel.nastepny);
            System.out.print(wezel.liczba + " ");
        }
        else 
            System.out.print("Lista jest pusta");
    }
    
    public static void main(String[] args) {
        Lista lista = new Lista();
        lista.dodaj(8);
        lista.dodaj(13);
        lista.dodaj(21);
        wypiszRekursywnie(lista.glowa);
    }

}

Ćwiczenie 7

Zapisz metodę wypiszOdWezla(wezel), która wypisuje elementy listy cyklicznej dwukierunkowej, zaczynając od węzła wskazywanego przez podaną referencję wezel. Jeśli metoda otrzyma jako argument referencję pustą (null), wypisywanie powinno rozpocząć się od pierwszego węzła listy.

Działanie programu przetestuj dla listy, do której dodasz kolejno wartości 13, 21, 34.

Poprawny wynik działania programu:

Lista: 21 34 13

R86oaSZ8kd2AZ

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel poprzedni średnik. Linia 5. Wezel otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka liczba znak równości liczba średnik. Linia 7. this kropka nastepny znak równości null średnik. Linia 8. this kropka poprzedni znak równości null średnik. Linia 9. zamknij nawias klamrowy. Linia 11. zamknij nawias klamrowy. Linia 13. class Lista otwórz nawias klamrowy. Linia 14. Wezel glowa średnik. Linia 15. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. glowa znak równości null średnik. Linia 17. zamknij nawias klamrowy. Linia 19. public void dodaj otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 22. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. glowa znak równości nowy średnik. Linia 24. glowa kropka nastepny znak równości glowa średnik. Linia 25. glowa kropka poprzedni znak równości glowa średnik. Linia 26. return średnik. Linia 27. zamknij nawias klamrowy. Linia 28. Wezel pomocniczy znak równości glowa kropka poprzedni średnik. Linia 29. nowy kropka nastepny znak równości glowa średnik. Linia 30. nowy kropka poprzedni znak równości pomocniczy średnik. Linia 31. glowa kropka poprzedni znak równości nowy średnik. Linia 32. pomocniczy kropka nastepny znak równości nowy średnik. Linia 33. zamknij nawias klamrowy. Linia 35. public void wypiszOdWezla otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły return średnik. Linia 38. System kropka out kropka print otwórz nawias okrągły cudzysłów Lista dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 40. if otwórz nawias okrągły wezel znak równości znak równości null zamknij nawias okrągły wezel znak równości glowa średnik. Linia 41. Wezel pomocniczy znak równości wezel średnik. Linia 43. while otwórz nawias okrągły pomocniczy kropka nastepny wykrzyknik znak równości wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. System kropka out kropka print otwórz nawias okrągły pomocniczy kropka liczba plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 45. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 46. zamknij nawias klamrowy. Linia 47. System kropka out kropka println otwórz nawias okrągły pomocniczy kropka liczba zamknij nawias okrągły średnik. Linia 48. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 52. public class Main otwórz nawias klamrowy. Linia 53. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 55. lista kropka dodaj otwórz nawias okrągły 13 zamknij nawias okrągły średnik. Linia 56. lista kropka dodaj otwórz nawias okrągły 21 zamknij nawias okrągły średnik. Linia 57. lista kropka dodaj otwórz nawias okrągły 34 zamknij nawias okrągły średnik. Linia 58. lista kropka wypiszOdWezla otwórz nawias okrągły lista kropka glowa kropka nastepny zamknij nawias okrągły średnik. Linia 59. zamknij nawias klamrowy. Linia 60. zamknij nawias klamrowy.

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel poprzedni;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
        this.poprzedni = null;
    }

}

class Lista {
Wezel glowa;
    public Lista() {
        glowa = null;
    }
    
    public void dodaj(int liczba) {
        Wezel nowy = new Wezel(liczba);
    
        if (glowa == null) {
            glowa = nowy;
            glowa.nastepny = glowa;
            glowa.poprzedni = glowa;
            return;
        }
        Wezel pomocniczy = glowa.poprzedni;
        nowy.nastepny = glowa;
        nowy.poprzedni = pomocniczy;
        glowa.poprzedni = nowy;
        pomocniczy.nastepny = nowy;
    }
    
    public void wypiszOdWezla(Wezel wezel) {
        
        if (glowa == null) return;
        System.out.print("Lista: ");
        
        if (wezel == null) wezel = glowa;
        Wezel pomocniczy = wezel;
        
        while (pomocniczy.nastepny != wezel) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println(pomocniczy.liczba);
    }

}

public class Main {
	public static void main(String[] args) {
        Lista lista = new Lista();
        lista.dodaj(13);
        lista.dodaj(21);
        lista.dodaj(34);
        lista.wypiszOdWezla(lista.glowa.nastepny);
    }
}

Ćwiczenie 8

Zapisz metodę usunWezel(wezel), która usuwa przekazany jako referencja węzeł z listy cyklicznej dwukierunkowej i zwraca wartość przechowywaną w tym węźle. W przypadku, gdy argumentem metody jest referencje pusta (null), metoda powinna usuwać pierwszy węzeł listy. Jeśli lista jest pusta, metoda powinna zwrócić minimalną wartość całkowitą reprezentowaną przez stałą Integer.MIN_VALUE.

Działanie programu przetestuj dla listy, do której dodasz kolejno wartości 13, 21, 34. Usuwanym węzłem powinien być węzeł znajdujący się bezpośrednio po głowie (jej następnik).

Poprawny wynik działania programu:

Lista: 13 34

RJOObZXywbNMq

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel poprzedni średnik. Linia 5. Wezel otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka liczba znak równości liczba średnik. Linia 7. this kropka nastepny znak równości null średnik. Linia 8. this kropka poprzedni znak równości null średnik. Linia 9. zamknij nawias klamrowy. Linia 11. zamknij nawias klamrowy. Linia 13. class Lista otwórz nawias klamrowy. Linia 14. Wezel glowa średnik. Linia 15. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. glowa znak równości null średnik. Linia 17. zamknij nawias klamrowy. Linia 19. public void dodaj otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 22. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. glowa znak równości nowy średnik. Linia 24. glowa kropka nastepny znak równości glowa średnik. Linia 25. glowa kropka poprzedni znak równości glowa średnik. Linia 26. return średnik. Linia 27. zamknij nawias klamrowy. Linia 28. Wezel pomocniczy znak równości glowa kropka poprzedni średnik. Linia 29. nowy kropka nastepny znak równości glowa średnik. Linia 30. nowy kropka poprzedni znak równości pomocniczy średnik. Linia 31. glowa kropka poprzedni znak równości nowy średnik. Linia 32. pomocniczy kropka nastepny znak równości nowy średnik. Linia 33. zamknij nawias klamrowy. Linia 35. public void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły return średnik. Linia 37. System kropka out kropka print otwórz nawias okrągły cudzysłów Lista dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 39. Wezel pomocniczy znak równości glowa średnik. Linia 40. while otwórz nawias okrągły pomocniczy kropka nastepny wykrzyknik znak równości glowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 41. System kropka out kropka print otwórz nawias okrągły pomocniczy kropka liczba plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 42. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 43. zamknij nawias klamrowy. Linia 44. System kropka out kropka println otwórz nawias okrągły pomocniczy kropka liczba zamknij nawias okrągły średnik. Linia 45. zamknij nawias klamrowy. Linia 47. public int usunWezel otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 48. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły return Integer kropka MIN podkreślnik VALUE średnik. Linia 49. if otwórz nawias okrągły wezel znak równości znak równości null zamknij nawias okrągły wezel znak równości glowa średnik. Linia 51. int liczba znak równości wezel kropka liczba średnik. Linia 53. wezel kropka nastepny kropka poprzedni znak równości wezel kropka poprzedni średnik. Linia 54. wezel kropka poprzedni kropka nastepny znak równości wezel kropka nastepny średnik. Linia 56. if otwórz nawias okrągły wezel znak równości znak równości glowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. if otwórz nawias okrągły glowa kropka nastepny wykrzyknik znak równości glowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 58. glowa znak równości glowa kropka nastepny średnik. Linia 59. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 60. glowa znak równości null średnik. Linia 61. zamknij nawias klamrowy. Linia 62. zamknij nawias klamrowy. Linia 64. return liczba średnik. Linia 65. zamknij nawias klamrowy. Linia 67. zamknij nawias klamrowy. Linia 69. public class Main otwórz nawias klamrowy. Linia 70. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 71. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 72. lista kropka dodaj otwórz nawias okrągły 13 zamknij nawias okrągły średnik. Linia 73. lista kropka dodaj otwórz nawias okrągły 21 zamknij nawias okrągły średnik. Linia 74. lista kropka dodaj otwórz nawias okrągły 34 zamknij nawias okrągły średnik. Linia 75. lista kropka usunWezel otwórz nawias okrągły lista kropka glowa kropka nastepny zamknij nawias okrągły średnik. Linia 76. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 77. zamknij nawias klamrowy. Linia 78. zamknij nawias klamrowy.

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel poprzedni;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
        this.poprzedni = null;
    }

}

class Lista {
Wezel glowa;
    public Lista() {
        glowa = null;
    }
    
    public void dodaj(int liczba) {
        Wezel nowy = new Wezel(liczba);
    
        if (glowa == null) {
            glowa = nowy;
            glowa.nastepny = glowa;
            glowa.poprzedni = glowa;
            return;
        }
        Wezel pomocniczy = glowa.poprzedni;
        nowy.nastepny = glowa;
        nowy.poprzedni = pomocniczy;
        glowa.poprzedni = nowy;
        pomocniczy.nastepny = nowy;
    }
    
    public void wypisz() {
        if (glowa == null) return;
        System.out.print("Lista: ");
    
        Wezel pomocniczy = glowa;
        while (pomocniczy.nastepny != glowa) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println(pomocniczy.liczba);
    }
    
    public int usunWezel(Wezel wezel) {
        if (glowa == null) return Integer.MIN_VALUE;
        if (wezel == null) wezel = glowa;
    
        int liczba = wezel.liczba;
    
        wezel.nastepny.poprzedni = wezel.poprzedni;
        wezel.poprzedni.nastepny = wezel.nastepny;
    
        if (wezel == glowa) {
            if (glowa.nastepny != glowa) {
                glowa = glowa.nastepny;
            } else {
                glowa = null;
            }
        }
    
        return liczba;
    }

}

public class Main {
  public static void main(String[] args) {
   Lista lista = new Lista();
   lista.dodaj(13);
   lista.dodaj(21);
   lista.dodaj(34);
   lista.usunWezel(lista.glowa.nastepny);
   lista.wypisz();
  }
}

Misja: Porównujemy stos i stertę

I_R_W13A_M03_JAVA Zaawansowane struktury danych