Lista dwukierunkowa
Kolejną ciekawą strukturą danych jest lista dwukierunkowa (ang. linked list). Działa podobnie jak zwykła lista, ale ma trochę inne zastosowanie. Zwykła lista jest dość wolną strukturą jeśli chodzi o modyfikowania danych, dlatego używaj jej do przechowywania informacji i ich odczytu. Ponieważ lista dwukierunkowa posiada dwa wskaźniki (na element następny oraz poprzedni), modyfikowanie danych jest dużo wydajniejsze. Dlatego jeśli będziesz usuwać, dodawać jakiś element ze środka, to pamiętaj, aby używać właśnie tej struktury.
Interfejs Comparator
Postaram się teraz, korzystając z LinkedList napisać swoje własne sortowanie zawartych w niej danych. Użyję tu interfejsu Comparator.
public class Song {
private String name;
private String author;
private double duration;
public Song(String name, String author, double duration) {
this.name = name;
this.author = author;
this.duration = duration;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getAuthor() {
return author;
}
public void setAuthor(String author) {
this.author = author;
}
public double getDuration() {
return duration;
}
public void setDuration(double duration) {
this.duration = duration;
}
@Override
public String toString() {
return "Song [name=" + name + ", author=" + author + ", duration=" + duration + "]";
}
}
public class DurationComparator implements Comparator<Song>{
@Override
public int compare(Song o1, Song o2) {
if (o1.getDuration() > o2.getDuration()) return 1;
else if (o1.getDuration() == o2.getDuration()) return 0;
else return -1;
}
}
public class PlayList {
public static void main(String[] args) {
List<Song> songs = new LinkedList<>();
songs.add(new Song("Beautiful day", "U2", 4.06));
songs.add(new Song("Song 2", "Blur", 2.02));
songs.add(new Song("Polska", "Kult", 5.26));
Collections.sort(songs, new DurationComparator());
System.out.println(songs);
}
}
Wpierw napisałem klasę Song, która zawiera nazwę piosenki, autora i jej długość. Następnie wykorzystałem interfejs Comparator, aby zaimplementować go w klasie DurationComparator, która porównuje dwa obiekty ze sobą (podobnie jak compareTo). Na końcu w klasie PlayList został a napisana lista piosenek i odpowiednio posortowana, używając metody sort z klasy pomocniczej o nazwie Collections.
W podobny sposób możesz sortować każdą kolekcję uporządkowaną.
Zbiór dwukierunkowy
Lista dwukierunkowa poza optymalizacją modyfikacji elementów, nie różni się niczym od zwykłej tablicy dynamicznej. Dużo bardziej zróżnicowana od klasy HashSet jest inna implementacja interfejsu Set o nazwie LinkedHashSet.
Set<String> colours = new LinkedHashSet<>();
colours.add("niebieski");
colours.add("zielony");
colours.add("czerwony");
colours.add("zielony");
System.out.println(colours);
Wynik:
[niebieski, zielony, czerwony]
W przeciwieństwie do zwykłego HashSet ta implementacja zbioru zachowuje kolejność zapisanych danych. Oczywiście wciąż zbiór nie może przechowywać duplikatów. Minusem tego rozwiązania jest gorsza wydajność tej struktury od zwykłej klasy HashSet. W podobny sposób możesz używać innej implementacji interfejsu Map, czyli LinkedHashMap.
Inne kolekcje (rzadko używane):
- Vector – synchronizowana (bezpieczny wątkowa) wersja ArrayList.
- Hashtable – synchronizowana wersja HashMap.
- PriorityQueue – implementacja kolejki (first-in-first-out).
- Stack – implementacja stosu (last-in-first-out).
Istnieją także kolekcje, które zapewniają poprawną pracę w środowisku wielowątkowym. Będę je omawiać w kursie zaawansowanym, gdzie skupię się m.in. na pracy z wątkami (ang. threads).
Linki do zewnętrznych źródeł odnośnie pozostałych struktur:
- https://www.javatpoint.com/java-stack
- https://beginnersbook.com/2013/12/vector-in-java/
- https://www.geeksforgeeks.org/hashtable-in-java/
Link do kodu: https://github.com/developeronthego/java-middle/tree/master/src/main/java/middle/lesson18