Списък (абстрактен тип данни)

Вижте пояснителната страница за други значения на Списък.

---

Списъкът е линейна структура от данни от данни, която съдържа редица от елементи. Различава се от масива по това, че предлага само последователен достъп до елементите. Всеки списък има дължина (брой елементи) и елементите му са наредени последователно. Възможно е добавянето на нов елемент на което и да е място в списъка, премахването на елемент, обхождането на списъка, обръщането на реда на елементите и т.н.

В известните езици за програмиране има различни начини за деклариране на списъци. В езика C# списък се декларира така: List<T> (където <Т> е базовият тип на списъка).

Примери:

• List<int> е тип списък от цели числа.
• List<double> е тип списък от реални числа.
• List<string> е тип списък от низове.

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

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

Статичен списък - капацитет

Класът 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>.

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

Създаваме собствен клас 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#. Велико Търново, Фабер, 2011. ISBN 978-954-400-527-6
• Telerik Academy Videos
• MSDN Library
• MSDN Library