Двобічно зв'язаний список

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

Вузол двобічно зв'язаного списку складається з трьох полів: вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент.

Рис.1. Кільцевий двобічно зв'язаний список

Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.

По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент.

Переваги двобічно зв'язаного списку над однобічно зв'язаним списком

1. Додавання нового вузла в певну позицію.
2. Видалення i-го елемента з послідовності.
3. Перегляд списку в обох напрямках.

Існують і недоліки: з'являється додаткова змінна — вказівник на попередній елемент (prev). У даній статті описаний принцип роботи двобічно зв'язного циклічного списку. Єдина відмінність двобічно зв'язного циклічного списку від двобічно зв'язного списку в тому, що останній елемент указує на перший, а перший — на останній. Дана відмінність дає змогу виключати перевірки на «перший» і «останній» елемент. Двобічно зв'язаний циклічний список (далі просто Двобічно зв'язаний список) можна представити в наступному вигляді (рис.1):

Стандартні функції для двобічно зв'язного списку

Функція push (додати новий елемент в i-ту позицію списку). Вона виконує наступні дії:

1. Створює новий елемент.
2. Копіює значення інформаційного поля.
3. Якщо даний елемент є єдиним:
   1. Обидва покажчики (next і prev) посилаються на цей елемент (рис. 2).
   2. Покажчик first вказує на єдиний елемент у списку.
4. Інакше зсувається покажчик на i-й елемент і додається новий елемент перед i-м.

---

Додати нове значення у двобічно зв'язний список (push 4), новий елемент додаватиметься після першого. Після операції push список міститиме один елемент (рис. 2).

рис.2 Додавання нового значення

---

Додавши ще кілька значень (push 6 і push 7), кожен новий елемент буде додаватися після першого. Список міститиме три елементи (рис. 3) у такій послідовності:

Рис 3. Додавання нових значень

---

Функція pop виштовхує i-й елемент зі списку. Вона виконує наступні дії:

1. Якщо список порожній, вихід із функції.
2. Якщо в список містить єдиний елемент:
   1. Копіюється значення інформаційного поля.
   2. Видаляється елемент зі списку.
   3. Присвоюється заголовку пусто.
3. Інакше — зсувається покажчик на i-й елемент;
   1. якщо заголовок вказує на i-й елемент (first == t), тоді переміщається заголовок на наступний елемент (First = t-> next)
   2. копіюється значення інформаційного поля;
   3. видаляється i-й елемент зі списку.
4. Повертається значення інформаційного поля.

---

Виконавши функцію pop над лінійним списком (виштовхується 3-й елемент). Отримується наступний стан зв'язного списку (рис. 4).

рис 4. Виштовхування елементу.

Функція print_all пробігає по всіх елементах і виводить в консоль значення інформаційного поля. Перегляд елементів здійснюється зліва направо, але легко можна переписати функцію і змінити перегляд елементів справа наліво (замінити a = a-> next на a = a-> prev). Функція clean видаляє всі елементи в списку і привласнює заголовку пусто (first = null). Після цієї операції список повертається в початковий стан.

Приклад реалізації двобічно зв'язаного списку мовою C#

namespace WikiSamples.LinkedList;  public class LinkedList<T>  where T : IEquatable<T> {  public class Node  {  public Node(T value)  {  Value = value;  }   public Node? Previous { get; set; }   public T Value { get; init; }   public Node? Next { get; set; }  }   private Node? _head = null;  private Node? _tail = null;   public void InsertBefore(Node existingNode, Node newNode)  {  var previousNode = existingNode.Previous;   if (previousNode is not null)  {  previousNode.Next = newNode;  newNode.Previous = previousNode;  }   existingNode.Previous = newNode;  newNode.Next = existingNode;   if (existingNode == _head)  {  _head = newNode;  }  }   public void InsertAfter(Node existingNode, Node newNode)  {  var nextNode = existingNode.Next;   if (nextNode is not null)  {  nextNode.Previous = newNode;  newNode.Next = nextNode;  }   existingNode.Next = newNode;  newNode.Previous = existingNode;   if (existingNode == _tail)  {  _tail = newNode;  }  }   public void InsertFirst(Node newNode)  {  if (_head is null)  {  _head = _tail = newNode;  }  else  {  InsertBefore(_head, newNode);  }  }   public void InsertLast(Node newNode)  {  if (_tail is null)  {  _head = _tail = newNode;  }  else  {  InsertAfter(_tail, newNode);  }  }   /// <summary>  /// Finds the node in the list with time complexity of O(N).  /// </summary>  public Node? Find(T searchedValue)  {  var currentNode = _head;   while (currentNode is not null)  {  if (searchedValue.Equals(currentNode.Value))  {  return currentNode;  }   currentNode = currentNode.Next;  }   return null;  }   public IEnumerable<Node> Iterate()  {  var currentNode = _head;   while (currentNode is not null)  {  yield return currentNode;   currentNode = currentNode.Next;  }  }   /// <summary>  /// Removes the node from the list with time complexity of O(1).  /// </summary>  public void Remove(Node node)  {  var previousNode = node.Previous;  var nextNode = node.Next;   if (previousNode is not null)  {  previousNode.Next = nextNode;  }   if (nextNode is not null)  {  nextNode.Previous = previousNode;  }   if (_head == node)  {  _head = nextNode;  }   if (_tail == node)  {  _tail = previousNode;  }  } } 

Приклад реалізації двобічно зв'язаного списку на С++

Реалізації двобічно зв'язаного списку на С++  

struct List{ char name[30]; List *next; List *prev; }; // List *head; // голова списку // void CreateList(){ // створення списку head = NULL; } // void add_from_the_head(char newname[30]){ // додати з голови List * n = new List; strcpy_s(n->name,newname); if(head == NULL){ head = n; head->next = NULL; } else{ n->next = head; head->prev = n; head = n; } } // void add_from_the_tail(char newname[30]){ // добавити з хвоста List *n = new List; strcpy_s(n->name,newname); if(head == NULL){ head = n; head->next = NULL; } else{ n->next = head; while(n->next != NULL) n = n->next; List * nova = new List; strcpy_s(nova->name,newname); n->next = nova; nova->prev = n; nova->next = NULL; } } // bool add_after(char after[30]){ // добавити після якогось елемента char newname[30]; List *n = head; while(n != NULL){ if(strcmp(n->name,after) == 0){ cout << after << " Знайдено!" << endl; cout <<"Введіть ім'я, що потрібно додати: "<<endl; cin >> newname; List * list = new List; list->next = n->next; n->next = list; list->prev = n; strcpy_s(list->name,newname); return true; } n = n->next; } cout<<"Не знайдено нікого!"<<endl; return false; } // void Udalit(char smbdy[30]){ // видалення елемента if(head == NULL){ perror("Список порожній!"); } else{ List * n = head; while(strcmp(head->name,smbdy)==0){ head = head->next; } List * pr; n = head; if(n!=NULL){ while(n->next!=NULL){ if(strcmp(n->next->name,smbdy)==0){ pr = n->next->next; delete n->next; n->next = pr; pr->prev = n; } if((n->next!=NULL) && (strcmp(n->next->name,smbdy)!=0)) n = n->next; } } } } // void print_all(){ // друкування елемента int counter = 1; List * n = head; if(n==NULL) perror("Список порожній!"); while(n!=NULL){ cout << counter <<". "<<n->name << endl; n = n->next; counter++; } } // void search(char * name){ // пошук по категорії «ім'я» елемента int counter = 1; List * n = head; while(n!=NULL){ if(strcmp(n->name,name)==0){ cout << counter <<". "<<n->name << endl; counter++; } n = n->next; } if(counter == 1) cout << "Не знайдено нікого!" <<endl; } // 

Джерела

• Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — .(англ.)