Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Список - структура данных, где каждый элемент имеет ссылку на соседний элемент.

Список бывает:

1. Однонаправленный

2. Двунаправленный

Графический пример однонаправленного списка:

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4815164223

Эта структура данных полезна для хранения данных, если планируется большое количество добавления и удаления элементов, потому что эти операции в списке будут работать быстрее, чем у массива.

---

Получение элемента по индексу

Принцип работы:

Чтобы получить элемент по индексу, нужно пройтись из начала списка по переходам до нужного индекса, затем вернуть полученный элемент.

В зависимости от запроса сложность получения элемента будет разной.

Сложность для двустороннего списка

1. Получение элемента из середины списка - $О(n)$

2. Получение элемента из начала списка - $O(1)$

3. Получение элемента из конца списка - $O(1)$

Сложность зависит от того, как направлен список, связан ли он слева направо, справа налево, или двунаправленный.

Пример получения элемента на индексе равный 3 в однонаправленном списке.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  48151642230               1               2                3               4               5indexзапрос, получитьэлемент на индексе 3Элемент на индексе 3 равен 16

Если список двунаправленный, то лучше добраться до индекса 3, начиная с правой стороны.

В итоге, это даёт сложность $O(\frac{n}2) = O(n)$.

Пример кода:

Реализация на C++

list - Стандартная реализация списка в С++. Хранится в виде двунаправленного списка. Чтобы начать работу со списком, нужно написать #include <list>.

Iterator - тип, предоставляющий двунаправленный итератор, который может читать или изменять любой элемент в списке. Используется для получения и дальнейшего взаимодействия. pointer - тип, предоставляющий указатель на элемент в списке.

list <int> c1;              // c1 = []
c1.push_back( 10 );         // c1 = [10]
c1.push_back( 20 );         // c1 = [10, 20]
c1.push_back( 30 );         // c1 = [10, 20, 30]
c1.push_back( 40 );         // c1 = [10, 20, 30, 40]
c1.push_back( 50 );         // c1 = [10, 20, 30, 40, 50]
auto Iter = c1.begin();
Iter++;
Iter++;
cout << *Iter;              // 30

---

Добавление элемента

Чтобы вставить новый элемент по индексу, нужно пройтись из начала списка по переходам до нужного индекса, затем добавить новые связи от элемента по индексу. В зависимости от запроса сложность вставки элемента будет разной.

Чтобы вставить элемент в начало списка, достаточно добавить связь с нового элемента до первой вершины списка.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  481516422311запрос на добавление вершины в начало

Аналогично для вставки в конец списка.

Если нужно вставить новый элемент на позиции $i$, то:

1. Добраться до элемента на позиции $i$;

2. Удалить связь с элемента на позиции $i - 1$ до элемента на позиции $i$;

3. Добавить связь с элемента на позиции $i - 1$ до нового элемента;

4. Добавить связь с нового элемента до элемента на позиции $i$;

Пример работы алгоритма для однонаправленного списка, добавим элемент 11 на позицию 3:

Сначала добраться до элемента.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  запрос на добавление вершины на позицию i = 34815164223 Затем удалить связь и добавить новые.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  481516422311

Полученный новый список после вставки элемента.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  481516422311

Для двунаправленного списка алгоритм аналогичный, только нужно вместо однонаправленных связей добавлять и удалять двунаправленные, а также появляется возможность на первом шаге идти справа до нужного элемента, если это будет выгодней.

Вычислительная сложность операций

1. Вставка элемента в середину списка - $О(n)$

2. Вставка элемента в начало списка - $O(1)$

3. Вставка элемента в конец списка - $O(1)$

Сложность зависит от того, как направлен список, связан ли он слева направо, справа налево, или двунаправленный.

Пример кода

Реализация на С++

Insert - вставляет элемент или количество элементов или диапазон элементов в указанное положение в списке.

Push_back - добавить элемент в конец списка.

list <int> c1;              // c1 = []
list <int>::iterator Iter;
c1.push_back(10);           // c1 = [10]
c1.push_back(20);           // c1 = [10, 20]
c1.push_back(30);           // c1 = [10, 20, 30]
c1.push_back(40);           // c1 = [10, 20, 30, 40]
Iter = c1.begin();
Iter++;
Iter++;
c1.insert(Iter, 2, 200);    // с1 = [10, 20, 200, 30, 40]

---

Удаление элемента

Чтобы удалить элемент по индексу, нужно пройтись из начала списка по переходам до нужного индекса, затем удалить связи у соседей до нужного элемента, затем добавить связь от одного соседа до другого. В зависимости от запроса сложность удаления элемента будет разной.

Чтобы удалить элемент из начала списка, достаточно удалить связь с первого элемента до второй вершины списка.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  запрос на удаление первой вершины4815164223

В итоге получился обновленный список без первого элемента.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  815164223

Аналогично для удаления последнего элемента списка.

Если нужно удалить элемент на позиции $i$, то:

1. Добраться до элемента на позиции $i$;

2. Удалить связи у соседей до элемента на позиции $i$;

   1. Удалить связь с элемента на позиции $i - 1$ до элемента на позиции $i$;
   2. Удалить связь с элемента на позиции $i$ до элемента на позиции $i+1$;

3. Добавить связь между соседями;

   1. Добавить связь с элемента на позиции $i-1$ до элемента на позиции $i+1$;

4. Удалить выбранный элемент из памяти.

Пример работы алгоритма для однонаправленного списка

Удалим элемент 16 из позиции 3

Сначала нужно добраться до элемента.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  запрос на удаление вершины на позицию i = 34815164223 Затем удалить связи и добавить новую. Удалить связи у соседей.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4815164223

Добавить новую связь между соседями.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4815164223

Сам элемент удалить из памяти. В итоге получился обновлённый список.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  48154223

Для двунаправленного списка алгоритм аналогичный, только нужно вместо однонаправленных связей добавлять и удалять двунаправленные, а также появляется возможность на первом шаге идти справа до нужного элемента, если это будет выгодней.

Если нужно удалить последовательность элементов из списка на промежутке от $L$ до $R$, то:

1. Добраться до элемента на позиции $L$;

2. Добраться до элемента на позиции $R$;

3. Удалить связи у соседей на границах;

   1. Удалить границу между элементом на позиции $L-1$ до элемента на позиции $L$;
   2. Удалить границу между элементом на позиции $R$ до элемента на позиции $R+1$;

4. Связать элемент на позиции $L-1$ с элементом на позиции $R+1$;

5. Удалить подвисшие элементы.

Пример работы алгоритма для однонаправленного списка, удалим элемент на промежутке на позиции от 2 до 3:

Сначала добраться до элементов на позиции $L = 2$, $R = 3$.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  запрос на удаление вершин на промежутке от 2 до 34815164223L-1           L               R              R+1

Затем удалить связи и добавить новую.

Удалить связь с элемента на позиции $L-1$ до элемента на позиции $L$

Удалить связь с элемента на позиции $R$ до элемента на позиции $R+1$.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4815164223L-1           L               R              R+1 Добавить новую связь между элементом на позиции $L-1$ до элемента на позиции $R+1$.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  4815164223L-1           L               R              R+1

Оставшиеся элементы удалить из памяти. В итоге получился обновлённый список.

 

   

      @font-face {

        font-family: "Virgil";

        src: url("https://excalidraw.com/Virgil.woff2");

      }

      @font-face {

        font-family: "Cascadia";

        src: url("https://excalidraw.com/Cascadia.woff2");

      }

   

 

  484223

Для двунаправленного списка алгоритм аналогичный, только нужно вместо однонаправленных связей добавлять и удалять двунаправленные, а также появляется возможность на первом шаге идти справа до нужного элемента, если это будет выгодней.

Сложность для двустороннего списка

Удаление элемента из середины списка - $О(n)$

Удаление элемента из начала списка - $O(1)$

Удаление элемента из конца списка - $O(1)$

Сложность зависит от того, как направлен список, связан ли он слева направо, справа налево, или двунаправленный.

Пример кода

Реализация на языке C++

erase - Удаляет элемент или диапазон элементов с указанных положений в списке.

list <int> c1;              // c1 = []
list <int>::iterator Iter;  
c1.push_back( 10 );         // c1 = [10]
c1.push_back( 20 );         // c1 = [10, 20]
c1.push_back( 30 );         // c1 = [10, 20, 30]
c1.push_back( 40 );         // c1 = [10, 20, 30, 40]
c1.push_back( 50 );         // c1 = [10, 20, 30, 40, 50]
c1.erase( c1.begin( ) );    // с1 = [20, 30, 40, 50]
Iter = c1.begin( );
Iter++;
c1.erase( Iter, c1.end( ) );// с1 = [20, 40, 50]

---

Продуктовый интерфейс на C++

Аннотация:
LIST - Шаблонный класс двусвязного списка.
Node - Структура узла списка.
value - Значение элемента в узле списка.
next - Указатель на следующий узел списка.
prev - Указатель на предыдущий узел списка.
Node(elem_type value, Node *next, Node *prev): Конструктор узла списка.
~Node() - Деструктор узла списка.
count_size - Количество элементов в списке.
first - Указатель на первый узел списка.
last - Указатель на последний узел списка.
LIST() - Конструктор списка по умолчанию.
LIST(std::vector<elem_type> &vec) - Конструктор списка с инициализацией из вектора.
~LIST() - Деструктор списка.

#ifndef C_LIST_H
#define C_LIST_H
#pragma once
#include <algorithm>
#include <memory>
#include <iterator>
#include <vector>
template <typename elem_type>
class LIST{
    struct Node{
        elem_type value;
        Node *next;
        Node *prev;

        Node(elem_type value, Node *next, Node *prev);
        ~Node();
    };
    int count_size = 0;
    Node *first;
    Node *last;

public:
    class Iterator{
        Node *m_ptr;

    public:
        Iterator(Node *ptr) : m_ptr(ptr) {}
        Node *operator->();
        elem_type operator*();
        Iterator *operator++();
        Iterator *operator+(int other);
        Iterator *operator-(int other);
        Iterator *operator--();
        const Iterator operator++(int);
        const Iterator operator--(int);
        bool operator!=(const Iterator &other);
        bool operator==(const Iterator &other);
    };

    elem_type &operator[](int n) const;
    LIST &operator=(std::vector<elem_type> &vec);

    void push_front(elem_type &x);
    void push_front(elem_type &&x);
    void push_back(elem_type &x);
    void push_back(elem_type &&x);
    void pop_front();
    void pop_back();
    elem_type &front();
    elem_type &back();
    int size();
    bool empty();

    void insert(Iterator pos, elem_type &x);
    void insert(Iterator pos, elem_type &&x);

    void erase(Iterator pos);
    void erase(Iterator pos_l, Iterator pos_r);

    Iterator begin();
    Iterator end();

    LIST();
    LIST(std::vector<elem_type> &vec);
    ~LIST();
};

---

Продуктовая реализация на С++

Аннотация:
m_ptr - указатель на текущий узел списка
first - указатель на первый узел списка
curr - указатель на текущий узел списка
vec - вектор для инициализации или присваивания значений списку
it - итератор по элементам вектора
Node - конструктор узла списка
value - значение элемента в узле списка
next - указатель на следующий узел списка
prev - указатель на предыдущий узел списка
~Node - деструктор узла списка
LIST - конструктор списка по умолчанию
push_front - метод добавления элемента в начало списка
last - указатель на последний узел списка
count_size - количество элементов в списке
push_back - метод добавления элемента в конец списка
pop_front - метод удаления первого элемента списка
elem - временная переменная для хранения указателя на узел
pop_back - метод удаления последнего элемента списка
size - метод получения размера списка
front - метод получения значения первого элемента списка
back - метод получения значения последнего элемента списка
empty - метод проверки списка на пустоту
pos - итератор на позицию вставки или удаления элемента
new_elem - новый узел списка
pos_l - итератор на левую границу диапазона удаления
pos_r - итератор на правую границу диапазона удаления
erase - метод удаления элемента из списка по итератору

#include "C_list.h"
#include <iostream>
#include <algorithm>

using namespace std;

template <typename elem_type>
typename LIST<elem_type>::Node *LIST<elem_type>::Iterator::operator->(){
    return m_ptr;
}

template <typename elem_type>
typename LIST<elem_type>::Iterator *LIST<elem_type>::Iterator::operator+(int other){
    while (other){
        m_ptr = m_ptr->next;
        other--;
    }
    return this;
}

template <typename elem_type>
typename LIST<elem_type>::Iterator *LIST<elem_type>::Iterator::operator-(int other){
    while (other){
        m_ptr = m_ptr->prev;
        other--;
    }
    return this;
}

template <typename elem_type>
elem_type LIST<elem_type>::Iterator::operator*() { return m_ptr->value; }

template <typename elem_type>
typename LIST<elem_type>::Iterator *LIST<elem_type>::Iterator::operator++(){
    m_ptr = m_ptr->next;
    return this;
}

template <typename elem_type>
typename LIST<elem_type>::Iterator *LIST<elem_type>::Iterator::operator--(){
    m_ptr = m_ptr->prev;
    return this;
}

template <typename elem_type>
const typename LIST<elem_type>::Iterator LIST<elem_type>::Iterator::operator++(int){
    Node *temp = m_ptr;
    m_ptr = m_ptr->next;
    return Iterator(temp);
}

template <typename elem_type>
const typename LIST<elem_type>::Iterator LIST<elem_type>::Iterator::operator--(int){
    Node *temp = m_ptr;
    m_ptr = m_ptr->prev;
    return Iterator(temp);
}

template <typename elem_type>
bool LIST<elem_type>::Iterator::operator!=(const LIST::Iterator &other) { return m_ptr != other.m_ptr; }

template <typename elem_type>
bool LIST<elem_type>::Iterator::operator==(const LIST::Iterator &other) { return m_ptr == other.m_ptr; }

template <typename elem_type>
typename LIST<elem_type>::Iterator LIST<elem_type>::begin() { return Iterator(first); }

template <typename elem_type>
typename LIST<elem_type>::Iterator LIST<elem_type>::end() { return Iterator(nullptr); }

template <typename elem_type>
elem_type &LIST<elem_type>::operator[](int n) const{
    Node *curr = first;
    while (n > 0){
        curr = curr->next;
        n--;
    }
    return curr->value;
}

template <typename elem_type>
LIST<elem_type> &LIST<elem_type>::operator=(std::vector<elem_type> &vec)
{
    while (count_size)
        pop_back();
    this->count_size = 0;
    this->first = nullptr;
    this->last = nullptr;
    for (auto it = vec.begin(); it != vec.end(); it++)
        push_back(*it);
}

template <typename elem_type>
LIST<elem_type>::Node::Node(elem_type value, Node *next, Node *prev){
    this->value = value;
    this->next = next;
    this->prev = prev;
}

template <typename elem_type>
LIST<elem_type>::Node::~Node(){
    this->next = nullptr;
    this->prev = nullptr;
}

template <typename elem_type>
LIST<elem_type>::LIST(){
    this->count_size = 0;
    this->first = nullptr;
    this->last = nullptr;
}

template <typename elem_type>
LIST<elem_type>::LIST(std::vector<elem_type> &vec){
    this->count_size = 0;
    this->first = nullptr;
    this->last = nullptr;
    for (auto it = vec.begin(); it != vec.end(); it++)
        push_back(*it);
}

template <typename elem_type>
LIST<elem_type>::~LIST(){
    while (count_size)
        pop_back();
}

template <typename elem_type>
void LIST<elem_type>::push_front(elem_type &x){
    if (!count_size){
        auto node = new Node(x, nullptr, nullptr);
        last = node;
        first = node;
    }
    else{
        auto node = new Node(x, first, nullptr);
        node->next->prev = node;
        first = node;
    }
    count_size++;
}

template <typename elem_type>
void LIST<elem_type>::push_front(elem_type &&x){
    if (!count_size){
        auto node = new Node(x, nullptr, nullptr);
        last = node;
        first = node;
    }
    else{
        auto node = new Node(x, first, nullptr);
        node->next->prev = node;
        first = node;
    }
    count_size++;
}

template <typename elem_type>
void LIST<elem_type>::push_back(elem_type &x){
    if (!count_size){
        auto node = new Node(x, nullptr, nullptr);
        last = node;
        first = node;
    }
    else{
        auto node = new Node(x, nullptr, last);
        node->prev->next = node;
        last = node;
    }
    count_size++;
}

template <typename elem_type>
void LIST<elem_type>::push_back(elem_type &&x){
    if (!count_size){
        auto node = new Node(x, nullptr, nullptr);
        last = node;
        first = node;
    }
    else{
        auto node = new Node(x, nullptr, last);
        node->prev->next = node;
        last = node;
    }
    count_size++;
}

template <typename elem_type>
void LIST<elem_type>::pop_front(){
    if (count_size == 0)
        return;
    else if (count_size == 1){
        delete first;
        count_size--;
    }
    else{
        auto elem = first->next;
        elem->prev = nullptr;
        delete first;
        first = elem;
        count_size--;
    }
}

template <typename elem_type>
void LIST<elem_type>::pop_back(){
    if (count_size == 0)
        return;
    else if (count_size == 1){
        delete first;
        count_size--;
    }
    else{
        auto elem = last->prev;
        elem->next = nullptr;
        delete last;
        last = elem;
        count_size--;
    }
}

template <typename elem_type>
int LIST<elem_type>::size(){
    return count_size;
}

template <typename elem_type>
elem_type &LIST<elem_type>::front(){
    return first->value;
}

template <typename elem_type>
elem_type &LIST<elem_type>::back(){
    return last->value;
}

template <typename elem_type>
bool LIST<elem_type>::empty(){
    if (count_size == 0)
        return true;
    return false;
}

template <typename elem_type>
void LIST<elem_type>::insert(LIST::Iterator pos, elem_type &x){
    if (pos == begin())
        push_front(x);
    else if (pos == end())
        push_back(x);
    else{
        auto new_elem = new Node(x, nullptr, nullptr);
        auto pos_l = pos->prev;
        auto pos_r = pos_l->next;

        pos_l->next = new_elem;
        pos_r->prev = new_elem;
        new_elem->next = pos_r;
        new_elem->prev = pos_l;
        count_size++;
    }
}

template <typename elem_type>
void LIST<elem_type>::insert(LIST::Iterator pos, elem_type &&x){
    if (pos == begin())
        push_front(x);
    else if (pos == end())
        push_back(x);
    else{
        auto new_elem = new Node(x, nullptr, nullptr);
        auto pos_l = pos->prev;
        auto pos_r = pos_l->next;

        pos_l->next = new_elem;
        pos_r->prev = new_elem;
        new_elem->next = pos_r;
        new_elem->prev = pos_l;
        count_size++;
    }
}

template <typename elem_type>
void LIST<elem_type>::erase(Iterator pos){
    if (pos == begin())
        pop_front();
    else if (pos == end())
        pop_back();
    else{
        auto pos_r = pos->next;
        auto pos_l = pos->prev;

        delete pos_l->next;
        pos_l->next = pos_r;
        pos_r->prev = pos_l;
        count_size--;
    }
}

template <typename elem_type>
void LIST<elem_type>::erase(Iterator pos_l, Iterator pos_r){
    if (pos_l->prev == nullptr){
        while (pos_l != pos_r){
            pos_l = pos_l->next;
            pop_front();
        }
        pop_front();
    }
    else if (pos_r == nullptr){
        pos_r = last;
        while (pos_r != pos_l){
            pos_r = pos_r->prev;
            pop_back();
        }
        pop_back();
    }
    else{
        auto elem_l = pos_l->prev;
        auto elem_r = pos_r->next;
        while (pos_l != pos_r){
            pos_l = pos_l->next;
            delete pos_l->prev;
            count_size--;
        }
        delete elem_r->prev;
        count_size--;
        elem_l->next = elem_r;
        elem_r->prev = elem_l;
    }
}