List w Java

Java Collection Framework zawiera przydatne interfejsy i klasy, które je implementują, do pracy ze strukturami danych. Można powiedzieć, że jest to jeden z najważniejszych frameworków JDK. Interfejs List jest bardzo popularny, ponieważ wszelkiego rodzaju listy są w programowaniu niezbędne. W tym artykule omówimy interfejs, metody Java List i implementacje.

Interfejs Java List

Najważniejszą cechą listy jest to, że jest to uporządkowana kolekcja. Można nazwać ją również sekwencją. W Javie listy są jednorodne, to znaczy, że elementy listy mają ten sam typ danych. Interfejs Java List dziedziczy po interfejsie Collection, dziedziczy wszystkie jego operacje. Oprócz nich List udostępnia również następujące operacje:

• Dostęp do pozycji. Każdy element ma indeks i można nim manipulować na podstawie jego pozycji na liście. Oznacza to, że możesz dodawać, wykluczać i modyfikować elementy.
• Wyszukiwanie. Możesz odszukać element listy na podstawie jego zawartości i zwrócić jego indeks.
• Iteracja. Sekwencyjny charakter List pozwala na użycie metod iteracyjnych (listIterator).
• Widok zakresu. Metoda sublist wykonuje dowolne operacje na wybranym zakresie listy.

Metody Java List

Powyższe operacje są dostępne poprzez metody interfejsu Java List. Oto niektóre z nich:

Implementacja List

Ponieważ List jest interfejsem, programy muszą stworzyć jego konkretną implementację. Możesz wybrać jedną z następujących implementacji List w Java Collections API:

• java.util.ArrayList
• java.util.LinkedList
• java.util.Vector
• java.util.Stack

Najbardziej popularna implementacja interfejsu List to ArrayList. Znacznie rzadziej używana, ale nadal spotykana w prawdziwych zastosowaniach jest LinkedList, natomiast Vector i Stack już dawno stały się moralnie przestarzałe, więc najprawdopodobniej znajdziesz je tylko w projektach ze starożytnym kodem.

Deklaracja interfejsu List

List w programie Java można zadeklarować na jeden z następujących sposobów:

List<String> myList = new ArrayList();
List myList1 = new ArrayList();
List myList3 = new ArrayList<String>();
ArrayList arrayList = new ArrayList();

Nową listę najlepiej zadeklarować za pomocą interfejsu. Podobnie możesz zadeklarować inne implementacje List. Najkrótszy sposób to:

Vector myVector = new Vector;
LinkedList linkedList = new LinkedList();
Stack stack = new Stack();

Przy takiej deklaracji typ danych elementów listy jest określany podczas inicjalizacji listy, czyli przy dodawaniu elementów.

List myList = new ArrayList<String>();
Vector myVector = new Vector();
LinkedList linkedList = new LinkedList();
Stack stack = new Stack();
stack.add("Paul");
linkedList.add(1);
myVector.add(1.2f);
myList.add('a');

Teraz do naszego stack można dodawać tylko ciągi znakowe, do linkedList liczby całkowite, do myVector liczby zmiennoprzecinkowe, a myList to lista znaków.

Jak działa ArrayList

Jeśli znasz już zwykłe tablice, znasz też trochę ArrayList. W rzeczywistości ArrayList jest tablicą dynamiczną, a wewnątrz niej znajduje się zwykła tablica. Ta tablica pełni rolę magazynu danych. ArrayList przechowuje tylko typy referencyjne, wszelkie obiekty, w tym dowolne zewnętrzne klasy, ciągi znaków, strumienie wyjściowe i inne kolekcje. Do przechowywania typów prostych w ArrayList służą klasy osłonowe. Podczas tworzenia listy możemy od razu określić jej rozmiar, ale w większości przypadków tego nie robimy. Domyślnie rozmiar ArrayList = 10. Jak wygląda dodanie nowego elementu do ArrayList? Najpierw wykonywane jest sprawdzanie, czy w tablicy wewnętrznej jest wystarczająco dużo miejsca i czy zmieści się jeszcze jeden element. Jeśli jest miejsce, nowy element jest dodawany na końcu listy, czyli w komórce następującej po ostatnim elemencie. Jego indeksem będzie arraylist.size(). Jeżeli właśnie utworzyliśmy naszą listę i jest ona pusta, oznacza to, że arrayList.size() = 0. W związku z tym nowy element zostanie dodany do komórki o indeksie 0. Jeśli okaże się, że miejsca jest za mało, wewnątrz ArrayList tworzona jest nowa tablica o rozmiarze (rozmiar OldArray * 1.5) + 1. Na tej samej zasadzie realizowane jest wstawienie na środku listy, ale jednocześnie wszystkie elementy następujące po wstawionym elemencie są przesuwane w prawo. Czyli jeśli mamy w tablicy 5 elementów i musimy wstawić element do komórki nr 2 (czyli trzeciej), to elementy 0 i 1 pozostają na swoim miejscu, w komórce 2 pojawia się nowy element i jego poprzednik trafia do komórki trzy i tak dalej.

Przykład Java List (realizacja Arraylist)

import java.util.*;

public class ArrayListExample2 {
   public static void main(String[] args) {
       List<String> myFriendsList = new ArrayList();
       //we created list of some objects 
       System.out.println( "the size of myList before init = " + myFriendsList.size());
       myFriendsList.add("Alex");
       myFriendsList.add("Tanya");
       myFriendsList.add("Veloxy");
       myFriendsList.add("Alex");
       myFriendsList.add("Andrew");
       System.out.println(myFriendsList);
       System.out.println( "the size of myList after init = " + myFriendsList.size());

       myFriendsList.add("Ihor");
       System.out.println(myFriendsList);
       System.out.println("the size of my list = " +  myFriendsList.size());


       //here the program will print out the first appearance of "Alex" element
       System.out.println(myFriendsList.indexOf("Alex"));
       //program will print out the first appearance of "Alex" element starting from the element 0

       myFriendsList.remove(3);
       System.out.println(myFriendsList.get(3));
       System.out.println("after removing one of Alex's there is only one Alex: " + myFriendsList);
       System.out.println(myFriendsList.get(1));



       myFriendsList.clear();
       System.out.println("the size of the vector after clear method = " +  myFriendsList.size());

   }
}

Oto wynik działania programu:

Jak działa LinkedList

W LinkedList elementy są w rzeczywistości linkami w tym samym łańcuchu. Każdy element, oprócz przechowywanych danych, posiada link do poprzedniego i następnego elementu. Te linki umożliwiają nawigację pomiędzy elementami. Iterator obsługuje przemieszczanie w obu kierunkach. Implementuje metody pobierania, usuwania i wstawiania na początku, w środku i na końcu listy. Umożliwia dodawanie dowolnych elementów, w tym wartości null. LinkedList implementuje dwa interfejsy — nie tylko List, ale również Deque. Daje to możliwość tworzenia kolejki dwukierunkowej z dowolnych elementów, nawet nullowych. Każdy obiekt umieszczony na połączonej liście jest węzłem (węzeł, node). Każdy węzeł zawiera element, link do poprzedniego i następnego węzła. W rzeczywistości połączona lista składa się z sekwencji węzłów, z których każdy jest przeznaczony do przechowywania obiektu o typie zdefiniowanym podczas jego tworzenia.

Przykładowy kod

import java.util.*;
public class LinkedListTest {

       public static void main(String args[]){

           List myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           myLinkedList.add(5);
           myLinkedList.remove(1);
           System.out.println(myLinkedList);
           myLinkedList.size(); //3
           
           //add new element at the specified position:
           myLinkedList.add(2,7);
           System.out.println(myLinkedList);
                }
       }

Wynik to:

Przykładowy kod z Vector

Vector jest również dynamiczną realizacją tablicy i jest bardzo podobny do ArrayList, ale jest synchronizowany i ma pewne starsze metody, których nie zawiera framework collection. Oto prosty przykład użycia tej klasy.

import java.util.Vector;

public class VectorExample1 {

   public static void main(String[] args) {
       Vector vector = new Vector();
       System.out.println("the size of the empty vector = " +  vector.size());
       vector.add("Alex");
       vector.add("Tanya");
       vector.add("Andrew");
       System.out.println(vector);
       vector.add("Alex");
       vector.add("Ihor");
       System.out.println(vector);
       System.out.println("the size of the vector = " +  vector.size());
       System.out.println("the first element of the vector = " + vector.firstElement());

       //here the program will print out the first appearance of "Johnny" element
       System.out.println(vector.indexOf("Andrew"));
       //program will print out the first appearance of "Johnny" element starting from the element 1
       System.out.println(vector.indexOf("Alex", 1));
       System.out.println(vector);
       vector.clear();
       System.out.println("the size of the vector after clear method = " +  vector.size());

   }
}

Wyświetlone zostanie:

Przykładowy kod z klasą Java Stack

import java.util.Stack;

public class StackTest {
   public static void main(String[] args) {
       Stack stack = new Stack();
       System.out.println(stack.isEmpty());
       stack.add("Paul");
       stack.add("Johnny");
       stack.add("Alex");
       System.out.println(stack.isEmpty());
       stack.push("Andrew");
       System.out.println(stack);
       stack.pop();
       System.out.println(stack);
   }
}

Stack posiada nie tylko metody add() i remove() ale także push i pop, które są typowe dla tej struktury danych. Stos działa zgodnie z zasadą "pierwszy wchodzi, ostatni wychodzi" — to taka antykolejka. Dlatego operacja pop zdejmuje element, który był umieszczony na stosie jako ostatni. Oto wynik działania naszego przykładu: