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

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

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

Файл:Рис.1 Двозв'язковий список у графічному виляді2.png

Рис.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 Додавання нового значення1.png

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

---

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

Файл:Рис 3. Додавання нових значень1.png

Рис 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. Виштовхування елементу.1.png

рис 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.(англ.)
• Двобічно зв'язні списки(рос.)