Klasa LinkedList - I_R_W13A_M03_JAVA Zaawansowane struktury danych

R1KSK8bTfIKoK

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.

Przykład 1

Przykładowy program:

Linia 1. import java kropka util kropka LinkedList średnik. Linia 3. public class ListaJF otwórz nawias klamrowy. Linia 4. 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 5. LinkedList otwórz nawias ostrokątny Integer zamknij nawias ostrokątny lista znak równości new LinkedList otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 6. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny System kropka out kropka println otwórz nawias okrągły cudzysłów Dodaję liczby 5 przecinek 4 na końcu cudzysłów zamknij nawias okrągły średnik. Linia 7. lista kropka add otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 8. lista kropka addLast otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 9. System kropka out kropka println otwórz nawias okrągły cudzysłów Dodaję liczbę 6 na początku cudzysłów zamknij nawias okrągły średnik. Linia 10. lista kropka addFirst otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 11. System kropka out kropka print otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły lista kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 12. System kropka out kropka print otwórz nawias okrągły cudzysłów Pierwszy dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły lista kropka peekFirst otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 13. System kropka out kropka println otwórz nawias okrągły cudzysłów Ostatni dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły lista kropka peekLast otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 15. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam ostatni kropka cudzysłów zamknij nawias okrągły średnik. Linia 16. lista kropka removeLast otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 17. System kropka out kropka print otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły lista kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 18. System kropka out kropka print otwórz nawias okrągły cudzysłów Pierwszy dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły lista kropka peekFirst otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 19. System kropka out kropka println otwórz nawias okrągły cudzysłów Ostatni dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły lista kropka peekLast otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 21. 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 22. while otwórz nawias okrągły wykrzyknik lista kropka isEmpty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. System kropka out kropka print otwórz nawias okrągły lista kropka peek otwórz nawias okrągły zamknij nawias okrągły plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 24. lista kropka remove otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 25. zamknij nawias klamrowy. Linia 26. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 28. System kropka out kropka println otwórz nawias okrągły cudzysłów Rozmiar dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły lista kropka size otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 29. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 31. zamknij nawias klamrowy.

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

}

Na początku tworzy obiekt lista, który posłuży do przechowywania wartości typu int (liczby całkowite). Następnie dodajemy na końcu listy dwie liczby (add(), addLast()), następnie jedną na początku (addFirst()), po czym wypisujemy rozmiar (size()) oraz pierwszy (peekFirst()) i ostatni (peekLast()) element.

Następnie usuwamy ostatni element (removeLast()) oraz wypisujemy rozmiar, pierwszy i ostatni element listy.

Na końcu przy użyciu pętli wykonującej się, dopóki lista nie jest pusta (isEmpty()), wypisujemy kolejne pierwsze elementy (peek()) i usuwamy je (remove()). Na końcu wypisujemy jeszcze raz aktualny rozmiar listy.

Wynik działania programu:

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

Java Collections Framework

zestaw interfejsów i klas, które implementują najczęściej używane struktury danych, czyli kolekcje, np. stos, kolejka, lista; mimo określenia framework omawiany zestaw traktować można jak bibliotekę zawierającą gotowe do użycia implementacje

klasa

definiowany przez użytkownika złożony typ danych, który pozwala grupować logicznie powiazane dane oraz funkcje wykonujące na nich operacje; składowe klasy nazywamy polami, funkcje zdefiniowane w klasie nazywa się metodami

konstruktor

metoda o takie samej nazwie jak klasa, która służy do nadawania wartości początkowych jej polom; w języku Java klasa może mieć wiele konstruktorów dzięki mechanizmowi przeciążania

niedopełnienie stosu

(ang. stack underflow) – rodzaj błędu występującego kiedy program próbuje zdjąć wartość z pustego stosu.

przepełnienie stosu

(ang. stack overflow) – rodzaj błędu polegającego na przekroczeniu rozmiaru pamięci zarezerwowanej dla stosu.

referencja

zmienna zawierająca informacje o położeniu jakiejś wartości (obiektu) w pamięci; referencje zarządzane są przez kompilator lub interpreter, a nie przez programistę, dzięki czemu są bezpieczniejsze niż wskaźniki; referencje mogą być puste, co znaczy, że nie wskazują na żaden obiekt, w języku Java wyraża to wartość null, w języku Python None

wskaźnik

zmienna przechowująca adres innej zmiennej lub obiektu, pozwalająca na bezpośredni dostęp do pamięci; możliwe jest tworzenie wskaźników pustych, które na nic nie wskazują

Implamentacja: Stos, kolejka i lista w Java Collections Framework

Misja: Porównujemy stos i stertę

Klasa `LinkedList`

Słownik