Визначення списку
Лінійний список - це скінченна послідовність однотипних елементів (вузлів). Кількість елементів у цій послідовності називається довжиною списку.
Наприклад :
F=(1,2,3,4,5,6) - лінійний список, його довжина 6.
Лінійні списки підтримують випадковий доступ до будь-якого елементу так же, як і масиви. Так же, як і в масивах, у лінійних списках можна зберігати однакові елементи.
Основна відмінність між списками і масивами полягає в тому, що списки передбачають можливість зміни кількості елементів в процесі виконання програми, а масиви – як правило, ні. Однак деякі мови програмування підтримують динамічні масиви, тобто такі, які дозволяють змінювати кількість елементів у масиві. Мова C# не підтримує динамічні масиви.
7.2. Види списків: незалежні списки, однозв’язані списки; двозв’язані списки; кільцеві списки; упорядковані списки
Незалежні списки максимально схожі до масивів, оскільки містять елементи одного типу, що ніяким чином не пов’язані між собою, а також дозволяють довільний доступ до своїх елементів.
Реалізація незалежних списків часто здійснюється на основі масиву – тобто сховищем даних для списку виступає масив.
Зв’язаний список – різновид лінійного списку, у якому всі елементи зв’язані між собою посиланнями. Розглядають односпрямовані (однобічно зв’язані), двоспрямовані (двобічно зв’язані), а також кільцеві списки.
Перевага зв’язаних списків у порівнянні з масивами полягає в тому, що операція включення та виключення елементу зі списку не залежить від розміру списку, недолік – безпосередній доступ до будь-якого елементу списку не передбачений і потребує перебору усіх елементів списку, які передують потрібному.
Крім того, в списках також не існує проблеми "розширення", яка рано чи пізно виникає в масивах фіксованого розміру, коли виникає необхідність включити в нього додаткові елементи. Точно так, фіксований масив, з якого було видалено багато елементів (або вони просто не використовуються) є дуже неефективним з точки зору використання пам'яті. Функціонування списків можливо в ситуації, коли пам'ять комп'ютера фрагментована, тоді як масиви переважно потребують неперервної області для зберігання. Іншим очевидним недоліком списків є необхідність разом з корисною інформацією додаткового збереження інформації про вказівники, що позначається на ефективності використання пам'яті цими структурами.
Однобічно зв’язаний список представлений на рисунку.
Двобічно зв’язаний список представлений на рисунку.
Двобічне зв'язування потребує більше пам'яті на елемент та більших обчислювальних затрат на виконання елементарних операцій. Але такими списками легше маніпулювати, тому що вони дозволяють проходження по списку в обох напрямах, що є необхідною умовою функціонування деяких алгоритмів.
7.3. Основні операції над списками: включення елементу до списку; видалення елементу; перехід між елементами; ітератор для списку
Лінійні списки мають підтримувати мінімум чотири обов’язкові операції:
– отримання n-го елемента списку для читання чи запису в нього нового значення;
– додавання нового елемента в будь-яку позицію в списку;
– видалення елемента списку;
– визначення довжини (розміру) списку.
Крім того, списки можуть підтримувати наступні операції:
– об'єднання в одному списку двох або більше лінійних списків;
– розбиття списку на два або більше фрагментів;
– створення копії списку;
– визначення кількості елементів в списку;
– сортування елементів списку;
– пошук елемента, що задовольняє певним критеріям.
В залежності від конкретних проблем, які вирішуються шляхом створення лінійного списку, можлива підтримка інших операцій.
Операція включення до списку
Розглянемо приклад створення незалежного списку на основі масиву.
Спочатку задекларуємо клас ListOfNumbers:
using System;
class ListOfNumbers
{
public ListOfNumbers()
{
}
}
Потім передбачимо змінну для збереження списку:
using System;
class ListOfNumbers
{
private double[] Item = new double[20];
public ListOfNumbers()
{
}
}
class Exercise
{
static int Main()
{
ListOfNumbers lstNumbers = new ListOfNumbers();
return 0;
}
}
Передбачимо змінну для збереження довжини списку:
class ListOfNumbers
{
private double[] Item = new double[20];
private int size;
public ListOfNumbers()
{
size = 0;
}
}
class ListOfNumbers
{
const int MaxSize = 100;
private double[] Item = new double[MaxSize];
public int size = 0;
public bool Add(double item)
{
if (size < 20)
{
Item[size] = item;
size++;
return true;
}
return false;
}
}
Передбачимо методи для запису елементу до списку і читання елементу зі списку:
using System;
using System.Collections.Generic;
using System.Text;
namespace ArrayBasedList
{
class ListOfNumbers
{
const int MaxSize = 100;
private int[] items = new int[MaxSize];
public int size = 0;
public void Add(int item)
{
if (size < MaxSize)
{
items[size] = item;
size++;
}
else
{
throw new IndexOutOfRangeException();
}
}
public int GetItem(int pos)
{
if (pos >= 0 & pos <= size)
{
return items[pos];
}
throw new IndexOutOfRangeException();
}
}
class Program
{
static void Main(string[] args)
{
ListOfNumbers numList = new ListOfNumbers();
numList.Add(10);
numList.Add(20);
Console.WriteLine("Кількість елементів: {0}", numList.size);
Console.WriteLine("Другий елемент: {0}", numList.GetItem(1));
Console.ReadLine();
}
}
}
Розглянемо приклад створення однобічно зв’язаного лінійного списку.
Розглянемо наступний код.
using System;
using System.Collections.Generic;
using System.Text;
namespace LinkedList
{
class StudentData
{
public string Name = null;
public string Group = null;
}
class ListOfStudents
{
public int size = 0;
}
class Program
{
static void Main(string[] args)
{
}
}
}
Для можливості зв’язування між елементами необхідно внести модифікації до класу StudentData:
class StudentData
{
public string Name;
public string Group;
public StudentData Next;
}
Готовий приклад:
using System;
using System.Collections.Generic;
using System.Text;
namespace LinkedList
{
class StudentData
{
public string Name = null;
public string Group = null;
public StudentData Next = null;
}
class ListOfStudents
{
public int Size = 0;
public StudentData Head = null;
public int Add(StudentData NewItem)
{
StudentData Dummy = new StudentData();
Dummy = NewItem;
Dummy.Next = Head;
Head = Dummy;
return Size++;
}
public StudentData GetItem(int pos)
{
StudentData current = Head;
for (int i = 0; i < pos & current != null; i++)
{
current = current.Next;
}
return current;
}
}
class Program
{
static void Main(string[] args)
{
ListOfStudents students = new ListOfStudents();
StudentData student;
student = new StudentData();
student.Name = "Петров";
student.Group = "ЕК-123";
students.Add(student);
student = new StudentData();
student.Name = "Сидоров";
student.Group = "ОА-456";
students.Add(student);
student = new StudentData();
student.Name = "Шевченко";
student.Group = "БС-987";
students.Add(student);
Console.WriteLine("Кількість елементів списку: {0}", students.Size);
Console.WriteLine("Ім'я першого студенту за списком: {0}", students.GetItem(0).Name);
Console.WriteLine("Ім'я другого студенту за списком: {0}", students.GetItem(1).Name);
Console.WriteLine("Ім'я третього студенту за списком: {0}", students.GetItem(2).Name);
Console.ReadLine();
}
}
}
Результат представлено на рисунку.
Рисунок 7.1 – Результат роботи програми
Операція видалення зі списку є однією з обов’язкових операцій.
Видалення з лінійного списку на основі масиву:
public void Delete(int pos)
{
if (pos >= 0 && pos <= size)
{
for (int i = pos; i < size; i++)
{
items[i] = items[i + 1];
}
size--;
}
else
{
throw new IndexOutOfRangeException();
}
}
Код методу «Main»:
static void Main(string[] args)
{
ListOfNumbers numList = new ListOfNumbers();
numList.Add(10);
numList.Add(20);
numList.Add(30);
Console.WriteLine("Кількість елементів: {0}", numList.size);
Console.WriteLine("Другий елемент: {0}", numList.GetItem(1));
numList.Delete(1);
Console.WriteLine("Кількість елементів: {0}", numList.size);
Console.WriteLine("Другий елемент: {0}", numList.GetItem(1));
Console.ReadLine();
}
Результат виконання програми наведений на рисунку:
Рисунок 7.2 – Результат виконання програми
Розглянемо видалення елементу зі зв’язаного списку.
Метод видалення першого елементу з голови списку:
public void DeleteFirst()
{
if (Head == null)
{
throw new IndexOutOfRangeException();
}
if (Head.Next != null)
{
Head = Head.Next;
}
else
{
Head = null;
}
Size--;
}
Виконання програми після виконання методу представлено на рисунку.
students.DeleteFirst();
Console.WriteLine("Кількість елементів списку: {0}", students.Size);
Console.WriteLine("Ім'я першого студенту за списком: {0}", students.GetItem(0).Name);
Console.WriteLine("Ім'я другого студенту за списком: {0}", students.GetItem(1).Name);
Рисунок 7.3 – Виконання програми
Метод видалення будь-якого елементу зі списку:
public void Delete(int pos)
{
if (this.GetItem(pos) == null)
{
throw new IndexOutOfRangeException();
}
this.GetItem(pos - 1).Next = this.GetItem(pos + 1);
Size--;
}
Виконання програми після виконання методу представлено на рисунку.
students.Delete(1);
Console.WriteLine("Кількість елементів списку: {0}", students.Size);
Console.WriteLine("Ім'я першого студенту за списком: {0}", students.GetItem(0).Name);
Console.WriteLine("Ім'я другого студенту за списком: {0}", students.GetItem(1).Name);
Рисунок 7.4 – Виконання програми
При роботі зі списками та іншими структурами даних, які передбачають повторення однотипних елементів, поширеним є використання ітераторів – спеціального механізму, який дозволяє обходити елементи структури.
Потреба у ітераторах викликана певними обмеженнями повного обходу усіх елементів структури:
– необхідність створення і дублювання власної логіки обходу елементів за умов складної системи визначення необхідних елементів;
– складність видалення елементів, обхід яких здійснюється у традиційному параметризованому циклі.