10 апр 2021 в 00:26

Реализация односвязного списка на c++

Ожидает приглашения

Всем привет! Сегодня я расскажу как реализовать, наверное, самую популярную структуру данных - односвязный список. Подразумевается, что вы уже знаете такие темы, как указатели, функции и конструкторы.

Односвязный список - это динамическая структура данных, состоящая из узлов. Каждый узел будет иметь какое-то значение (я буду использовать строку) и указатель на следующий узел.

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

Реализация узла

struct Node {
  string val;
  Node* next;
  Node(string _val) : val(_val), next(nullptr){}
};

В этом узле есть:

Значение, которое будет задавать пользователь
Указатель на следующий элемент (по умолчанию nullptr)
Конструктор

Реализация односвязного списка

В списке будет:

Указатель на первый узел
Указатель на последний узел
Конструктор
Функция проверки наличия узлов в списке
Функция добавления элемента в конец списка
Функция печати всего списка
Функция поиска узла в списке по заданному значению
Функция удаления первого узла
Функция удаления последнего узла
Функция удаления узла по заданному значению значению
Функция обращения к узлу по индексу (дополнительная функция)

Реализация 1-3 пункта

struct list {
    Node* first;
    Node* last;

    list() : first(nullptr), last(nullptr) {}
};

Функция проверки наличия узлов в списке

Это однострочная функция, в которой надо проверить является ли первый узел - пустым

bool is_empty() {
    return first == nullptr;
}

Функция добавления элемента в конец списка

Здесь надо рассмотреть два случая:

Список - пустой
Список не пустой
В обоих случаях надо создать сам узел со значением, которое мы передали в эту функцию.

void push_back(string _val) {
    Node* p = new Node(_val);
}

Первый случай:

Здесь нам как раз пригодиться функция проверки наличия узлов. Если список пустой, тогда мы присваиваем указателю на первый узел и последний узел указатель на новый узел и выходим из функции.

void push_back(string _val) {
    Node* p = new Node(_val);
    if (is_empty()) {
      first = p;
      last = p;
      return;
    }
}

Второй случай:

Нам уже не нужно проверка наличия узлов в списке, так как если первый случай не происходит, то в списке есть узлы. Раз мы добавляем в конец, надо указать, что новый узел стоит после последнего узла. Затем мы меняем значения указателя last.

void push_back(string _val) {
    Node* p = new Node(_val);
    if (is_empty()) {
      first = p;
      last = p;
      return;
    }
    last->next = p;
    last = p;
}

Теперь в список можно добавлять элементы.

Функция печати всего списка

Начинаем функцию с проверки is_empty(). Далее создаём указатель p на первый узел и выводим значение узла, пока p не пустой, при каждой итерации обновляем значение p на следующий узел.

void print() {
    if (is_empty()) return;
    while (p) { // p != nullptr
      cout << p->val << " ";
      p = p->next;
    }
    cout << endl;
}

Тест уже написанных функций

Код который мы написали:

#include <iostream>
using namespace std;

struct Node {
    string val;
    Node* next;

    Node(string _val) : val(_val), next(nullptr) {}
};

struct list {
    Node* first;
    Node* last;

    list() : first(nullptr), last(nullptr) {}

    bool is_empty() {
        return first == nullptr;
    }

    void push_back(string _val) {
        Node* p = new Node(_val);
        if (is_empty()) {
            first = p;
            last = p;
            return;
        }
        last->next = p;
        last = p;
    }

    void print() {
        if (is_empty()) return;
        Node* p = first;
        while (p) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }
}

int main() {
    list l;
    cout << l.is_empty() << endl;
    l.push_back("3");
    l.push_back("123")    l.push_back("8");
    cout << l.is_empty() << endl;
    l.print();
    return 0;
}

[Output]
1
3 123 8 
0

Функция поиска узла в списке по заданному значению

Также делаем проверку is_empty() и создаём указатель p на первый узел

if (is_empty()) return;
Node* p = first;

Обходим список, пока указатель p не пустой и пока значение узла p не равно заданному значению. После цикла возвращаем наш узел

while (p && p->val != _val) p = p->next;
return p ? p : nullptr;

Весь код функции:

Node* find(string _val) {
    Node* p = first;
    while (p && p->val != _val) p = p->next;
		return (p && p->val == _val) ? p : nullptr;
}

Функция удаления первого узла

Делаем проверку is_empty(). Далее создаём указатель p на первый узел списка. Меняем значение первого узла на следующий и удаляем узел p;

void remove_first() {
    if (is_empty()) return;
    Node* p = first;
    first = p->next;
    delete p;
}

Функция удаления последнего узла

Это функция сложнее функции удаления первого узла. Сначала также делаем проверку is_empty(). А теперь надо надо рассмотреть два случая:

Конец списка одновременно и начало
Когда размер списка больше одного

Первый случай:

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

Второй случай:

Создаём указатель p на первый узел и обходим список, пока следующий узел не равен последнему. Убираем у указателя p следующий узел и удаляем p.

Код функции:

void remove_last() {
    if (is_empty()) return;
    if (first == last) {
        remove_first();
        return;
    }
    Node* p = first;
    while (p->next != last) p = p->next;
    p->next = nullptr;
    delete last;
    last = p;
}

Функция удаления узла по заданному значению значению

Делаем проверку is_empty(). И рассматриваем уже три случая:

Узел, который нам нужен, равен первому
Узел, который нам нужен, равен последнему
Когда не первый и не второй случаи

Первый случай:

Сравниваем значение первого узла с заданным значением, если значения совпадают, тогда вызываем функцию удаления первого узла.

Второй случай:

Сравниваем значение последнего узла с заданным значением, если значения совпадают, тогда вызываем функцию удаления последнего узла.

Третий случай:

Создаём указатели slow, равный первому узлу, и fast, равный следующему узлу после первого. Затем пока fast не пустой и пока значения узла fast не равно заданному значению, при каждой итерации обновляем значения slow и fast на следующий после них узел. Далее делаем проверку, что указатель fast пустой, если это так, тогда мы выводим ошибку, иначе просто удаляем узел fast.

Код функции:

void remove(string _val) {
    if (is_empty()) return;
    if (first->val == _val) {
        remove_first();
        return;
    }
    else if (last->val == _val) {
    		remove_last();
        return;
    }
    Node* slow = first;
    Node* fast = first->next;
    while (fast && fast->val != _val) {
        fast = fast->next;
        slow = slow->next;
    }
    if (!fast) {
        cout << "This element does not exist" << endl;
        return;
    }
    slow->next = fast->next;
    delete fast;
}

Функция обращения к узлу по индексу

Для этой функции надо перегрузить оператор []

Node* operator[] (const int index)

Дальше делаем проверку is_empty(). Создадим указатель p на первый узел списка. С помощью цикла for будем обновлять значение указателя p на следующий указатель, также делаем проверку на пустоту указателя p. В конце возвращаем узел p.

Node* operator[] (const int index) {
    if (is_empty()) return nullptr;
    Node* p = first;
    for (int i = 0; i < index; i++) {
        p = p->next;
        if (!p) return nullptr;
    }
    return p;
}

Тест программы

Весь код:

#include <iostream>
using namespace std;

struct Node {
    string val;
    Node* next;

    Node(string _val) : val(_val), next(nullptr) {}
};

struct list {
    Node* first;
    Node* last;

    list() : first(nullptr), last(nullptr) {}

    bool is_empty() {
        return first == nullptr;
    }

    void push_back(string _val) {
        Node* p = new Node(_val);
        if (is_empty()) {
            first = p;
            last = p;
            return;
        }
        last->next = p;
        last = p;
    }

    void print() {
        if (is_empty()) return;
        Node* p = first;
        while (p) {
            cout << p->val << " ";
            p = p->next;
        }
        cout << endl;
    }

    Node* find(string _val) {
        Node* p = first;
        while (p && p->val != _val) p = p->next;
        return (p && p->val == _val) ? p : nullptr;
    }

    void remove_first() {
        if (is_empty()) return;
        Node* p = first;
        first = p->next;
        delete p;
    }

    void remove_last() {
        if (is_empty()) return;
        if (first == last) {
            remove_first();
            return;
        }
        Node* p = first;
        while (p->next != last) p = p->next;
        p->next = nullptr;
        delete last;
        last = p;
    }

    void remove(string _val) {
        if (is_empty()) return;
        if (first->val == _val) {
            remove_first();
            return;
        }
        else if (last->val == _val) {
            remove_last();
            return;
        }
        Node* slow = first;
        Node* fast = first->next;
        while (fast && fast->val != _val) {
            fast = fast->next;
            slow = slow->next;
        }
        if (!fast) {
            cout << "This element does not exist" << endl;
            return;
        }
        slow->next = fast->next;
        delete fast;
    }

    Node* operator[] (const int index) {
        if (is_empty()) return nullptr;
        Node* p = first;
        for (int i = 0; i < index; i++) {
            p = p->next;
            if (!p) return nullptr;
        }
        return p;
    }
};

int main()
{
    list l;
    cout << l.is_empty() << endl;
    l.push_back("3");
    l.push_back("123");
    l.push_back("8");
    l.print();
    cout << l.is_empty() << endl;
    l.remove("123");
    l.print();
    l.push_back("1234");
    l.remove_first();
    l.print();
    l.remove_last();
    l.print();
    cout << l[0]->val << endl;
    return 0;
}

[Output]
1
3 123 8
0
3 8
8 1234
8
8

Заключение

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

Теги:

Хабы: