Списък (абстрактен тип данни): Разлика между версии

Списък (List<T>) е линейна структура от данни, съдържаща в себе си поредица от елементи, която в най-общия смисъл е вид [[масив (програмиране)|масив]], с тази разлика, че може да се оразмерява динамично. Списъците имат свойството капацитет, определящ текущата им дължина и брояч - броя на елементите съдържащи се в него. С помощта на имплементираните към него [[Метод (програмиране)|методи]], можем да добавяме нови елементи на която и да е позиция в списъка, да махаме такива, да обхождаме или обръщаме тези елементи и т.н. Използва се в почти всички популярни езици за програмиране под различна абревиатура. В езика [[C Sharp|C#]] е List<T> и с <Т>, означаваме [[тип данни|типа данни]], който може да съдържа даден списък - цели и реални числа, [[низ|символни низове]] и т.н. Примери - List<int>, List<double>, List<string>.

== Какво е линейна структура от данни? ==

[[Структура от данни|Структорите от данни]] са множества от данни, организирани на основата на математически и логически закони. При решаване на различни проблеми, правилният избор на такава, е от голямо значение. Към линейните структори от данни спадат Списъk, [[Стек (структура от данни)|Стек]](Stack) и [[Опашка (програмиране)|Опашка]](Queue).

== Видове списъци ==

=== Статичен списък ===

[[Клас (програмиране)|Класът]] List в C# имплементира статичния списък. Той се представя в паметта като масив, елементите на който може да са заети или свободни. По този начин можем да добавяме нови елементи и това да се осъществява бързо, благодарение на големината на списъка. Когато се запълни последната свободна позиция, при добавяне на нов елемент, списъкът автоматично увеличава дължината си двойно. По този начин можем да добавяме нови и нови елементи, без това да пречи на производителността на нашата програма.

==== Функционалност ====

Чрез класа List<T> можем:

* да ги копираме в друг списък или масив.

* да сортираме или обръщаме елементи.

Създаване на нов обект от тип List в езика C# и обработка посредством някои негови методи:

<syntaxhighlight lang=CSharp>

}

}

</syntaxhighlight>

 

=== Свързан списък ===

Свързаният списък е набор от елементи, за които се знае първият от тях и в този набор, всеки следващ елемент, освен вида и стойността си, пази и [[Променлива (програмиране)|променлива]](указател), която сочи към следващия елемент в колекцията. И така с всеки останал обект в свързания списък. Указателят на последния елемент има стойност null, а елементите в свързаният списък могат да се обхождат само от началото към края, за разлика от двойно-свързаните списъци, където се съхранява още една променлива - едната сочи към адреса на следващия, а другата, към адреса на предишния елемент. Така е възможно обхождането и в двете посоки. Свързаният списък се имплементира в езика C# чрез класа LinkedList<T>.

==== Примерна имплементация чрез езика C# ====

Създаваме собствен клас DynamicList и вътрешно в него(private), ще е необходим втори клас - Node. Той ще съдържа указателя към следващия елемент и поле за обекта, който пази.

Създаваме си три полета:

* head - указател към началния елемент.

}

</syntaxhighlight>

Да разгледаме и метода Изтриване(Remove).

Проверява се дали посочения индекс на елемент е верен. Ако не е - се хвърля Изключение(Exception). След това се търси елемента за изтриване и при намирането му се разглеждат три възможни сценария:

* ако count = 0 , значи списъкът е празен (head = null).

}

</syntaxhighlight>

== Източници и допълнителни материали ==

* "Въведение в програмирането със C#" - Светлин Наков, Веселин Колев и колектив