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

Структорите от данни са множества от данни, организирани на основата на математически и логически закони. При решаване на различни проблеми, правилният избор на такава, е от голямо значение. Към линейните структори от данни спадат списъците,Стек(Stack) и опашките(Queue (abstract data type)).

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

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

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

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

using System;
using System.Collections.Generic;
using System.Linq;

class List
{
    static void Main()
    {
        List<int> myList = new List<int>();
        myList.Add(5);
        myList.Add(1);
        myList.Add(8);
        myList.Add(-7);
        myList.RemoveAt(1);

        Console.WriteLine("Elements in myList is: ");
        for (int i = 0; i < myList.Count; i++)
        {
            Console.Write(myList[i] + " ");
        }
        Console.WriteLine();

        Console.WriteLine("Sort myList is: ");
        myList.Sort();
        for (int i = 0; i < myList.Count; i++)
        {
            Console.Write(myList[i] + " ");
        }
        Console.WriteLine();

        Console.WriteLine("Reverse myList is:");
        myList.Reverse();
        for (int i = 0; i < myList.Count; i++)
        {
            Console.Write(myList[i] + " ");
        }

        // Output
        // Elements in myList is:
        // 5 8 -7
        // Sort myList is:
        // -7 5 8
        // Reverse myList is:
        // 8 5 -7 Press any key to continue . . .
    }
}

Предимства и недостатъци: Плюсът на списъка е, че, както вече споменахме, може да се оразмерява и търсенето на елементите в него е сравнителна бърза операция. За разлика от това, самото добавяне или премахване на елементите работи доста по-бавно, особено, когато тези елементите не са в началото или края на списъка. За да се подобри ефективността на тези операции служи Свързания списък.

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

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

• head - указател към началния елемент.
• tail - указател към последния елемент.
• count - брояч на елементите.

using System;

public class DynamicList
{
    private class Node
    {
        private object element;
        private Node next;

        public object Element
        {
            get { return element; }
            set { element = value; }
        }

        public Node Next
        {
            get { return next; }
            set { next = value; }
        }

        public Node(object element, Node prevNode)
        {
            this.element = element;
            prevNode.next = this;
        }

        public Node(object element)
        {
            this.element = element;
            next = null;
        }
    }
    private Node head;
    private Node tail;
    private int count;

Декларираме полетата чрез конструктор. Списъкът е празен в момента и затова head и tail имат стойност null, а count = 0.

    public DynamicList()
    {
        this.head = null;
        this.tail = null;
        this.count = 0;
    }

Имплементация на операцията Добавяне(Add). Разглеждайки двата варианта за стойност на списъка(празен или не), добавяме нов елемент в края на редицата и по този начин декларираните полета, вече имат конкретни стойности.

    public void Add(object item)
    {
        if (head == null)
        {
            // We have empty list
            head = new Node(item);
            tail = head;
        }
        else
        {
            // We have non-empty list
            Node newNode = new Node(item, tail);
            tail = newNode;
        }
        count++;
    }

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

• ако count = 0 , значи списъкът е празен (head = null).
• ако елементът е в началото на списъка - правим head да сочи към елемента веднага след изтрития (или в частност към null, ако няма такъв).
• ако елементът е в средата или в края на списъка - насочваме елемента преди него да сочи към елемента след него (или в частност към null, ако няма следващ).

    public object Remove(int index)
    {
        if (index >= count || index < 0)
        {
            throw new ArgumentOutOfRangeException("Invalid index: " + index); 
        }

        // Find the element at the specified index
        int currentIndex = 0;
        Node currentNode = head;
        Node prevNode = null;
        while (currentIndex < index)
        {
            prevNode = currentNode;
            currentNode = currentNode.Next;
            currentIndex++;
        }

        // Remove the element
        count--;
        if (count == 0)
        {
            head = null;
        }
        else if (prevNode == null)
        {
            head = currentNode.Next;
        }
        else
        {
            prevNode.Next = currentNode.Next;
        }

        // Find last element
        Node lastElement = null;
        if (this.head != null)
        {
            lastElement = this.head;
            while (lastElement.Next != null)
            {
                lastElement = lastElement.Next;
            }
        }
        tail = lastElement;
        return currentNode.Element;
    }

• "Въведение в програмирането със C#" - Светлин Наков, Веселин Колев и колектив
• Telerik Academy Videos - http://www.youtube.com/watch?v=C_7LzkN1e1Q
• MSDN Library - http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx
• MSDN Library - http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx