Implementacja listy - I_R_W13A_M03_JAVA Zaawansowane struktury danych

R1KSK8bTfIKoK

Lista

Przypomnijmy, że lista – podobnie jak stos i kolejka – jest liniową i dynamiczną strukturą danych. Elementami listy są węzły, które zawierają dane oraz referencję na element następny (w przypadku listy jednokierunkowej) lub na następny i poprzedni (w przypadku listy dwukierunkowej).

Do implementacji stosu i kolejki użyliśmy listy jednokierunkowej. Jej węzły zdefiniowaliśmy przy użyciu klasy zawierającej dwa pola i konstruktor argumentowy:

class Wezel {
    int liczba;
    Wezel nastepny;

    // Konstruktor argumentowy
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }
}

Konstruktor argumentowy wymaga podania argumentu podczas tworzenia obiektu, co pozwala zainicjować pole liczba otrzymaną wartością:

// Wykorzystanie konstruktora argumentowego
Wezel wezel = new Wezel(1);

Lista jednokierunkowa

Listę jednokierunkową implementujemy jako klasę z jednym polem glowa – wskazującym na pierwszy element listy. Oprócz tego w klasie definiujemy metody umożliwiające dodawanie, usuwanie i wypisywanie elementów listy. W konstruktorze Lista() inicjalizujemy pole glowa referencją pustą.

class Lista {
    Wezel glowa;

    public Lista() {
        glowa = null;
    }

    // Miejsce na metody
}

Metody czyPusta() oraz wypisz() działają tak samo jak w przypadku stosu i kolejki. Wyjaśnimy działanie metody dodającej węzły na końcu listy oraz usuwającej węzły o podanej pozycji.

Dodawanie węzłów na końcu listy jednokierunkowej

Metoda dodaj() jako argument będzie przyjmowała liczbę całkowitą. Nowy węzeł – inaczej niż w przypadku stosu i kolejki – będzie dodawany na końcu listy.

public void dodaj(int liczba) {
    System.out.println("Dodaję " + String.valueOf(liczba));

    // Tworzymy nowy węzeł
    Wezel nowy = new Wezel(liczba);

    // Jeżeli lista jest pusta
    if (czyPusta()) {
        glowa = nowy;
        return;
    }

    // W przeciwnym razie przejdź do ostatniego elementu
    Wezel pomocniczy = glowa;
    while (pomocniczy.nastepny != null) {
        pomocniczy = pomocniczy.nastepny;
    }

    // Dodajemy nowy węzeł na końcu listy
    pomocniczy.nastepny = nowy;
}

Na początku metody tworzymy nowy węzeł, przekazując do jego konstruktora otrzymaną liczbę. Następnie, jeżeli lista jest pusta, nowy węzeł staje się pierwszym elementem listy przypisanym do pola glowa.

W przeciwnym razie za pomocą węzła pomocniczy w pętli przechodzimy listę do ostatniego elementu, którego referencja nastepny będzie pusta. Po zakończeniu pętli pole nastepny dotychczasowego ostatniego elementu ustawiamy na nowy węzeł. W ten sposób dodajemy węzeł na końcu listy.

R1eSTXiWk4HIn

Ilustracja przedstawia schemat dodawania węzła do końca listy jednokierunkowej. Lista składa się z czterech elementów, gdzie element pierwszy jest głową, trzeci jest pomocniczy, a czwarty jest elementem nowym. Elementy połączone są strzałkami z podpisem następny. Przy czym element NULL znajdujący się po elemencie trzecim został skreślony, a nowy element NULL jest następny po nowym elemencie czwartym. — Schemat dodawania węzła do końca listy jednokierunkowej
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Usuwanie węzłów z listy jednokierunkowej

Metoda usuwająca węzły z listy otrzymywać będzie jako argument liczbę całkowitą wskazującą indeks czy też numer węzła, który chcemy usunąć. Przyjmijmy, że indeksy węzłów zaczynają się od 1.

public void usun(int indeks) {
    if (czyPusta()) return;

    System.out.println("Usuwam pozycję: " + Integer.toString(indeks));

    Wezel pomocniczy1 = glowa, pomocniczy2 = null;
    int rozmiar = 0;

    // Zliczamy elementy listy
    while (pomocniczy1 != null) {
        pomocniczy1 = pomocniczy1.nastepny;
        rozmiar++;
    }
    // Jeżeli indeks jest większy od rozmiaru listy
    if (indeks > rozmiar) {
        System.out.println("Indeks poza zakresem.");
        return;
    }

    // Poniżej dodamy kod usuwający elementy

}

Jeżeli lista nie jest pusta, definiujemy zmienne, których używamy w metodzie:

referencję pomocniczy1 ustawiamy na pierwszy element listy,
referencję pomocniczy2 wykorzystamy przy usuwaniu węzłów innych od pierwszego,
zmienna rozmiar posłuży do ustalenia rozmiaru listy.

Następnie zliczamy elementy listy za pomocą pętli while przechodzącej po wszystkich węzłach listy, zaczynając od pierwszego. Po dojściu do ostatniego elementu w zmiennej pomocniczy1 zostanie zapisana wartość null i pętla zakończy swoje działanie.

Ważne!

Warto zapamiętać omówioną pętlę, ponieważ przechodzenie wszystkich elementów listy, zaczynając od pierwszego, jest typową operacją wykonywaną na listach.

Następnie, jeżeli podany indeks nie jest większy od obliczonego rozmiaru listy, zaczynamy usuwanie węzła. Zadanie to realizuje kod, który umieszczamy na końcu omawianej metody:

    // Usuwanie pierwszego węzła
    if (indeks == 1) {
        glowa = glowa.nastepny;
        return;
    }

    // Szukanie węzła do usunięcia (innego niż pierwszy)
    pomocniczy1 = glowa;
    while (indeks-- > 1) {
        pomocniczy2 = pomocniczy1;
        pomocniczy1 = pomocniczy1.nastepny;
    }

    // Zmiana pola nastepny węzła poprzedzającego usuwany
    pomocniczy2.nastepny = pomocniczy1.nastepny;

Jeżeli usuwanym elementem jest pierwszy węzeł (indeks 1), pole glowa ustawiamy na następny węzeł, co powoduje wyłączenie dotychczasowego pierwszego elementu z listy.

W przeciwnym razie w pętli, która wykonuje się, dopóki indeks jest większy od 1, szukamy węzła do usunięcia. W każdej iteracji indeks jest zmniejszany o 1 dzięki notacji postfiksowej. Wewnątrz pętli przechodzimy po indeks - 1 elementach listy od jej początku, więc po jej zakończeniu zmienna pomocniczy1 będzie wskazywała węzeł do usunięcia, a zmienna pomocniczy2 węzeł poprzedni.

Po zakończeniu pętli w węźle poprzedzającym węzeł usuwany ustawiamy referencję nastepny na węzeł następny po węźle usuwanym (w przypadku usuwania ostatniego węzła będzie to wartość null).

Dla zainteresowanych

W językach programowania Java i Python nie trzeba usuwać węzłów i zwalniać zajmowanych przez niego pamięci za pomocą osobnej instrukcji takiej jak np. wyrażenie delete() w języku C++. Jeżeli na jakiś obiekt nie wskazują żadne referencje, zostanie on usunięty przez mechanizm odśmiecania pamięci (ang. garbage collection).

R1DT71fUbiSfA

Ilustracja przedstawia schemat usuwania węzła z listy jednokierunkowej. Lista składa się z czterech elementów, gdzie element pierwszy jest głową, drugi jest elementem pomocniczym dwa a trzeci jest elementem pomocniczym jeden. Element trzeci został przekreślony, wraz ze strzałką pomiędzy elementami pomocniczymi. Z elementu drugiego prowadzi nowa strzałka prosto do elementu czwartego. — Schemat usuwania węzła z listy jednokierunkowej
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 1

Wykorzystaj omówiony kod i przygotuj program pozwalający sprawdzić działanie listy jednokierunkowej. Dodaj do listy trzy liczby i wypisz listę. Następnie usuń drugi element i wypisz listę. Na końcu jeszcze raz usuń drugi element, dodaj liczbę i wypisz listę.

R1Og0RiM25SjP

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny ś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. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. class Lista otwórz nawias klamrowy. Linia 12. Wezel glowa średnik. Linia 14. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. glowa znak równości null średnik. Linia 16. zamknij nawias klamrowy. Linia 18. public boolean czyPusta otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. 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 20. System kropka out kropka println otwórz nawias okrągły cudzysłów Lista jest pusta wykrzyknik cudzysłów zamknij nawias okrągły średnik. Linia 21. zamknij nawias klamrowy. Linia 22. return otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły średnik. Linia 23. zamknij nawias klamrowy. Linia 25. public void dodaj otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. System kropka out kropka println otwórz nawias okrągły cudzysłów Dodaję cudzysłów plus String kropka valueOf otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 27. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 29. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. glowa znak równości nowy średnik. Linia 31. return średnik. Linia 32. zamknij nawias klamrowy. Linia 34. Wezel pomocniczy znak równości glowa średnik. Linia 35. 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 36. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 37. zamknij nawias klamrowy. Linia 39. pomocniczy kropka nastepny znak równości nowy średnik. Linia 40. zamknij nawias klamrowy. Linia 42. public void usun otwórz nawias okrągły int indeks zamknij nawias okrągły otwórz nawias klamrowy. Linia 43. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return średnik. Linia 45. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam pozycję dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły indeks zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 47. Wezel pomocniczy1 znak równości glowa przecinek pomocniczy2 znak równości null średnik. Linia 48. int rozmiar znak równości 0 średnik. Linia 50. while otwórz nawias okrągły pomocniczy1 wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 51. pomocniczy1 znak równości pomocniczy1 kropka nastepny średnik. Linia 52. rozmiar plus plus średnik. Linia 53. zamknij nawias klamrowy. Linia 55. if otwórz nawias okrągły indeks zamknij nawias ostrokątny rozmiar zamknij nawias okrągły otwórz nawias klamrowy. Linia 56. System kropka out kropka println otwórz nawias okrągły cudzysłów Indeks poza zakresem kropka cudzysłów zamknij nawias okrągły średnik. Linia 57. return średnik. Linia 58. zamknij nawias klamrowy. Linia 60. if otwórz nawias okrągły indeks znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. glowa znak równości glowa kropka nastepny średnik. Linia 62. return średnik. Linia 63. zamknij nawias klamrowy. Linia 64. pomocniczy1 znak równości glowa średnik. Linia 65. while otwórz nawias okrągły indeks minus minus zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 66. pomocniczy2 znak równości pomocniczy1 średnik. Linia 67. pomocniczy1 znak równości pomocniczy1 kropka nastepny średnik. Linia 68. zamknij nawias klamrowy. Linia 70. pomocniczy2 kropka nastepny znak równości pomocniczy1 kropka nastepny średnik. Linia 71. zamknij nawias klamrowy. Linia 73. public void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 74. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return średnik. Linia 76. System kropka out kropka print otwórz nawias okrągły cudzysłów Lista zawiera dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 77. Wezel pomocniczy znak równości glowa średnik. Linia 78. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 79. 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 80. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 81. zamknij nawias klamrowy. Linia 82. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 83. zamknij nawias klamrowy. Linia 84. zamknij nawias klamrowy. Linia 86. public class Lista1 otwórz nawias klamrowy. Linia 87. 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 88. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 89. lista kropka dodaj otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 90. lista kropka dodaj otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 91. lista kropka dodaj otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 92. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 94. lista kropka usun otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 95. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 97. lista kropka usun otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 98. lista kropka dodaj otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 99. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 100. zamknij nawias klamrowy. Linia 101. 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 boolean czyPusta() {
        if (glowa == null) {
            System.out.println("Lista jest pusta!");
        }
        return (glowa == null);
    }

    public void dodaj(int liczba) {
        System.out.println("Dodaję " + String.valueOf(liczba));
        Wezel nowy = new Wezel(liczba);

        if (czyPusta()) {
            glowa = nowy;
            return;
        }

        Wezel pomocniczy = glowa;
        while (pomocniczy.nastepny != null) {
            pomocniczy = pomocniczy.nastepny;
        }

        pomocniczy.nastepny = nowy;
    }

    public void usun(int indeks) {
        if (czyPusta()) return;

        System.out.println("Usuwam pozycję: " + Integer.toString(indeks));

        Wezel pomocniczy1 = glowa, pomocniczy2 = null;
        int rozmiar = 0;

        while (pomocniczy1 != null) {
            pomocniczy1 = pomocniczy1.nastepny;
            rozmiar++;
        }

        if (indeks > rozmiar) {
            System.out.println("Indeks poza zakresem.");
            return;
        }

        if (indeks == 1) {
            glowa = glowa.nastepny;
            return;
        }
        pomocniczy1 = glowa;
        while (indeks-- > 1) {
            pomocniczy2 = pomocniczy1;
            pomocniczy1 = pomocniczy1.nastepny;
        }

        pomocniczy2.nastepny = pomocniczy1.nastepny;
    }

    public void wypisz() {
        if (czyPusta()) return;

        System.out.print("Lista zawiera: ");
        Wezel pomocniczy = glowa;
        while (pomocniczy != null) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println();
    }
}

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

        lista.usun(2);
        lista.wypisz();

        lista.usun(2);
        lista.dodaj(4);
        lista.wypisz();
    }
}

Wynik działania programu:

Dodaję: 1
Lista jest pusta!
Dodaję: 2
Dodaję: 3
Lista zawiera: 1 2 3
Usuwam pozycję: 2
Lista zawiera: 1 3
Usuwam pozycję: 2
Dodaję: 4
Lista zawiera: 1 4

Lista dwukierunkowa

Lista dwukierunkowa od jednokierunkowej różni się tym, że jej węzły – oprócz referencji na element następny – zawierają także referencję na element poprzedni. Implementację przygotujemy, korzystając z omówionego kodu listy jednokierunkowej.

Na początku uzupełniamy klasę Wezel o pole poprzedni i uzupełniamy konstruktor tak, aby inicjalizował je wartością pustą. Do klasy Lista dodajemy pole ogon, które będzie wskazywało ostatni element listy. W konstruktorze klasy pola glowa i ogon ustawiamy na wartości puste.

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;
    }

    // Poniżej dodamy kolejne metody
}

Pole ogon, tj. referencja na ostatni element listy, jest opcjonalne – może występować zarówno w listach jedno-, jak i dwukierunkowych. Używa się go m.in. do szybkiego dodawania elementów na końcu listy bez konieczności przechodzenia po wszystkich jej elementach w celu znalezienia ostatniego.

Dodawanie węzłów na końcu listy dwukierunkowej

Metody czyPusta() oraz wypisz() pozostają bez zmian. Modyfikacji wymagają tylko implementacje metod dodaj() i usun(). Zacznijmy od metody dodającej nowe węzły:

public void dodaj(int liczba) {
    System.out.println("Dodaję " + String.valueOf(liczba));

    Wezel nowy = new Wezel(liczba);

    // jeżeli lista jest pusta
    if (czyPusta()) {
        glowa = ogon = nowy;
        return;
    }

    // dodanie nowego węzła na końcu listy
    ogon.nastepny = nowy;
    nowy.poprzedni = ogon;
    ogon = nowy;
}

Różnice w porównaniu do implementacji tej metody w przypadku listy jednokierunkowej są następujące:

ustawienia pola ogon na nowy węzeł w przypadku dodawania pierwszego elementu listy,
wykorzystanie pola ogon – zamiast pętli przechodzącej wszystkie elementy listy – do wskazania ostatniego węzła listy,
ustawienie referencji nastepny dotychczasowego ostatniego węzła na nowy oraz poprzedni nowego węzła na dotychczasowy ostatni,
ustawienie pola ogon na nowo dodany element.

RlhFi1x6RJLwH

Ilustracja przedstawia schemat dodawania węzła do końca listy dwukierunkowej. Lista składa się z czterech elementów. Pomiędzy elementami są po dwie strzałki, gdyż każdy z nich jest jednocześnie elementem następnym oraz poprzednim. Pierwszy z elementów to głowa. Trzeci element początkowo był ogonem, jednak po dodaniu węzła to nowy element czwarty jest podpisany jako ogon. — Schemat dodawania węzła do końca listy dwukierunkowej
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Usuwanie węzłów z listy dwukierunkowej

Metoda usuwająca elementy z podanej pozycji nie wymaga zmian, lecz uzupełnienia. Jeżeli usuwamy element niebędący ani pierwszym, ani ostatnim, musimy odpowiednio ustawić referencję poprzedni węzła występującego po węźle usuwanym. W przeciwnym razie, jeżeli usuwamy ostatni element, musimy zaktualizować pole ogon, aby wskazywało na dotychczasowy węzeł przedostatni. Poniżej kod uzupełnionej metody usun(). W komentarzu zaznaczyliśmy instrukcję warunkową realizującą omówione operacje:

Linia 1. public void usun otwórz nawias okrągły int indeks zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return średnik. Linia 4. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam pozycję dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły indeks zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 6. Wezel pomocniczy1 znak równości glowa przecinek pomocniczy2 znak równości null średnik. Linia 7. int rozmiar znak równości 0 średnik. Linia 9. while otwórz nawias okrągły pomocniczy1 wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. pomocniczy1 znak równości pomocniczy1 kropka nastepny średnik. Linia 11. rozmiar plus plus średnik. Linia 12. zamknij nawias klamrowy. Linia 14. if otwórz nawias okrągły indeks zamknij nawias ostrokątny rozmiar zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. System kropka out kropka println otwórz nawias okrągły cudzysłów Indeks poza zakresem kropka cudzysłów zamknij nawias okrągły średnik. Linia 16. return średnik. Linia 17. zamknij nawias klamrowy. Linia 19. if otwórz nawias okrągły indeks znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. glowa znak równości glowa kropka nastepny średnik. Linia 21. return średnik. Linia 22. zamknij nawias klamrowy. Linia 24. pomocniczy1 znak równości glowa średnik. Linia 25. while otwórz nawias okrągły indeks minus minus zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. pomocniczy2 znak równości pomocniczy1 średnik. Linia 27. pomocniczy1 znak równości pomocniczy1 kropka nastepny średnik. Linia 28. zamknij nawias klamrowy. Linia 30. pomocniczy2 kropka nastepny znak równości pomocniczy1 kropka nastepny średnik. Linia 32. prawy ukośnik prawy ukośnik Kod obsługujący listę dwukierunkową. Linia 33. if 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 34. prawy ukośnik prawy ukośnik Jeżeli usuwany węzeł nie jest ostatni. Linia 35. pomocniczy1 kropka nastepny kropka poprzedni znak równości pomocniczy2 średnik. Linia 36. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 37. prawy ukośnik prawy ukośnik Jeżeli usuwany element jest ostatni. Linia 38. ogon znak równości pomocniczy2 średnik. Linia 39. zamknij nawias klamrowy. Linia 40. zamknij nawias klamrowy.

public void usun(int indeks) {
    if (czyPusta()) return;

    System.out.println("Usuwam pozycję: " + Integer.toString(indeks));

    Wezel pomocniczy1 = glowa, pomocniczy2 = null;
    int rozmiar = 0;

    while (pomocniczy1 != null) {
        pomocniczy1 = pomocniczy1.nastepny;
        rozmiar++;
    }

    if (indeks > rozmiar) {
        System.out.println("Indeks poza zakresem.");
        return;
    }

    if (indeks == 1) {
        glowa = glowa.nastepny;
        return;
    }

    pomocniczy1 = glowa;
    while (indeks-- > 1) {
        pomocniczy2 = pomocniczy1;
        pomocniczy1 = pomocniczy1.nastepny;
    }

    pomocniczy2.nastepny = pomocniczy1.nastepny;

    // Kod obsługujący listę dwukierunkową
    if (pomocniczy1.nastepny != null) {
            // Jeżeli usuwany węzeł nie jest ostatni
        pomocniczy1.nastepny.poprzedni = pomocniczy2;
    } else {
        // Jeżeli usuwany element jest ostatni
        ogon = pomocniczy2;
    }
}

R50oTO05RitRz

Ilustracja przedstawia schemat usuwania węzła z listy dwukierunkowej. Lista składa się z czterech elementów. Pomiędzy elementami są po dwie strzałki, gdyż każdy z nich jest jednocześnie elementem następnym oraz poprzednim. Pierwszy z elementów to głowa. Element drugi to element pomocniczy dwa. Element trzeci to element pomocniczy jeden. Element czwarty to ogon. Element trzeci został przekreślony wraz ze strzałkami łączącymi go z drugim oraz czwartym elementem. Pomiędzy drugim i czwartym elementem dodane zostały nowe strzałki. — Schemat usuwania węzła z listy dwukierunkowej
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 2

Wykorzystaj omówiony kod i przygotuj program pozwalający sprawdzić działanie listy dwukierunkowej. Dodaj do listy trzy liczby i wypisz listę. Następnie usuń pierwszy, drugi i trzeci element. Dodaj do listy jeszcze jedną liczbę i wypisz listę.

RUHeK9ZkbEYI9

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel poprzedni średnik. Linia 6. Wezel otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. this kropka liczba znak równości liczba średnik. Linia 8. this kropka nastepny znak równości null średnik. Linia 9. this kropka poprzedni znak równości null średnik. Linia 10. zamknij nawias klamrowy. Linia 11. zamknij nawias klamrowy. Linia 13. class Lista otwórz nawias klamrowy. Linia 14. Wezel glowa średnik. Linia 15. Wezel ogon średnik. Linia 17. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. glowa znak równości ogon znak równości null średnik. Linia 19. zamknij nawias klamrowy. Linia 21. public boolean czyPusta otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. 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. System kropka out kropka println otwórz nawias okrągły cudzysłów Lista jest pusta wykrzyknik cudzysłów zamknij nawias okrągły średnik. Linia 24. zamknij nawias klamrowy. Linia 25. return otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły średnik. Linia 26. zamknij nawias klamrowy. Linia 28. public void dodaj otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. System kropka out kropka println otwórz nawias okrągły cudzysłów Dodaję cudzysłów plus String kropka valueOf otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 31. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 33. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. glowa znak równości ogon znak równości nowy średnik. Linia 35. return średnik. Linia 36. zamknij nawias klamrowy. Linia 38. ogon kropka nastepny znak równości nowy średnik. Linia 39. nowy kropka poprzedni znak równości ogon średnik. Linia 40. ogon znak równości nowy średnik. Linia 41. zamknij nawias klamrowy. Linia 43. public void usun otwórz nawias okrągły int indeks zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return średnik. Linia 46. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam pozycję dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły indeks zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 48. Wezel pomocniczy1 znak równości glowa przecinek pomocniczy2 znak równości null średnik. Linia 49. int rozmiar znak równości 0 średnik. Linia 51. while otwórz nawias okrągły pomocniczy1 wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 52. pomocniczy1 znak równości pomocniczy1 kropka nastepny średnik. Linia 53. rozmiar plus plus średnik. Linia 54. zamknij nawias klamrowy. Linia 56. if otwórz nawias okrągły indeks zamknij nawias ostrokątny rozmiar zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. System kropka out kropka println otwórz nawias okrągły cudzysłów Indeks poza zakresem kropka cudzysłów zamknij nawias okrągły średnik. Linia 58. return średnik. Linia 59. zamknij nawias klamrowy. Linia 61. if otwórz nawias okrągły indeks znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 62. glowa znak równości glowa kropka nastepny średnik. Linia 63. return średnik. Linia 64. zamknij nawias klamrowy. Linia 66. pomocniczy1 znak równości glowa średnik. Linia 67. while otwórz nawias okrągły indeks minus minus zamknij nawias ostrokątny 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 68. pomocniczy2 znak równości pomocniczy1 średnik. Linia 69. pomocniczy1 znak równości pomocniczy1 kropka nastepny średnik. Linia 70. zamknij nawias klamrowy. Linia 72. pomocniczy2 kropka nastepny znak równości pomocniczy1 kropka nastepny średnik. Linia 74. prawy ukośnik prawy ukośnik Kod obsługujący listę dwukierunkową. Linia 75. if 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 76. prawy ukośnik prawy ukośnik Jeżeli usuwany węzeł nie jest ostatni. Linia 77. pomocniczy1 kropka nastepny kropka poprzedni znak równości pomocniczy2 średnik. Linia 78. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 79. prawy ukośnik prawy ukośnik Jeżeli usuwany element jest ostatni. Linia 80. ogon znak równości pomocniczy2 średnik. Linia 81. zamknij nawias klamrowy. Linia 82. zamknij nawias klamrowy. Linia 84. public void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 85. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return średnik. Linia 87. System kropka out kropka print otwórz nawias okrągły cudzysłów Lista zawiera dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 88. Wezel pomocniczy znak równości glowa średnik. Linia 89. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 90. 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 91. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 92. zamknij nawias klamrowy. Linia 93. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 94. zamknij nawias klamrowy. Linia 95. zamknij nawias klamrowy. Linia 97. public class Lista2 otwórz nawias klamrowy. Linia 98. 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 99. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 100. lista kropka dodaj otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 101. lista kropka dodaj otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 102. lista kropka dodaj otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 103. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 105. lista kropka usun otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 106. lista kropka usun otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 107. lista kropka usun otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 108. lista kropka dodaj otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 109. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 110. zamknij nawias klamrowy. Linia 111. 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;
    Wezel ogon;

    public Lista() {
        glowa = ogon = null;
    }

    public boolean czyPusta() {
        if (glowa == null) {
            System.out.println("Lista jest pusta!");
        }
        return (glowa == null);
    }

    public void dodaj(int liczba) {
        System.out.println("Dodaję " + String.valueOf(liczba));

        Wezel nowy = new Wezel(liczba);

        if (czyPusta()) {
            glowa = ogon = nowy;
            return;
        }

        ogon.nastepny = nowy;
        nowy.poprzedni = ogon;
        ogon = nowy;
    }

    public void usun(int indeks) {
        if (czyPusta()) return;

        System.out.println("Usuwam pozycję: " + Integer.toString(indeks));

        Wezel pomocniczy1 = glowa, pomocniczy2 = null;
        int rozmiar = 0;

        while (pomocniczy1 != null) {
            pomocniczy1 = pomocniczy1.nastepny;
            rozmiar++;
        }

        if (indeks > rozmiar) {
            System.out.println("Indeks poza zakresem.");
            return;
        }

        if (indeks == 1) {
            glowa = glowa.nastepny;
            return;
        }

        pomocniczy1 = glowa;
        while (indeks-- > 1) {
            pomocniczy2 = pomocniczy1;
            pomocniczy1 = pomocniczy1.nastepny;
        }

        pomocniczy2.nastepny = pomocniczy1.nastepny;

        // Kod obsługujący listę dwukierunkową
        if (pomocniczy1.nastepny != null) {
            // Jeżeli usuwany węzeł nie jest ostatni
            pomocniczy1.nastepny.poprzedni = pomocniczy2;
        } else {
            // Jeżeli usuwany element jest ostatni
            ogon = pomocniczy2;
        }
    }

    public void wypisz() {
        if (czyPusta()) return;

        System.out.print("Lista zawiera: ");
        Wezel pomocniczy = glowa;
        while (pomocniczy != null) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println();
    }
}

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

        lista.usun(1);
        lista.usun(3);
        lista.usun(2);
        lista.dodaj(4);
        lista.wypisz();
    }
}