Najprostszymi dynamicznymi strukturami, które poznaliśmy, są stos i kolejka. Obydwie implementować można za pomocą różnych mechanizmów. Jedno z najprostszych rozwiązań, które służy zazwyczaj do wyjaśnienia działania tych struktur, to użycie statycznej lub dynamicznej tablicy. Jednak nie jest to rozwiązanie w pełni dynamiczne, ponieważ użycie tablic wymaga podania maksymalnej liczby przechowywanych w strukturze elementów. Aby uzyskać w pełni dynamiczne struktury stosu i kolejki, wykorzystuje się listy.

Stos

Przypomnijmy, że stos to liniowa struktura typu LIFO (ang. Last‑In, First‑Out – ostatni na wejściu, pierwszy na wyjściu), która obsługuje dwie podstawowe operacje, tj. odkładanie i zdejmowanie danych. Dodatkowe działania, które wykonuje się na stosie, to odczytywanie wierzchołka stosu, czyli ostatniego odłożonego elementu, bez usuwania go, oraz ewentualnie sprawdzanie rozmiaru stosu, czyli liczby odłożonych elementów.

Biorąc podane warunki pod uwagę, do implementacji stosu wystarczy jednokierunkowa lista niecykliczna. Elementami tej listy będą węzły zawierające dane, np. liczby, oraz – w przypadku listy jednokierunkowej – referencjareferencjareferencja na element następny. Do zdefiniowania węzła użyjemy klasyklasaklasy zawierającej dwa pola oraz konstruktorkonstruktorkonstruktor:

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

Stworzenie nowego węzła i przypisanie wartości do jego składowych umożliwia instrukcja:

Wezel nowy = new Wezel(liczba);

Stos zaimplementujemy również jako klasę, której atrybutem będzie referencja na wierzchołek stosu o nazwie wierzcholek. Klasa będzie zawierała również definicję konstruktora.

class Stos {
    Wezel wierzcholek;

    public Stos() {
        wierzcholek = null;
    }

    // Miejsce na dodanie metod
}

W konstruktorze Stos() inicjalizujemy pole wierzcholek referencją pustąreferencjareferencją pustą.

Do klasy Stos() dodamy teraz metody wykonujące charakterystyczne dla stosu operacje.

Zaczniemy od metody czyPusty(), która będzie zwracała wartość true (prawda), jeżeli stos będzie pusty, czyli w sytuacji, kiedy pole wierzcholek będzie referencją pustą. W przeciwnym razie metoda zwróci wartość false (fałsz).

public boolean czyPusty() {
    if (wierzcholek == null) {
        System.out.println("Stos pusty!");
    }
    return (wierzcholek == null);
}

W celu zachowania poprawności działania struktury LIFO, funkcja odloz() będzie dodawała elementy na początku listy i odpowiednio funkcja zdjemij() będzie usuwała elementy również z początku listy.

Zacznijmy od metody odloz():

public void odloz(int liczba) {
    System.out.println("Odkładam " + String.valueOf(liczba));
    
    Wezel nowy = new Wezel(liczba);
    nowy.nastepny = wierzcholek;
    wierzcholek = nowy;
}

W funkcji odloz() tworzymy nowy węzeł i zapisujemy w nim wartość zmiennej liczba przekazaną jako argument. Następnie pole nastepny nowego elementu ustawiamy na dotychczasowy wierzcholek, w ten sposób dodajemy element na początku listy. Na koniec aktualizujemy pole wierzcholek, tak aby wskazywało na nowo dodany element.

Usuwanie pierwszego elementu jest możliwe dzięki referencji wierzcholek:

public int zdejmij() {
    if (czyPusty()) return Integer.MIN_VALUE;
    Wezel pomocniczy = wierzcholek;
    int liczba = pomocniczy.liczba;
    wierzcholek = wierzcholek.nastepny;
    
    System.out.println("Zdejmuję " + Integer.toString(liczba));
    
    return liczba;
}

Jeżeli stos jest pusty, tzn. zachodzi błąd niedopełnienia stosuniedopełnienie stosuniedopełnienia stosu, zwracamy minimalną wartość zdefiniowaną dla typu całkowitego w stałej MIN_VALUE.

W przeciwnym razie dotychczasowy pierwszy element oraz zapisaną w nim wartość zapamiętujemy w zmiennych pomocniczych. Następnie ustawiamy wierzchołek na drugi element listy, dotychczasowy pierwszy usuwamy, a zapamiętaną wartość zwracamy.

Metoda pobierzWierzcholek() ma tylko jedno zadanie: jeżeli stos nie jest pusty, zwraca wartość zapisaną w pierwszym, czyli ostatnim dodanym, elemencie listy:

public int pobierzWierzcholek() {
    if (czyPusty()) return Integer.MIN_VALUE;
    return wierzcholek.liczba;
}

Metoda wypisz() posłuży do wypisania wartości odłożonych na stosie, czyli zapisanych w kolejnych węzłach listy:

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

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

Do wypisania wartości używamy pętli przechodzącej po wszystkich elementach stosu zapisywanych w zmiennej pomocniczy, którą ustawiamy na wierzchołek, a następnie wewnątrz pętli przesuwamy na kolejne węzły wskazywane przez pole nastepny. Pętla będzie działać dopóki nie dojdziemy do ostatniego węzła, którego referencja nastepny będzie pusta.

Do sprawdzenia działania stosu możemy użyć poniższego kodu:

public class StosLista {
    public static void main(String[] args) {
        Stos stos = new Stos();
        stos.odloz(1);
        stos.odloz(2);
        stos.odloz(3);
        stos.wypisz();
        stos.zdejmij();
        stos.zdejmij();
        stos.zdejmij();
        stos.zdejmij();
    }
}

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

class Stos {
    Wezel wierzcholek;

    public Stos() {
        wierzcholek = null;
    }

    public boolean czyPusty() {
        if (wierzcholek == null) {
            System.out.println("Stos pusty!");
        }
        return (wierzcholek == null);
    }
    
    public void odloz(int liczba) {
        System.out.println("Odkładam " + String.valueOf(liczba));
        
        Wezel nowy = new Wezel(liczba);
        nowy.nastepny = wierzcholek;
        wierzcholek = nowy;
    }
    public int zdejmij() {
        if (czyPusty()) return Integer.MIN_VALUE;
        Wezel pomocniczy = wierzcholek;
        int liczba = pomocniczy.liczba;
        wierzcholek = wierzcholek.nastepny;
        
        System.out.println("Zdejmuję " + Integer.toString(liczba));
        
        return liczba;
    }  
    
    public int pobierzWierzcholek() {
        if (czyPusty()) return Integer.MIN_VALUE;
        return wierzcholek.liczba;
    }
    
    public void wypisz() {
        if (czyPusty()) return;
    
        System.out.print("Stos zawiera: ");
        Wezel pomocniczy = wierzcholek;
        while (pomocniczy != null) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println();
    }
    
}

public class StosLista {
    public static void main(String[] args) {
        Stos stos = new Stos();
        stos.odloz(1);
        stos.odloz(2);
        stos.odloz(3);
        stos.wypisz();
        stos.zdejmij();
        stos.zdejmij();
        stos.zdejmij();
        stos.zdejmij();
    }
}

Odkładam 1
Odkładam 2
Odkładam 3
Stos zawiera: 3 2 1 
Zdejmuję 3
Zdejmuję 2
Zdejmuję 1
Stos pusty!

Kolejka

Kolejka to liniowa struktura danych typu FIFO (ang. First‑In, First‑Out – pierwszy na wejściu, pierwszy na wyjściu), co oznacza, że jej elementy odczytywane są zgodnie z kolejnością dodawania, a zatem odwrotnie niż w przypadku stosu.

W implementacji kolejki również użyjemy listy jednokierunkowej oraz takiej samej jak w przypadku stosu definicji klasy Wezel. Natomiast klasa Kolejka będzie zawierała dwa pola:

• glowa – referencję na pierwszy element kolejki;

• ogon – referencję na ostatni element kolejki, który ułatwi dodawanie elementów na końcu listy.

Nazwy pozostałych metod dostosujemy do omawianej struktury.

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

class Kolejka {
    Wezel glowa;
    Wezel ogon;

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

    // Miejsce na metody
}

Metoda czyPusta() działa tak samo, jak w przypadku stosu i każdej listy, tzn. jeżeli referencja na pierwszy element jest pusta, lista jest pusta.

public boolean czyPusta() {
	return (glowa == null);
}

Metoda dodaj() będzie dodawała nowe elementy na końcu listy przy użyciu pola ogon.

public void dodaj(int liczba) {
    Wezel nowy = new Wezel(liczba);
    nowy.nastepny = null;

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

    ogon.nastepny = nowy;
    ogon = nowy;
}

Na początku metody tworzymy nowy węzeł, przypisujemy otrzymaną liczbę do jego pola liczba, a referencję nastepny ustawiamy na wartość pustą. Następnie, jeżeli lista jest pusta, referencje na pierwszy (glowa) i ostatni (ogon) element listy ustawiamy na nowy węzeł.

W przeciwnym razie referencję nastepny dotychczasowego ostatniego elementu ustawiamy na nowy węzeł i aktualizujemy referencję ogon, aby wskazywał nowo dodany element.

Metoda usun() będzie zwracała kolejne elementy z początku listy, czyli działać będzie tak samo, jak metoda zdejmij() w przypadku stosu. Ponieważ jednak elementy będą dodawane na końcu listy, zasada działania kolejki FIFO zostanie zachowana.

public int usun() {
    if (czyPusta()) return Integer.MIN_VALUE;
    Wezel pomocniczy = glowa;
    int liczba = pomocniczy.liczba;
    glowa = glowa.nastepny;
    
    System.out.println("Usuwam: " + Integer.toString(liczba));
    
    return liczba;
}

class Wezel {
    int liczba;
    Wezel nastepny;

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

class Kolejka {
    Wezel glowa;
    Wezel ogon;

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

    public boolean czyPusta() {
        return (glowa == null);
    }

    public void dodaj(int liczba) {
        System.out.println("Dodaje: " + String.valueOf(liczba));
        Wezel nowy = new Wezel(liczba);
        nowy.nastepny = null;

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

        ogon.nastepny = nowy;
        ogon = nowy;
    }

    public int usun() {
        if (czyPusta()) {
            System.out.println("Kolejka jest pusta!");
            return Integer.MIN_VALUE;
        }
        Wezel pomocniczy = glowa;
        int liczba = pomocniczy.liczba;
        glowa = glowa.nastepny;
        System.out.println("Usuwam: " + Integer.toString(liczba));
        return liczba;
    }

    public void wypisz() {
        if (czyPusta()) {
            System.out.println("Kolejka jest pusta!");
            return;
        }

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

public class KolejkaLista {
    public static void main(String[] args) {
        Kolejka kolejka = new Kolejka();
        kolejka.dodaj(1);
        kolejka.dodaj(2);
        kolejka.dodaj(3);
        kolejka.wypisz();
        kolejka.usun();
        kolejka.usun();
        kolejka.usun();
        kolejka.usun();
    }
}

Dodaje: 1
Dodaje: 2
Dodaje: 3
Kolejka zawiera: 1 2 3 
Usuwam: 1
Usuwam: 2
Usuwam: 3
Kolejka jest pusta!

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ęreferencjareferencję 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 klasyklasaklasy 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ęklasaklasę 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ąreferencjareferencją 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.

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.

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).

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.

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

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
}

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.

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:

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.

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

Dodaję: 1
Lista jest pusta!
Dodaję: 2
Dodaję: 3
Lista zawiera: 1 2 3
Usuwam pozycję: 1
Usuwam pozycję: 3
Indeks poza zakresem.
Usuwam pozycję: 2
Dodaję: 4
Lista zawiera: 2 4

Stos, kolejka i lista w Java Collections Framework

Interfejs Deque i klasa ArrayDeque

Java Collections Framework definiuje klasę Stack będącą implementacją struktury stosu. Jednak ze względu na jej ograniczenia, m.in. dziedziczenie z niewspieranej już klasy Vector, zaleca się używanie interfejsu Deque i wybranej jego implementacji. Nazwa interfejsu Deque jest skrótem od wyrażenia double ended queue, które oznacza kolejkę dwukierunkową. Jedną z implementacji tego interfejsu jest klasa ArrayDeque, wykorzystująca dynamiczne tablice. Klasa ta implementuje m.in. następujące metody interfejsu:

• push() – zadaniem metody jest umieszczenie elementu na stosie;

• pop() – metoda usuwa pierwszy element kolejki;

• getFirst() – metoda zwraca bez usuwania pierwszy element kolekcji;

• peek() – zadaniem metody jest pobranie wierzchołka stosu;

• isEmpty() – metoda sprawdza, czy stos jest pusty;

• size() – zadaniem metody jest zwrócenie liczby elementów na stosie.

import java.util.Deque;
import java.util.ArrayDeque;

public class StosJF {
    public static void main(String[] args) {
        Deque<Integer> stos = new ArrayDeque<>();

        System.out.println("Odkładam liczby 5, 4, 6");
        stos.push(5);
        stos.push(4);
        stos.push(6);
        System.out.print("Rozmiar: " + Integer.toString(stos.size()));
        System.out.println(" Wierzchołek: " + Integer.toString(stos.getFirst()));

        System.out.println("Zdejmuję wierzchołek: " + stos.pop());
        System.out.print("Rozmiar: " + Integer.toString(stos.size()));
        System.out.println(" Wierzchołek: " + Integer.toString(stos.getFirst()));

        System.out.print("Stos zawiera: ");
        while (!stos.isEmpty()) {
            System.out.print(stos.peek() + " ");
            stos.pop();
        }
        System.out.println();

        System.out.println("Rozmiar: " + Integer.toString(stos.size()));
    }
}

Odkładam liczby 5, 4, 6
Rozmiar: 3 Wierzchołek: 6
Zdejmuję wierzchołek.
Rozmiar: 2 Wierzchołek: 4
Stos zawiera: 4 5
Rozmiar: 0

Interfejs Queue i klasa LinkedList

Interfejs Queue definiuje metody dla typowych kolejek typu FIFO, kolejek priorytetowych oraz kolekcji typu LIFO (typu stos). Jedną z implementacji interfejsu dostarcza klasa LinkedList. Do dyspozycji mamy m.in. następujące metody:

• add() – zadaniem metody jest dodawanie elementu na końcu listy;

• remove() – metoda usuwa pierwszy element listy;

• peek() – metoda zwraca pierwszy element listy bez usuwania go;

• size() – zadaniem metody jest zwrócenie liczby elementów listy.

import java.util.Queue;
import java.util.LinkedList;

public class KolejkaJF {
    public static void main(String[] args) {
        Queue<Integer> kolejka = new LinkedList<>();

        System.out.println("Dodaję liczby 5, 4, 6");
        kolejka.add(5);
        kolejka.add(4);
        kolejka.add(6);
        System.out.print("Rozmiar: " + Integer.toString(kolejka.size()));
        System.out.println(" Pierwszy: " + Integer.toString(kolejka.peek()));

        System.out.println("Usuwam pierwszy.");
        kolejka.remove();
        System.out.print("Rozmiar: " + Integer.toString(kolejka.size()));
        System.out.println(" Pierwszy: " + Integer.toString(kolejka.peek()));

        System.out.print("kolejka zawiera: ");
        while (kolejka.size() > 0) {
            System.out.print(kolejka.peek() + " ");
            kolejka.remove();
        }
        System.out.println();

        System.out.println("Rozmiar: " + Integer.toString(kolejka.size()));
    }
}

Dodaję liczby 5, 4, 6
Rozmiar: 3 Pierwszy: 5
Usuwam pierwszy.
Rozmiar: 2 Pierwszy: 4
kolejka zawiera: 4 6
Rozmiar: 0

Klasa LinkedList

Klasa LinkedList implementuje interfejsy Queue, Deque oraz List za pomocą listy dwukierunkowej, której elementami są węzły. Klasa udostępnia wszystkie opcjonalne metody wspomnianych interfejsów, m.in.:

• add() – zadaniem metody jest dodawanie elementu na końcu listy;

• remove() – metoda usuwa pierwszy element listy;

• peek() – metoda zwraca pierwszy element bez usuwania go;

• addLast() – zadaniem metody jest dodawanie elementu na końcu listy;

• addFirst() – metoda odpowiada za dodawanie elementu na początku listy;

• removeLast() – metoda usuwa ostatni element listy;

• removeFirst() – zadaniem metody jest usuwanie pierwszego elementu listy;

• peekLast() – metoda zwraca ostatni elementu listy bez usuwania go;

• peekFirst() – działanie metody polega na zwracaniu pierwszego elementu listy bez usuwania go;

• get(index) – metoda zwraca węzeł o podanym indeksie bez usuwania go;

• isEmpty() – metoda podaje informację, czy lista jest pusta;

• size() – metoda odpowiada za podanie rozmiaru listy.

import java.util.LinkedList;

public class ListaJF {
    public static void main(String[] args) {
        LinkedList<Integer> lista = new LinkedList<>();

        System.out.println("Dodaję liczby 5, 4 na końcu");
        lista.add(5);
        lista.addLast(4);
        System.out.println("Dodaję liczbę 6 na początku");
        lista.addFirst(6);
        System.out.print("Rozmiar: " + Integer.toString(lista.size()));
        System.out.print(" Pierwszy: " + Integer.toString(lista.peekFirst()));
        System.out.println(" Ostatni: " + Integer.toString(lista.peekLast()));

        System.out.println("Usuwam ostatni.");
        lista.removeLast();
        System.out.print("Rozmiar: " + Integer.toString(lista.size()));
        System.out.print(" Pierwszy: " + Integer.toString(lista.peekFirst()));
        System.out.println(" Ostatni: " + Integer.toString(lista.peekLast()));

        System.out.print("Lista zawiera: ");
        while (!lista.isEmpty()) {
            System.out.print(lista.peek() + " ");
            lista.remove();
        }
        System.out.println();

        System.out.println("Rozmiar: " + Integer.toString(lista.size()));
    }
}

Dodaję liczby 5, 4 na końcu
Dodaję liczbę 6 na początku
Rozmiar: 3 Pierwszy: 6 Ostatni: 4
Usuwam ostatni.
Rozmiar: 2 Pierwszy: 6 Ostatni: 5
Lista zawiera: 6 5
Rozmiar: 0

Słownik