Algoritmai ir duomenų struktūros

Sąrašas

Sąrašas (angl. List) yra struktūrinis duomenų tipas, skirtas laikyti duomenų rinkinius su kintamu elementų skaičiumi, kurie išlaiko įterpimo tvarką. Sąrašo elementai gali būti pasiekiami pagal jų indeksus, todėl tai yra lanksti ir galinga struktūra, naudojama tvarkyti duomenų rinkinius, kai svarbi jų tvarka arba kai reikia atlikti daug įterpimo, šalinimo ar rūšiavimo operacijų.

Java kalboje sąrašas realizuojamas kaip List sąsaja, kuri yra Java kolekcijų karkaso (angl. Java Collections Framework) dalis. List sąsaja apibrėžia metodus, reikalingus sąrašo valdymui, įskaitant elementų įterpimą, šalinimą, prieigą ir paiešką. Populiariausi sąrašo įgyvendinimai Java kalboje yra ArrayList, LinkedList ir Vector.

1. Pagrindinės `List` sąsajos savybės

Java kalboje List sąsaja turi kelias svarbias savybes:

Indeksuota prieiga: Sąrašo elementai pasiekiami naudojant indeksus, pradedant nuo 0.
Elementų tvarka: Sąraše elementai yra saugomi tokia tvarka, kokia jie buvo pridėti, todėl sąrašas išlaiko nuoseklią elementų tvarką.
Dublikatai: Sąrašas leidžia saugoti pasikartojančias reikšmes.
Kintamas dydis: Skirtingai nei masyvas, sąrašas gali augti arba mažėti priklausomai nuo pridedamų ar šalinamų elementų.

2. `List` sąsajos pagrindiniai metodai

List sąsaja apibrėžia metodus, kurie leidžia atlikti visas pagrindines operacijas su sąrašo struktūra. Štai keletas svarbiausių:

add(E element): Prideda elementą į sąrašo pabaigą.
add(int index, E element): Prideda elementą į nurodytą poziciją sąraše.
get(int index): Grąžina elementą pagal nurodytą indeksą.

set(int index, E element)

remove(int index): Pašalina elementą iš nurodytos pozicijos.
remove(Object o): Pašalina pirmą rastą nurodytą elementą sąraše.
size(): Grąžina sąrašo elementų skaičių.
contains(Object o): Patikrina, ar sąrašas turi tam tikrą elementą.
indexOf(Object o): Grąžina pirmojo rasto elemento indeksą.
lastIndexOf(Object o): Grąžina paskutinio rasto elemento indeksą.
subList(int fromIndex, int toIndex): Grąžina dalinį sąrašą, pradedant nuo fromIndex iki toIndex.

3. Sąrašo įgyvendinimai Java kalboje

Java kalboje dažniausiai naudojami sąrašo įgyvendinimai yra ArrayList, LinkedList ir Vector. Kiekvienas jų turi skirtingas savybes ir pritaikymą:

a) `ArrayList`

ArrayList yra populiariausias List sąsajos įgyvendinimas Java kalboje. Jis pagrįstas dinaminio dydžio masyvu, kuris automatiškai padidėja, kai trūksta vietos naujiems elementams.

Privalumai: Greita prieiga prie elementų pagal indeksą (O(1) laiko sudėtingumas).
Trūkumai: Lėtesnis elementų įterpimas arba šalinimas iš pradžios arba vidurio (O(n) laiko sudėtingumas), nes reikia perkelti elementus.

Pavyzdys:

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        System.out.println("Elementas pozicijoje 1: " + list.get(1));  // Grąžina "Banana"
        list.remove(2);  // Pašalina "Cherry"

        System.out.println("Sąrašas: " + list);  // Išspausdina ["Apple", "Banana"]
    }
}

b) `LinkedList`

LinkedList yra sąrašo įgyvendinimas, pagrįstas dvipusiu sąrašu su ryšiais. Tai reiškia, kad kiekvienas elementas turi nuorodą į prieš jį ir po jo esančius elementus.

Privalumai: Greitas elementų įterpimas ir šalinimas iš pradžios ir pabaigos (O(1) laiko sudėtingumas).
Trūkumai: Lėtesnė prieiga prie elementų pagal indeksą (O(n) laiko sudėtingumas), nes reikia pereiti per sąrašo elementus.

Pavyzdys:

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();

        list.add("Dog");
        list.add("Cat");
        list.add("Bird");

        list.add(1, "Rabbit";  // Prideda "Rabbit" į 1-ąją poziciją
        list.remove("Cat");  // Pašalina "Cat"

        System.out.println("Sąrašas: " + list);  // Išspausdina ["Dog", "Rabbit", "Bird"]
    }
}

c) `Vector`

Vector yra senesnis List įgyvendinimas, kuris, skirtingai nei ArrayList, yra sinchronizuotas. Tai reiškia, kad Vector yra saugus naudoti kelių gijų aplinkoje, tačiau dėl šios savybės jis yra lėtesnis nei ArrayList.

Privalumai: Sinchronizuotas, todėl saugus kelių gijų aplinkoje.
Trūkumai: Lėtesnis už ArrayList vienagijėje (single-threaded) aplinkoje.

4. Sąrašo panaudojimo atvejai

Sąrašai yra naudingi įvairiose situacijose, kai reikia valdyti duomenų rinkinius, išlaikyti jų tvarką ir turėti kintamą dydį. Štai keletas sąrašų naudojimo atvejų:

Dinamiškai augantys duomenų rinkiniai: Kai reikalingas sąrašas, kuris gali kisti, pridėti naujus elementus ar pašalinti senus, sąrašas yra ideali struktūra, nes jo dydis gali būti keičiamas be apribojimų.
Paieška pagal indeksą: ArrayList yra puikus pasirinkimas, kai reikia dažnai prieiti prie elementų pagal indeksą, nes ji užtikrina greitą prieigą.
Elementų įterpimas ir šalinimas: Jei reikia dažnai įterpti arba šalinti elementus sąrašo pradžioje ar viduryje, geriausias pasirinkimas yra LinkedList, nes ši operacija yra greitesnė nei masyvo pagrindu veikiančiame ArrayList.

5. Sąrašo privalumai ir trūkumai Java kalboje

Privalumai:

Dydžio lankstumas: Sąrašas gali augti ir mažėti priklausomai nuo duomenų kiekio.
Indeksuota prieiga: Sąrašas leidžia greitai pasiekti elementus pagal jų poziciją, todėl yra patogus navigacijai.
Įterpimo ir pašalinimo lankstumas: Sąrašas, ypač LinkedList, leidžia lengvai įterpti arba pašalinti elementus iš bet kurios vietos sąraše.

Trūkumai:

Atminties sunaudojimas: LinkedList sunaudoja daugiau atminties dėl kiekvieno elemento nuorodų į kitus elementus.
Prieigos laikas: Prieiga prie elementų LinkedList yra lėtesnė, nes kiekvienas elementas pasiekiamas einant per nuorodas.
Sinchronizacijos trūkumas: ArrayList ir LinkedList nėra sinchronizuoti, todėl jie nėra tinkami tiesioginiam naudojimui kelių gijų aplinkoje. Jei reikia sinchronizuoto sąrašo, galima naudoti Vector arba papildomai sinchronizuoti ArrayList naudojant Collections.synchronizedList() metodą.

6. Kodas su pagrindinių `List` metodų pavyzdžiais

Štai pavyzdys, kaip naudoti pagrindinius sąrašo metodus Java kalboje:

import java.util.ArrayList;
import java.util.List;

public class ListExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        // Pridėti elementus
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // Gauti elementą pagal indeksą
        System.out.println("Elementas pozicijoje 1: " + list.get(1));  // Grąžina "Banana"

        // Keisti elemento reikšmę
        list.set(1, "Blueberry");
        System.out.println("Naujas sąrašas: " + list);  // ["Apple", "Blueberry", "Cherry"]

        // Pašalinti elementą pagal reikšmę
        list.remove("Apple");

        // Patikrinti, ar sąrašas turi tam tikrą elementą
        boolean hasCherry = list.contains("Cherry");
        System.out.println("Ar sąrašas turi 'Cherry'? " + hasCherry);  // true

        // Sąrašo dydis
        System.out.println("Sąrašo dydis: " + list.size());  // 2
    }
}

Algoritmai ir duomenų struktūros

Sąrašas

1. Pagrindinės List sąsajos savybės

2. List sąsajos pagrindiniai metodai