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

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

Якщо в списку після останнього елемента йде перший, то такий список називається кільцевим двобічно зв'язаним списком. Тобто, поле 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).

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

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

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

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

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

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)

Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її.