C, PHP, VB, .NET

1. Масиви: Когато се заговори за понятието "списък" всеки начинаещ програмист моментално се досеща за най-често използваната в учебните примери структура - масив. Масивите представляват наредени елементи от един и същи тип данни (може да бъде както примитивен тип, така и данни от определен клас). Те са с константна дължина (т.е. точно определен брой елементи). Това е колкото полезно (няма опасност от "утечки на памет"), толкова и неудобно (трябва да се пазим от проблема с "препълване", често се заделя повече памет отколкото е необходима, и др.). Можем да обобщим проблемите свързани с използването на масив в три точки:

1. Обикновено заделяме повече памет, отколкото използваме. Когато говорим за данни с обем в малки граници (брой ученици в клас, работници в малка фирма, продуктова гама от традиционни стоки и др.), това не е проблем. Когато данните обаче варират (унифициран софтуер за малки и големи фирми, данни записани в зависимост от натовареността и посещаемостта на уебсайт и др.), то използването на масив започва да изглежда като голямо разхищение на памет;
2. Ако не желаем да изпадаме в ситуация, в която не можем да добавяме повече елементи, то трябва да се направи доста тежка откъм процесорно време операция:
   a) Заделя се памет за нов масив с 1 или няколко елемента по-голям от стария;
   б) Копират се данните от стария масив в новия;
   в) Премахва се указателят към стария масив и се дава на GarbageCollector да освободи паметта.
3. Най-често ние не "изтриваме" елементите на масив, а просто слагаме стойност "null" в съответната клетка (както беше в горния пример). По този начин паметта остава заделена и не може да се освободи. Както и в точка 1 - това е разхищение на памет. Алтернативата с реално изтриване на елемент също изисква много процесорно време и е бавна операция:
   a) Заделя се памет за нов масив с 1 по-малък от стария;
   б) Копират се всички елементи от стария в новия масив, с изключение на изтривания;
   в) Премахва се референцията към стария масив и се оставя на GarbageCollector да освободи паметта.

Поради изброените по-горе проблеми, когато имаме данни заемащи голям обем памет и/или когато работим с множества от елементи които не са с фиксирани граници, то традиционните масиви не са препоръчителна структура от данни. Вместо тях е удобно да използваме т.нар. "списъци" или "динамични масиви". Традиционните масиви следва да бъдат използвани предимно в случаите, когато работим с фиксирано количество данни.

2. Списъци: в Java съществува клас LinkedList или в превод "свързан списък". Това е динамична структура от данни (без ограничение на максимален брой елементи, стига да има достатъчно памет). Елементите в LinkedList са "наредени на опашка", т.е. имаме винаги един първи, един последен елемент, а всички останали имат свой "предходен" и "следващ". Такива списъци се наричат "двусвързани".

LinkedList се дефинира по следния начин:

java.util.LinkedList<Integer> list = new java.util.LinkedList<Integer>();

Естествено в ъгловите скоби вместо Integer (цяло число) може да стои всякакъв друг тип данни или обект. Нека сега разгледаме най-важните методи:

а) Добавяне на елемент в края на списъка:

list.add(new Integer(1));
list.addLast(new Integer(2)); // еквивалентно на първото

б) Добавяне на елемент в началото на списъка:

list.addFirst(new Integer(3));

в) Размер (брой елементи на списък):

System.out.println("\nList size: "+list.size());

г) Отпечатване на съдържанието на списъка чрез итератор:

java.util.Iterator it = list.iterator();
while(it.hasNext()){
   System.out.print(it.next()+" ");
}

Може да приемете, че обектът java.util.Iterator се използва като "указател" към текущия елемент на списък. В началото той винаги "сочи" към първия елемент. Показания пример е стандартен за "обхождане" на списък елемент по елемент.

д) Добавяне на елемент на определена позиция:

list.add(2, new Integer(25)); // първи аргумент е позиция, а втори стойност

е) Прочитане на елемент от определена позиция:

System.out.println("The element at position 2 is: "+list.get(2));

ж) Прочитане на първи и последен елементи:

System.out.println("The first element is is: "+list.getFirst());
System.out.println("The last element is is: "+list.getLast());

з) Отпечатване на съдържанието на списъка БЕЗ итератор:

for (int i=0; i<list1.size(); i++){
 System.out.print(list1.get(i)+" ");
}

и) Изтриване на елемент: тук освен фактическото премахване на елемента имаме и функционалност същевременно да прочетем стойността й. Така например този вид списък може лесно да бъде използван като стек:

int first = list.removeFirst();
System.out.println("First element: "+first+" removed...");
int last = list.removeLast();
System.out.println("Last element: "+last+" removed...");
int x = list.remove(1);
System.out.println("Element with index 1: "+x+" removed...");
System.out.println("Now list contains:");
it = list.iterator();
while(it.hasNext()){
   System.out.print(it.next()+" ");
}

й) Изтриване на всички елементи в списък:

list.clear();

к) Проверка дали списък е празен или не:

if (list.isEmpty()) System.out.println("List is empty");

л) "Клониране" на списък:

java.util.LinkedList list = new java.util.LinkedList();
list.add(new Integer(1));
list.addLast(new Integer(2));
list.addFirst(new Integer(3));
java.util.LinkedList listClone = list.clone();

м) Търсене на елемент в списък:

if(list.contains(3)) System.out.println("List has element with val 3");

н) Промяна на елемент с нова стойност:

list.set(1, new Integer(25)); // първи аргумент индекс, а втори стойност

о) Добавяне на един списък в края на друг или вмъкването му в даден индекс:

java.util.LinkedList list1 = new java.util.LinkedList();
list1.add(new Integer(1));
list1.addLast(new Integer(1));
list1.addFirst(new Integer(1));
java.util.LinkedList list2 = new java.util.LinkedList();
list2.add(new Integer(2));
list2.addLast(new Integer(2));
list2.addFirst(new Integer(2));
list1.addAll(list2);
list1.addAll(1, list2);

Виждате, основната разлика между LinkedList и Array е в липсата на предварително фиксиране на размера на структурата. Един списък може да бъде толкова голям, колкото налична памет има.

Въпреки, че на няколко места използвахме термина "индекс", все пак трябва да знаете, че то не е коректно. Физически в паметта отделните елементи на LinkedList са разположени в различни места, а във всеки от тях се пази препратка към следващия. Така всъщност ние не знаем къде точно се намира елемент №4 от самото начало - налага се да тръгнем от елемент №1, през №2 и №3, за да стигнем до търсения. Така въпреки, че остава скрито за нас като потребители, извличането на елемент от даден индекс е значително по-бавна операция от тази при масивите. Изтриването на елемент също включва в себе си първо "намиране" на елемента. Така можем да заключим, че LinkedList наистина спестява памет в сравнение с масивите, но за сметка на това може да се каже, че е значително по-бавен.

3. Динамични Масиви: - В общи линии можем да приемем, че динамичните масиви (ArrayList) са нещо средно между свързани списъци и обикновени масиви. Всъщност те се опитват да комбинират предимствата и на едните и на другите. Един ArrayList първоначално заделя определен обем от памет подобно на стандартния масив. Елементите, които добавяме се натрупват един след друг в тази памет (т.е. тук имаме истинско понятие "индекс", защото елементите са на поредни места в паметта). Достъпването до елемент е бързо както при масивите. Изтриването на елемент също - просто последващите се преместват назад. Проблемът със следенето за препълване на масив обаче липсва - ArrayList си разширява капацитета автоматично. Вече демонстрирахме подобна функционалност при динамичните низове (StringBuffer и StringBuilder).

С ArrayList се работи подобно на LinkedList. Някои методи са премахнати (addFirst, addLast, removeLast, removeLast). Ето само списък с наличните познати методи (няма да даваме примери, понеже синтаксисът е аналогичен на този на LinkedList):

add(елемент) - добавя елемент в края на списъка;
add(индекс, елемент) - добавя елемент в даден индекс (и премества следващите напред);
clear() - изтрива всички елементи;
contains(елемент) - търси елемента в списъка и връща true или false ако е намерен или не;
get(индекс) - връща стойността на елемент от даден индекс;
isEmpty() - връща true или false в зависимост дали списъка е празен;
remove(индекс) - изтрива елемент на даден индекс;
set(индекс, елемент) - променя стойността на елемент на даден индекс с нова стойност);
size() - връща броя елементи на масива;

Новите методи спрямо LinkedList са:

a) Подсигуряване за минимален капацитет:

java.util.ArrayList<Integer> arrlist = new java.util.ArrayList<Integer>();
arrlist.ensureCapacity(10);

Понеже автоматичното разширяване на динамичен масив може да бъде "скъпа" операция (ако няма място за разширяването), то с ensureCapacity ние се подсигуряваме, че имаме достатъчно голям размер. Всъщност показаното в горния пример е грешен метод - можем да подсигурим размера директно чрез конструктора при инициализация:

java.util.ArrayList<Integer> arrlist = new java.util.ArrayList<Integer>(10);

Използвайте ensureCapacity() ако е необходимо да разширявате масива с много елементи при извършаването на дадена операция.

б) indexOf(елемент) - връща индекса на първото срещане на елемента вътре в списъка (не се поддържа търсене от "елемент нататък", както беше при клас String);

в) lastIndexOf(елемент) - индекса на последното срещане на елемента вътре в списъка;

г) removeRange(индекс "от", индекс "до") - изтрива елементите от първия до втория индекс подадени като аргумент. Например list.removeRange(2,4); изтрива елементи от 2 до 4 включително;

д) trimToSize() - "свива" капацитета на масива до броя на елементите му. Обикновено го използваме, за да освободим памет в случаи когато знаем, че няма да има повече добавяне на елементи.

4. Опашка и стек: Като частни случаи на двусвързаният списък (LinkedList) са списъците от тип Queue (опашка) и Stack (стек). При опашката можете да добавяте елементи само в края на списъка и премахване на елемент само от началото на списъка. При опашката операции "търсене" и "извличане по индекс" няма. Опашките се използват често при създаване на интернет приложения, при които трябва да обработваме поредни заявки в стил FIFO (first in first out).

При стека пък се добавят елементи (push) само в края на списъка и се изтриват (pop) пак само в края на списъка. Има и операция "прочитане на елемент", която връща (peek) стойността на последния елемент без да го изтрива. Тази структура е от тип LIFO (last in first out). Представете си стека като натрупана купчина от книги. За да достигнете до най-долната трябва преди това да премахнете една по една по-горните над нея.

5. Вектор: Класът Vector е много подобен на ArrayList. Той има същите методи като него, но има няколко съществени разлики:

• Синхронизиран е, т.е. безопасен при работа в многонишкова среда. По-нататък като се запознаем с многонишковото програмиране ще видим, че това е важно свойство на споделените ресурси между подпрограми;
• Понеже не е синхронизиран, ArrayList е значително по-бърз;
• Vector използва Enumeration вместо Iterator. Основната разлика от потребителска гледна точка е, че Enumeration няма метод remove(), докато Iterator го има (можете да изтривате елементи чрез него). Другата разлика е, че при Enumeration се използват методи hasMoreElement() и nextElement(), вместо hasNext() и next(). От потребителска гледна точка действат по един и същи начин.