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


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


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

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

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

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

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

Це відмінний спосіб зберігати дані. Більшість мов програмування дозволяють так чи інакше виділити пам’ять у вигляді масиву і оперувати його вмістом. Послідовне зберігання даних збільшує продуктивність (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){ // ... обробити дані.}

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

Крім того, з цього коду можна побачити, що наш список прийматиме параметр типу і реалізовувати інтерфейс 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"

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

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