В програмирането, както и в математиката, доста често се налага да обработваме дадено множество от елемети. Пример за това е прибавяне на елемент към дадено множество, премахване на елемент от множество, подреждане на множество по даден закон или даден показател. Структурите от данни са една основна концепция за съхранението и организацията на данните в компютърната наука.
Структурите от данни могат да бъдат разглеждани като математически, логически модел, по който са организирани данните или абстрактни типове данни. Детайлното познаване на тази концепция води до създавене на по-ефективен и по-структуриран програмен код.
Един добре познат пример за структура от данни е масивът. Както добре знаем, масивите са линейни структури от данни, записани последователно в паметта, като всеки един елемент притежава индекс и достъпа до даден елемент става чрез неговия индекс.
Основната идея на дадената статия е да разгледа някои от останалите линейни структури от данни-списъци, стекове и опашки.
Свързан списък(LinkedList)
Както подсказва името на тази структура, списъкът представлява множество от елементи, произволно разположени в паметта, където всеки елемент съхранява в себе си адреса на следващия елемент.
Основният въпрос, който възниква, е какви са предимствата и недостатъците на свързания списък спрямо масива?
Предимства:
- Дава възможност за добавяне или изтриване на елемент.
- Не е необходимо наличие на голям блок от последователна свободна памет.
Недостатъци:
- По – бавни са.
- Нямат директен достъп до елемент
- Използват повече памет за съхранението на адреси.
Реализация на LinkedList
В Java съществува клас LinkedList, имплементиращ интерфейса List, който от своя страна наследява интерфейса Collection.
Важно е да се отбележи, че List е интерфейс и не може да се инстанцира!
Основните методи, които притежава са:
– void add(int, Object) – добавя елемент на позиция определена от първия аргумент
– boolean remove(Object) – премахва елемент
– Object remove (int) – премахва елемент на дадена позиция
– Object get(int) – взима елемент със съответния индекс
– Boolean contains (Object) проверява дали даден елемент е част от списъка
– int indexOf(Object) – връща позицията на елемента
Нека дадем следния пример.
import java.util.*;
public class LinkedListDemo {
public static void main(String args[]) {
// create a linked list
LinkedList ll = new LinkedList();
// add elements to the linked list
ll.add("I");
ll.add("am");
ll.add("example");
ll.add("!");
System.out.println("Original contents of ll: " + ll);
// remove elements from the linked list
ll.remove("!");
ll.remove(2);
System.out.println("Contents of ll after deletion: " + ll);
// remove first and last elements
ll.removeFirst();
ll.removeLast();
}
}
При компилиране ще получим следния резултат:
Original contents of ll: [I, am, example, !]
Contents of ll after deletion: [I, am]
ll after deleting first and last: []
Въпреки, че дадения код е коректно написан, в него има известни слабости. След Java 5 се появиха така наречените шаблонни класове (generics). Необходимостта от това се появява защото, както се вижда от горния код, елементите на дадена колекция се предават като обекти от базовия клас Object, което носи някой отрицателни черти. Такъв е случаят с преобразуване на един тип в друг.
Показаният код би изглеждал по-добре, като редът за създаване на обект от тип свързан списък се преобразува по следния начин:
LinkedList<String> ll= new LinkedList<String>();
Свързаният списък поддържа два конструктора:
• LinkedList( ) – създаващ празен списък;
• LinkedList(Collection c) – създаващ свързан списък , инициализиран с елементи от колекцията с.
За повече информация относно всички методи погледнете документацията на Oracle.
Съществува и хибриден вариант между масив и свързан списък – ArrayList или динамичен масив.
Динамичният масив представлява масив, в който могат да се добавят и изтриват елементи, като за целта една част от елементите се пазят свободни. Това го прави предпочитан от повечето програмисти. При него, както и при свързания списък, е имплементиран интерфейсът List. Недостатък на тази структура е, използването на повече памет и че в случай когато за добавяне на нови елементи, е необходим голям блок от последователна памет и тази памет не е налична, то целият масив се презаписва на ново място, което е бавна операция.
Пример
List listA = new ArrayList();
listA.add("First element");
listA.add(" Second element ");
listA.add("Third element");
listA.add(0, "element 0");
В показания пример на последния ред методът add получава два аргумента, като първия оказва позицията на елемента в списъка.
Важно е да се отбележи, че динамичния масив може да съхранява само елементи от референтен тип – String, Integer, Double- разположени в динамичната памет -heap.
Пример
ArrayList numbers=new ArrayList(); numbers.add(1); numbers.add(2); numbers.add(3);
Стек
Стекът представлява структура от данни при която организацията на елементите е на принципа последен влязъл, първи излязъл -LIFO (Last Input First Output). Представянето на тази структура може да се онагледи чрез пример с кутия в която се поставят книги. Последната книга ще “излезе” пърава от кутията,а първата поставена ще”излезе” последна.
Структурата от данни стек представлява абстрактна структура, която има различни реализации. Студентите познават реализацията чрез свързан списък от дисциплината ПИК2. Тук ние ще разгледаме класът Stack
Основни методи:
push(T) – добавя нов елемент на върха на стека
pop() – връща най-горния елемент и го премахва от стека
peek() – връща най-горния елемент без да го премахва
size()- връща броя на елементите в стека
contains(Т) -проверява дали даден елемент Т се съдържа в стека
toArray() – връща масив, с елементите на стека
clear() – изтрива всички елементи
пример:
public static void main(String[] args) {
// create a linked list
Stack cars=new Stack();
cars.push("Honda");
cars.push("Opel");
cars.push("Mazda");
cars.push("Audi");
System.out.println(cars.peek());
}
Резултатът от дадения код ще бъде: Audi
Опашка
Опашката също като стека е абстрактна структура с различни реализации. При нея елементите се редят на опашка – първи влязъл, първи излязъл-FIFO(First Input First Output)
В Java опашката се реализира чрез интерфейса Queue
Методи съдържащи се в интерфейса:
-offer(T) – добавя елемент на края на опашката
-peek() – връща елемент от началото на опашката без да го премахва
-poll() – връща елемент от началото на опашката като го премахва
-contains(T) -проверява дали даден елемент се съдържа в опашката
-clear() – премахва всички елементи от опашката
Нека разгледаме горния пример реализиран с опашка и сравним резултатите.
public static void main(String[] args) {
// create a linked list
Queue cars=new LinkedList();
cars.offer("Honda");
cars.offer("Opel");
cars.offer("Mazda");
cars.offer("Audi");
System.out.println(cars.peek());
}
}
Резултатът тук е – Honda. Което онагледява разликата между двете реализации.
Сортиране чрез Comparator:
Comparator е интерфейс в Java, който предоставя възможност за сравняване на обекти и подредба(сортиране) на структури от данни. Можете да извикате метод sort() на клас Collections, на който освен колекцията, да подадете и компаратор, с който тя да бъде сортирана, в случай че не е колекция от числа или от стрингове. Ако не сте създали предватително компаратор, ще трябва да го създадете като анонимна променлива и да имплементирате иначе абстрактния му метод compareTo(). За стринговете методът compareTo() e предефиниран. Ето пример как се прави това:
Нека имаме клас Customer и ще сравняваме обекти от този клас по име.
public class Test {
static class Customer {
private String name;
private int years;
Customer(String name, int years){
this.name = name;
this.years = years;
}
}
public static void main(String[] args) {
List listOfCustomers = new ArrayList();
listOfCustomers.add(new Customer("Adam",18));
listOfCustomers.add(new Customer("Saly", 19));
listOfCustomers.add(new Customer("Bob", 15));
listOfCustomers.add(new Customer("Marry", 21));
Collections.sort(listOfCustomers, new Comparator() {
@Override
public int compare(Customer o1, Customer o2) {
String firstCustomerName = o1.name.toUpperCase();
String secondCustomerName = o2.name.toUpperCase();
//asc
return firstCustomerName.compareTo(secondCustomerName);
//desc
//return secondCustomerName.compareTo(firstCustomerName);
}
});
for(Customer cust : listOfCustomers){
System.out.println(cust.name);
}
}
}
Резултатът е сортиран по азбучен ред списък с имена на клиенти:
Adam
Bob
Marry
Saly
Можем да направим и случай, при който искаме клиентите да се сортират по години. Ще използваме друг вариант за реализиране на сортиране чрез компаратор – чрез първоначално създаване на компаратора и последващо подаване на sort() метода:
public static void main(String[] args) {
List listOfCustomers = new ArrayList();
listOfCustomers.add(new Customer("Adam",18));
listOfCustomers.add(new Customer("Saly", 19));
listOfCustomers.add(new Customer("Bob", 15));
listOfCustomers.add(new Customer("Marry", 21));
Comparator customerYearComparator = new Comparator() {
@Override
public int compare(Customer o1, Customer o2) {
int firstCustYears = o1.years;
int secondCustYears = o2.years;
//for asc
return firstCustYears - secondCustYears;
//for desc
//return secondCustYears - firstCustYears
}
};
Collections.sort(listOfCustomers,customerYearComparator);
for(Customer cust : listOfCustomers){
System.out.println(cust.name + " - " + cust.years);
}
}
}
Резултатът е:
Bob – 15
Adam – 18
Saly – 19
Marry – 21
Явор Томов, Даниел Джолев