Двобічно зв'язаний список
Двобічно зв'язаний список — вид зв'язаного списку, у якому посилання в кожному вузлі вказують на попередній і на подальший вузол у списку.
Вузол двобічно зв'язаного списку складається з трьох полів: вказівника на попередній елемент prev, поля даних data та вказівника next на наступний елемент.
Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку.
По двобічно зв'язаному списку можна пересуватися в будь-якому напрямку — як від початку до кінця, так і навпаки. Для нього простіше проводити видалення і перестановку елементів, оскільки завжди відомі адреси тих елементів списку, вказівник яких спрямований на змінюваний елемент.
Переваги двобічно зв'язаного списку над однобічно зв'язаним списком
ред.- Додавання нового вузла в певну позицію.
- Видалення i-го елемента з послідовності.
- Перегляд списку в обох напрямках.
Існують і недоліки: з'являється додаткова змінна — вказівник на попередній елемент (prev). У даній статті описаний принцип роботи двобічно зв'язного циклічного списку. Єдина відмінність двобічно зв'язного циклічного списку від двобічно зв'язного списку в тому, що останній елемент указує на перший, а перший — на останній. Дана відмінність дає змогу виключати перевірки на «перший» і «останній» елемент. Двобічно зв'язаний циклічний список (далі просто Двобічно зв'язаний список) візуально можна представити в наступному вигляді (рис.1):
Стандартні функції для двобічно зв'язного списку
ред.Функція push (додати новий елемент в i-ту позицію списку). Вона виконує наступні дії:
- Створює новий елемент.
- Копіює значення інформаційного поля.
- Якщо даний елемент є єдиним:
- Обидва покажчики (next і prev) посилаються на цей елемент (рис. 2).
- Покажчик first вказує на єдиний елемент у списку.
- Інакше зсувається покажчик на i-й елемент і додається новий елемент перед i-м.
Додати нове значення у двобічно зв'язний список (push 4), новий елемент додаватиметься після першого. Після операції push список міститиме один елемент (рис. 2).
Додавши ще кілька значень (push 6 і push 7), кожен новий елемент буде додаватися після першого. Список міститиме три елементи (рис. 3) у такій послідовності:
Функція pop виштовхує i-й елемент зі списку. Вона виконує наступні дії:
- Якщо список порожній, вихід із функції.
- Якщо в список містить єдиний елемент:
- Копіюється значення інформаційного поля.
- Видаляється елемент зі списку.
- Присвоюється заголовку пусто.
- Інакше — зсувається покажчик на i-й елемент;
- якщо заголовок вказує на i-й елемент (first == t), тоді переміщається заголовок на наступний елемент (First = t-> next)
- копіюється значення інформаційного поля;
- видаляється i-й елемент зі списку.
- Повертається значення інформаційного поля.
Виконавши функцію pop над лінійним списком (виштовхується 3-й елемент). Отримується наступний стан зв'язного списку (рис. 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 с. — ISBN 0-201-89683-4.(англ.)
- Двобічно зв'язні списки(рос.)
| Цю статтю треба вікіфікувати для відповідності стандартам якості Вікіпедії. (лютий 2017) |
 | Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її. |