Лабораторно упражнение 10

Колекции - част 1

Структури от данни

  • Основни структури от данни:
    • Масиви
    • Свързани списъци
    • Хеш таблици
    • Дървета
  • Основни операции за работа със структури:
    • добавяне
    • триене
    • търсене
    • обхождане

Структурите от данни намират своята реализация в Java като Arrays, List, Set и Map.

Колекции

Колекциите в Java са част от Java Collections Framework (JCF), който представлява набор от интерфейси и класове, улесняващи работата с групи обекти.

Фреймуъркът предоставя структури от данни и общи операции върху тях като добавяне, премахване, търсене, обхождане и сортиране.

Колекциите са:

  • динамични
  • гъвкави
  • с множество функционалности
  • обектно-ориентирани (работят само с обекти)

Масиви vs колекции

характеристика масиви колекции
размер фиксиран динамичен
тип данни примитиви и обекти обекти
дублиране на елементи позволява зависи от типа колекция
операции ограничен набор, достъп по индекс широк набор
структура едномерни/многомерни List, Set, Map
гъвкавост ниска висока

Масивите са подходящи за използване в ситуации, когато размерът е предварително известен или се изисква бърз достъп по индекс.

От своя страна, колекциите са подходящи за използване когато размерът не е предварително известен, налага се извършване на множество добавяния или премахвания на елементи, както и се работи със сложни структури от данни.

List и Set

И двата интерфейса наследяват интерфейса Collection, който предоставя следните общи методи:

//връща броя на елементите в колекцията
int size()
//проверява и връща дали е празна колекцията
boolean isEmpty()
//проверява и връща дали колекцията съдържа предавания като параметър елемент
boolean contains(Object element)
//добавя елемент в колекция (връща истина при успешно добавяне)
boolean add(E element)
//премахва елемент от колекция (връща истина при успешно изтриване)
boolean remove(Object element)
//извлича и връща итератора на колекцията
Iterator<E> iterator()
//проверява и връща дали всички елементи се съдържат в колекцията
boolean containsAll(Collection<?> c)
//добавя всички обекти от списъка към колекцията
boolean addAll(Collection<? extends E> c)
//премахва всички обекти от списъка към колекцията
boolean removeAll(Collection<?> c)
//премахва всички елементи от колекцията, които не присъстват в подавания списък от елементи
boolean retainAll(Collection<?> c)
//почиства паметта, към която сочи колекцията
void clear()
//преобразува колекцията в масив от класа Ojbect
Object[] toArray() 
//преобразува колекцията в масив от програмно дефиниран клас
<T> T[] toArray(T[] a)

List

Колекция от тип List:

  • позволява дублиране на елементи;
  • елементите са подредени според реда на добавяне (метода add добавя предавания като параметър елемент винаги в края на списъка)
  • поддържа индекси и съответно достъп до елемент може да се осъществи по индекс както при масивите
  • подходяща за използване при решаване на проблеми, изискващи списъци, последователности или работни опашки.

Някои от типичните имплементации на интерфейса List са:

  • ArrayList – предоставя бърз достъп, бавни операции в средата
  • LinkedList – бързо добавяне и/или премахване на елементи, по-бавен достъп до тях
  • Vector – остаряла имплементация, синхронизиран списък

Set

Колекция от тип Set:

  • не позволява дублиране на елементи
  • подредбата на елементите не е гарантирана, тъй като зависи от конкретната имплементация
  • не поддържа индекси
  • подходяща при необходимост от работа с уникални елементи, филтриране или при търсене.

Често използвани имплементации на Set са:

  • HashSet – най-бърз, няма подредба на елементите
  • LinkedHashSet – запазва реда на добавяне
  • TreeSet – поддържа автоматично сортиран ред.

Итератори

  • Итераторите предоставят унифициран начин за обхождане на елементите на дадена колекция.
  • Колекциите (както и масивите) могат да се обхождат с foreach цикъл.
  • В java са дефинирани интерфейси, поведението на които се имплементира от всички колекции.
//Интерфейси Iterable
public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}
//Интерфейси Iterable
public interface Iterable<T> {
    Iterator<T> iterator();
}
  • Методът next() връща следващия елемент в колекцията;
  • Методът remove() премахва от колекцията елемента, последно върнат от next();
  • Ако колекцията бъде модифицирана докато бъде итерирана, по какъвто и да е начин, различен от извикване на remove() на итератора, поведението на итератора е недефинирано и води до грешка (ConcurrentModificationException).

Comparable и Comparator

Това са два интерфейса, определящи реда на елементите в дадена колекция и се използват за сортиране.

Използването на интерфейс Comparable дава възможност за дефиниране на естествен ред в контекста на конкретен обект, т.е. по какъв критерий ще бъдат подредени елементите при сортиране на колекция, съдържаща такива обекти.

Ако се налага използването на колекции от тип TreeSet или ще се използва Collections.sort(), базовия за конкретната колекция клас задължително трябва да имплементира интерфейса Comparable. Интерфейсният метод връща положителна стойност, отрицателна стойност или нула, което подсигурява подредба в естествен ред (възходящ).

public class Book implements Comparable<Object> {
    private String title;
	private String author;
    private int publishingYear;
	private double price;

    // constructor, getters, setters, equals, toString

    @Override
    public int compareTo(Object o) {
        Book book = (Book) o;
        if (this.publishingYear < book.publishingYear) return -1;
        if (this.publishingYear > book.publishingYear) return 1;
        return 0;
    }
}

Интерфейсът Comparator се използва за прилагане на външни правила за сравнение. За разлика от Comparable, интерфейсният метод compare(T o1, T o2) приема два обекта от един и същи тип и ги сравнява по зададения критерий. Използването на Comparator осигурява възможности за сортиране по различни критерии без да се налага промяна в базовия за колекцията клас. Примерът по-долу показва различни начини за сортиране на колекция от книги.

import java.util.Comparator;

public class AuthorComparator implements Comparator<Object> {

    @Override
    public int compare(Object o1, Object o2) {
        Book book1 = (Book) o1;
        Book book2 = (Book) o2;
        return book1.getAuthor().compareTo(book2.getAuthor());
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Library {

    private List<Book> books = new ArrayList<>();

    public void sortByPublishingYear() {
        Collections.sort(books); // използва критерия, зададен в метода compareTo
    }

    public void sortByAuthor() {
        Collections.sort(books, new AuthorComparator());
    }

    public void sortByTitle() {
        books.sort(new Comparator<Book>() {
            @Override
            public int compare(Book o1, Book o2) {
                return o1.getTitle().compareTo(o2.getTitle());
            }
        });
    }

    public void sortByPrice() {
        books.sort(Comparator.comparingDouble(Book::getPrice));
    }
}

Важно: могат да бъдат сортирани само колекции от тип List.

Queue

Queue (опашка) е структура от данни в Java Collections Framework, която следва принципа FIFO (First In, First Out).

Елементите се добавят в края и се премахват от началото – точно както в опашка от хора.

Queue се използва, когато:

  • задачи трябва да се обработят в реда, в който са пристигнали
  • изисква се реализация на буфер
  • имплементация на алгоритми като BFS (Breadth First Search)
  • моделира се система с чакаща заявки.

Интерфейсът Queue наследява интерфейса Collection, но добавя специализирани методи: методи, които хвърлят изключения при грешка и методи, които връщат специална стойност (false, null).

  • Добавяне

    – add(e) — хвърля изключение, ако мястото е пълно

    – offer(e) — връща false, ако елементът не може да бъде добавен в опашката

  • Премахване

    – remove() — хвърля изключение при празна опашка

    – poll() — връща null при празна опашка

  • Преглеждане на първия елемент (без премахване)

    – element() — хвърля изключение ако няма такъв

    – peek() — връща null при празна опашка

Най-често използваните имплементации на интерфейса Queue са:

  • LinkedList - най-често използвана имплементация на Queue; предоставя бързо добавяне/премахване от двата края; може да действа като Queue, Stack или Deque
  • PriorityQueue - не гарантира FIFO; сортира елементите според естествения им ред или чрез Comparator; използва се за алгоритми като Dijkstra
  • ArrayDeque - много бърза имплементация на Queue и Deque; по-добра от Stack и LinkedList в повечето случаи; няма капацитетни ограничения.

Използването на интерфейс Queue е подходящо в следните случаи:

  • при задачи, които чакат обработка (producer-consumer)
  • при обработка на събития
  • при навигация на графи (BFS)
  • при управление на принтери, процеси, заявки, мрежови пакети

Table of contents