Алгоритми і структури даних для початківців: зв’язний список


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Перша структура даних, яку ми розглянемо, – зв’язний список. На те є дві причини: перше – зв’язний список використовується практично скрізь – від ОС до ігор, і друге – на його основі будується безліч інших структур даних.


Також дивиться інші матеріали цієї серії: бінарне дерево, стеки і черги, динамічний масив, оцінка складності алгоритму, сортування і множини.

Зв’язний список

Основне призначення зв’язного списку – надання механізму для зберігання і доступу до довільної кількості даних. Як випливає з назви, це досягається зв’язуванням даних разом у список.

До того як ми перейдемо до розгляду зв’язного списку, давайте згадаємо, як зберігаються дані в масиві.

Як показано на рисунку, дані в масиві зберігаються у безперервній ділянці пам’яті, розділеній на осередки певного розміру. Доступ до даних в осередках здійснюється за посиланням на їх розташування – індекс.

Це відмінний спосіб зберігати дані. Більшість мов програмування дозволяють так чи інакше виділити пам’ять у вигляді масиву і оперувати його вмістом. Послідовне зберігання даних збільшує продуктивність (data locality), дозволяє легко ітерируватися за вмістом і діставати доступ до довільного елемента за індексом.

Проте іноді масив – не є найбільше відповідною структурою.

Припустимо, що у нашої програми є вимоги:

  • Прочитати деяку кількість цілих чисел із джерела (метод NextValue), поки не зустрінеться число 0xffff.
  • Передати зчитані числа в метод ProcessItems

Оскільки у вимогах вказано, що зчитані числа передаються в метод ProcessItems за один раз, очевидним рішення буде масив цілих чисел:

void LoadData (){ // Припустимо, що елементів буде не більше 20 int[] values = new int[20]; for (int i = 0; i < values.Length; i++) { if (values[i] == 0xffff) { break; } values[i] = NextValue (); } ProcessItems (values);}void ProcessItems (int[] values){ // ... обробити дані.}

У цього рішення є ряд проблем, але найочевидніша з них – що станеться, якщо буде необхідно прочитати більше 20 значень? У цій реалізації значення з 21 і далі просто проігноруються. Можна виділити більше пам’яті – 200 або 2000 елементів. Можна дати користувачеві можливість вибрати розмір масиву. Чи виділити пам’ять під новий масив більшого розміру при заповненні старого і скопіювати елементи. Але ці рішення ускладнюють код і марно витрачають пам’ять.

Нам потрібна колекція, яка дозволяє додати довільне число елементів і перебрати їх в порядку додавання. Розмір колекції має бути необмеженим, а довільний доступ нам не потрібний. Нам потрібний зв’язний список.

Щоб перейти до його реалізації, спершу давайте подивимося на те, як могло б виглядати розв’язання нашої задачі.

static void LoadItems (){ LinkedList list = new LinkedList (); while (true) { int value = NextValue (); if (value != 0xffff) { list.Add (value); } else { break; } } ProcessItems (list);}static void ProcessItems (LinkedList list){ // ... обробити дані.}

Зверніть увагу: проблем, властивих першому варіанту рішення більше немає, – ми не можемо виділити недостатньо або, навпаки, надто багато пам’яті під масив.

Крім того, з цього коду можна побачити, що наш список прийматиме параметр типу <T> і реалізовувати інтерфейс IEnumerable

Реалізація класу LinkedList

Клас Node

В основі зв’язного списку лежить поняття вузла, або елемента (Node). Вузол – це контейнер, який дозволяє зберігати дані й отримувати наступний вузол.

У найпростішому випадку клас Node можна реалізувати так:

public class Node{ public int Value { get; set; } public Node Next { get; set; }}

Тепер ми можемо створити примітивний зв’язний список. Виділимо пам’ять під три вузли (first, middle, last) і з’єднаємо їх послідовно:

// +-----+------+// | 3 | null +// +-----+------+Node first = new Node { Value = 3 };// +-----+------+ +-----+------+// | 3 | null + | 5 | null +// +-----+------+ +-----+------+Node middle = new Node { Value = 5 };// +-----+------+ +-----+------+// | 3 | *---+--->| 5 | null +// +-----+------+ +-----+------+first.Next = middle;// +-----+------+ +-----+------+ +-----+------+// | 3 | *---+--->| 5 | null + | 7 | null +// +-----+------+ +-----+------+ +-----+------+Node last = new Node { Value = 7 };// +-----+------+ +-----+------+ +-----+------+// | 3 | *---+--->| 5 | *---+-->| 7 | null +
// +-----+------+ +-----+------+ +-----+------+middle.Next = last;

Тепер у нас є список з трьох елементів, починаючи з first і закінчуючи last. Поле Next останнього вузла має значення null, що показує: це останній елемент. З даним списком вже можна робити різні операції. Наприклад, надрукувати дані з кожного елемента:

private static void PrintList (Node node){ while (node != null) { Console.WriteLine (node.Value); node = node.Next; }}

Метод PrintList ітерирується за елементами списку: друкує значення поля Value і переходить до наступного вузла за посиланням в полі Next.

Тепер, коли ми знаємо, як повинен виглядати вузол зв’язного списку, давайте подивимося на приклад реалізації класу LinkedListNode.

public class LinkedListNode{ /// /// Конструктор нового вузла зі значенням Value. /// public LinkedListNode (T value) { Value = value; } /// /// Полі Value. /// public T Value { get; internal set; } /// /// Посилання на наступний вузол списку (якщо вузол останній, то null). /// public LinkedListNode Next { get; internal set; }}

Клас LinkedList

До того як реалізовувати наш зв’язний список, треба зрозуміти, як ми з ним працюватимемо.

Раніше ми побачили, що колекція повинна підтримувати будь-який тип даних, тобто нам треба реалізувати узагальнений інтерфейс.

Оскільки ми використовуємо платформу .NET, має сенс реалізувати наш клас так, щоб його поведінка була схожа на поведінку вбудованих колекцій. Найпростіший спосіб зробити це – реалізувати інтерфейс ICollection. Зверніть увагу, що ми реалізуємо ICollection, а не Ilist, оскільки інтерфейс Ilist дозволяє діставати доступ до елементів за індексом. Попри те, що довільний доступ до елементів у цілому корисний, його неможливо ефективно реалізувати в зв’язному списку.

Враховуючи усе вищесказане, давайте складемо зразковий план класу, а потім заповнимо методи, яких бракує.

public class LinkedList: System.Collections.Generic.ICollection{ public void Add (T item) { throw new System.NotImplementedException (); }
public void Clear (){ throw new System.NotImplementedException (); } public bool Contains (T item) { throw new System.NotImplementedException (); } public void CopyTo (T[] array, int arrayIndex) { throw new System.NotImplementedException (); } public int Count { get; private set; } public bool IsReadOnly { get { throw new System.NotImplementedException (); } } public bool Remove (T item) { throw new System.NotImplementedException (); } public System.Collections.Generic.IEnumerator GetEnumerator (){ throw new System.NotImplementedException (); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator (){ throw new System.NotImplementedException (); }}

Метод Add

  • Поведінка: додає елемент у кінець списку.
  • Складність: O (1)

Додавання елемента в зв’язний список робиться в три етапи:

  1. Створити екземпляр класу LinkedListNode.
  2. Знайти останній вузол списку.
  3. Встановити значення поля Next останнього вузла списку так, щоб воно вказувало на створений вузол.

Основна складність полягає в тому, щоб знайти останній вузол списку. Можна зробити це двома способами. Перший – зберігати покажчик на перший вузол списку і перебирати вузли, поки не дійдемо до останнього. В цьому випадку нам не потрібно зберігати покажчик на останній вузол, що дозволяє використати менше пам’яті (залежно від розміру покажчика на Вашій платформі), але вимагає проходу за всім списком при кожному додаванні вузла. Це означає, що метод Add займе O (n) часу.

Другий метод полягає у збереженні покажчика на останній вузол списку, і тоді при додаванні нового вузла ми поміняємо покажчик так, щоб він вказував на новий вузол. Цей спосіб прийнятніший, оскільки виконується за O (1) часу.

Перше, що нам необхідно зробити, – додати два приватні поля в клас LinkedList: посилання на перший (head) і останній (tail) вузли.

private LinkedListNode_head;private LinkedListNode_tail;

Тепер ми можемо додати метод, який виконує три необхідні кроки.

public void Add (T value){ LinkedListNode node = new LinkedListNode (value); if (_ head == null) {_head = node;_tail = node; } else {_tail.Next = node;_tail = node; } Count++;
}

Спочатку ми створюємо екземпляр класу LinkedListNode. Потім перевіряємо, чи є список порожнім. Якщо список порожній, ми просто встановлюємо значення полів _ head і _ tail так, щоб вони вказували на новий вузол. Цей вузол в даному випадку буде одночасно і першим, і останнім у списку. Якщо список не порожній, вузол додається в кінець списку, а поле _ tail тепер вказує на новий кінець списку.

Поле Count інкрементується при додаванні вузла для того, щоб зберігався контракт інтерфейсу ICollection. Поле Count повертає точну кількість елементів списку.

Метод Remove

  • Поведінка: видаляє перший елемент списку зі значенням, що дорівнює переданому. Повертає true, якщо елемент був видалений і false інакше.
  • Складність: O (n)

До того як розбирати метод Remove, давайте подивимося, чого ми хочемо добитися. На наступному рисунку список з чотирма елементами. Ми видаляємо елемент зі значенням “3”.

Після видалення вузла поле Next вузла зі значенням “2” вказуватиме на вузол зі значенням “4”.

Основний алгоритм видалення елемента такий:

  1. Знайти вузол, який необхідно видалити.
  2. Змінити значення поля Next попереднього вузла так, щоб воно вказувало на вузол, що йде за тим, який видаляється.

Як завжди, основна проблема криється в дрібницях. Ось випадки, які необхідно передбачити:

  • Список може бути порожнім, або значення, яке ми передаємо в метод може не бути в списку. У цьому випадку список залишиться без змін.
  • Вузол, що видаляється, може бути єдиним у списку. В цьому випадку ми встановимо значення полів _ head і _ tail , що дорівнює null.
  • Вузол, що видаляється, буде на початку списку. В цьому випадку ми записуємо в _ head посилання на наступний вузол.
  • Вузол, що видаляється, буде в середині списку.
  • Вузол, що видаляється, буде в кінці списку. В цьому випадку ми записуємо в _ tail посилання на передостанній вузол, а в його полі Next записуємо null.
public bool Remove (T item){ LinkedListNode previous = null; LinkedListNode current =_head; // 1: Порожній список: нічого не робити.
// 2: Один елемент: встановити Previous = null. // 3: Декілька елементів: // a: елемент, що Видаляється, перший. // b: елемент, що Видаляється, в середині або кінці. while (current != null) { if (current.Value.Equals (item)) { // Вузол в середині або у кінці. if (previous != null) { // Випадок 3b. // До: Head -> 3 -> 5 -> null // Після: Head -> 3 ------> null previous.Next = current.Next; // Якщо у кінці, то міняємо_tail. if (current.Next == null) {_tail = previous; } } else { // Випадок 2 або 3a. // До: Head -> 3 -> 5 // Після: Head ------> 5 // Head -> 3 -> null
// Head ------> null_head =_head.Next; // Список тепер порожній? if (_ head == null) {_tail = null; } } Count--; return true; } previous = current; current = current.Next; } return false;}

Полі Count декрементується при видаленні вузла.

Метод Contains

  • Поведінка: повертає true чи false залежно від того, чи є елемент, який ми шукаємо, у списку.
  • Складність: O (n)

Метод Contains простий. Він переглядає кожен елемент списку, від першого до останнього, і повертає true як тільки знайде вузол, чиє значення дорівнює переданому параметру. Якщо такий вузол не знайдений, і метод дійшов до кінця списку, то повертається false.

public bool Contains (T item){ LinkedListNode current =_head; while (current != null) { if (current.Value.Equals (item)) { return true; } current = current.Next; } return false;}

Метод GetEnumerator

  • Поведінка: повертає екземпляр IEnumerator, який дозволяє ітерируватися за елементами списку.
  • Складність: отримання ітератора – O (1). Прохід всіма елементами – O (n).

Повернений ітератор проходить за всім списком від першого до останнього вузла і повертає значення кожного елемента за допомогою ключового слова yield.

IEnumerator IEnumerable.GetEnumerator (){ LinkedListNode current =_head; while (current != null) { yield return current.Value; current = current.Next; }}IEnumerator IEnumerable.GetEnumerator (){ return ((IEnumerable)this).GetEnumerator ();}

Метод Clear

  • Поведінка: видаляє всі елементи зі списку.
  • Складність: O (1)

Метод Clear просто встановлює значення полів _ head і _ tail , які дорівнюють null. Оскільки C# – мова з автоматичним управлінням пам’яттю, немає необхідності явно видаляти невживані вузли. Клієнт, який викликає метод, повинен переконатися в коректному видаленні значень вузлів, якщо це необхідно.

public void Clear (){_head = null;_tail = null; Count = 0;}

Метод CopyTo

  • Поведінка: копіює вміст списку у вказаний масив, починаючи зі вказаного індексу.
  • Складність: O (n)

Метод CopyTo проходить за списком і копіює елементи в масив за допомогою привласнення. Клієнт, який викликає метод повинен переконатися, що масив має достатній розмір для того, щоб вмістити всі елементи списку.

public void CopyTo (T[] array, int arrayIndex){ LinkedListNode current =_head; while (current != null) { array[arrayIndex++] = current.Value; current = current.Next; }}

Метод Count

  • Поведінка: повертає кількість елементів списку. Повертає 0, якщо список порожній.
  • Складність: O (1)

Count – поле з публічним гетером і приватним сетером. Зміна його значення здійснюється в методах Add, Remove і Clear.

public int Count{ get; private set;}

Метод IsReadOnly

  • Поведінка: повертає false, якщо список тільки для читання.
  • Складність: O (1)
public bool IsReadOnly{ get { return false; }}

Двозв’язний список

Зв’язний список, який ми щойно створили, називається також “однозв’язним”. Це означає, що між вузлами тільки один зв’язок в єдиному напрямі від першого вузла до останнього. Є також поширений варіант списку, який надає доступ до обох кінців, – двозв’язковий список.

Для того щоб створити двозв’язний список, ми повинні додати в клас LinkedListNode поле Previous, яке утримуватиме посилання на попередньому елементі списку.

Далі ми розглянемо тільки відмінності в реалізації одинозв’язного і двозв’язного списку.

Клас Node

Єдина зміна, яку потрібно внести в клас LinkedListNode – додати поле з посиланням на попередній вузол.

public class LinkedListNode{ /// /// Конструктор нового вузла зі значенням Value. /// /// public LinkedListNode (T value) { Value = value; } /// /// Полі Value. /// public T Value { get; internal set; } /// /// Посилання на наступний вузол списку (якщо вузол останній, то null). /// public LinkedListNode Next { get; internal set; } /// /// Посилання на попередній вузол списку (якщо вузол перший, то null). /// public LinkedListNode Previous { get; internal set; }}

Метод AddFirst

В той час як однозв’язний список дозволяє додавати елементи тільки в кінець, використовуючи двозв’язний список ми можемо додавати елементи як в початок, так і в кінець, за допомогою методів AddFirst і AddLast відповідно. Метод ICollection.Add викликатиме AddLast для сумісності з одинзв’язним списком.

  • Поведінка: додає переданий елемент в початок списку.
  • Складність: O (1)

При додаванні елементу в початок списку послідовність дій майже така сама, як і при додаванні елемента в одинозв’язний список.

  1. Встановити значення поля Next у новому вузлі так, щоб воно вказувало на колишній перший вузол.
  2. Встановити значення поля Previous у колишньому першому вузлі так, щоб воно вказувало на новий вузол.
  3. Оновити поле _ tail за необхідності інкрементувати поле Count
public void AddFirst (T value){ LinkedListNode node = new LinkedListNode (value); // Зберігаємо посилання на перший елемент. LinkedListNode temp =_head; //_head вказує на новий вузол._head = node; // Вставляємо список позаду першого елементу._head.Next = temp; if (Count == 0) { // Якщо список був порожній, то head and tail повинні // вказувати на новій вузол._tail =_head; } else { // До: head -------> 5 7 -> null // Після: head -> 3 5 7 -> null temp.Previous =_head; } Count++;}

Метод AddLast

  • Поведінка: додає переданий елемент в кінець списку.
  • Складність: O (1)

Додавання вузла в кінець списку виконати легше, ніж у початок. Ми просто створюємо новий вузол і оновлюємо поля _ head і _ tail, а потім інкрементуємо поле Count.

public void AddLast (T value){ LinkedListNode node = new LinkedListNode (value); if (Count == 0) {_head = node; } else {_tail.Next = node; // До: Head -> 3 5 -> null // Після: Head -> 3 5 7 -> null // 7.Previous = 5 node.Previous =_tail; }_tail = node; Count++;}

Як було сказано вище, ICollection.Add просто кличе AddLast.

public void Add (T value){ AddLast (value);}

Метод RemoveFirst

Як і метод Add, Remove буде розділений на два методи, що дозволяють видаляти елементи з початку і з кінця списку. Метод ICollection.Remove також видалятиме елементи з початку, але тепер ще оновлюватиме поля Previous у тих вузлах, де це необхідно.

  • Поведінка: видаляє перший елемент списку. Якщо список порожній, не робить нічого. Повертає true, якщо елемент був видалений і false інакше.
  • Складність: O (1)

RemoveFirst встановлює посилання head на другий вузол списку і обнуляє поле Previous цього вузла, видаляючи в такий спосіб усі посилання на попередній перший вузол. Якщо список був порожній або містив тільки один елемент, то поля _ head і _ tail дорівнюють null.

public void RemoveFirst (){ if (Count != 0) { // До: Head -> 3 5 // Після: Head -------> 5 // Head -> 3 -> null // Head ------> null_head =_head.Next; Count--; if (Count == 0) {_tail = null; } else { // 5.Previous було 3; тепер null._head.Previous = null; } }}

Метод RemoveLast

  • Поведінка: видаляє останній елемент списку. Якщо список порожній, не робить нічого. Повертає true, якщо елемент був видалений і false інакше.
  • Складність: O (1)

RemoveLast встановлює значення поля _ tail так, щоб воно вказувало на передостанній елемент списку і видаляє останній елемент. Якщо список був порожнім, або містив тільки один елемент, то поля _ head і _ tail дорівнюють null.

public void RemoveLast (){ if (Count != 0) { if (Count == 1) {_head = null;_tail = null; } else { // До: Head --> 3 --> 5 --> 7 // Tail = 7 // Після: Head --> 3 --> 5 --> null // Tail = 5 // Обнуляємо 5.Next_tail.Previous.Next = null;_tail =_tail.Previous; } Count--; }}

Метод Remove

  • Поведінка: видаляє перший елемент списку зі значенням, що дорівнює переданому. Повертає true, якщо елемент був видалений і false , якщо ні.
  • Складність: O (n)

Метод ICollection.Remove () майже такий самий, як і в однозв’язному списку. Єдина відмінність – тепер нам необхідно поміняти значення поля Previous при видаленні вузла. Для того щоб не повторювати код, цей метод кличе RemoveFirst при видаленні першого вузла.

public bool Remove (T item){ LinkedListNode previous = null; LinkedListNode current =_head; // 1: Порожній список: нічого не робити. // 2: Один елемент: встановити Previous = null. // 3: Декілька елементів: // a: елемент, що Видаляється, перший. // b: елемент, що Видаляється, в середині або кінці.
while (current != null) { // Head -> 3 -> 5 -> 7 -> null // Head -> 3 ------> 7 -> null if (current.Value.Equals (item)) { // Вузол в середині або у кінці. if (previous != null) { // Випадок 3b. previous.Next = current.Next; // Якщо у кінці, то міняємо_tail. if (current.Next == null) {_tail = previous; } else { // До: Head -> 3 5 7 -> null // Після: Head -> 3 7 -> null // previous = 3 // current = 5 // current.Next = 7 // Означає... 7.Previous = 3 current.Next.Previous = previous; }
Count--; } else { // Випадок 2 або 3a. RemoveFirst (); } return true; } previous = current; current = current.Next; } return false;}

Навіщо потрібний двозв’язний список?

Отже, ми можемо додавати елементи в початок списку і в його кінець. Що нам це дає? У тому вигляді, в якому він реалізований зараз, немає особливих переваг перед звичайним однозв’язним списком. Але якщо додати гетери для полів head і tail, користувач нашого списку зможе реалізувати множину різних алгоритмів.

public LinkedListNode Head{ get { return_head; }}public LinkedListNode Tail{ get { return_tail; }}

Так ми зможемо ітерируватися за списком вручну, у тому числі від останнього елемента до першого.

У даному прикладі ми використовуємо поля Tail і Previous для того, щоб обійти список задом наперед.

public void ProcessListBackwards (){ LinkedList list = new LinkedList (); PopulateList (list); LinkedListNode current = list.Tail; while (current != null) { ProcessNode (current); current = current.Previous; }}

Крім того, двозв’язний список дозволяє легко реалізувати двозв’язну чергу, яка є будівельним блоком для інших структур даних. Ми повернемося до неї пізніше, у відповідній частині.

Далі буде

На цьому ми закінчуємо розбір зв’язних списків. Наступного разу детально розберемо будову векторів (array list).

Переклад статті “The Linked List”

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Trends: передостанні елементи списку

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *