Evgenii Legotckoi
Evgenii Legotckoi22 апреля 2019 г. 2:13

Операции со связанным списком

Данная статья приурочена к старту курса "Алгоритмы для разработчиков" от компании OTUS. Выражаю признательность за поддержку ресурса данной компанией.

Давайте изучим, какие операции можно выполнять со связанным списком.

Два важных момента, которые нужно помнить:

  • head указывает на первый узел связанного списка
  • next указатель последнего узла равен nullptr , поэтому, если следующий из текущего узла равен nullptr , мы достигли конца связанного списка.

Во всех примерах мы будем предполагать, что связанный список имеет три узла 1 ---> 2 ---> 3 со структурой узла, как показано ниже:

struct node
{
    int data;
    struct node* next {nullptr};
};

Как пройти по связанному списку

Отображение содержимого связанного списка очень просто. Мы продолжаем перемещать временный узел к следующему и отображаем его содержимое.

Когда temp равен NULL , мы знаем, что достигли конца связанного списка, поэтому мы выходим из цикла while .

struct node* temp = head;
std::cout << std::endl << std::endl << "List elements are - " << std::endl;
while(temp != nullptr)
{
    std::cout << temp->data << " ---> ";
    temp = temp->next;
}

Вывод этой программы будет:

List elements are - 
1 ---> 2 ---> 3 --->

Как добавить элементы в связанный список

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

Добавить в начало

  • Выделите память для нового узла
  • Сохраните данные
  • Измените новый next узел, чтобы он указывал на head
  • Измените head , чтобы указать на недавно созданный узел
struct node* newNode = new node();
newNode->data = value;
newNode->next = head;
head = newNode;

Добавить в конец

  • Выделите память для нового узла
  • Сохраните данные
  • Сделайте переход к последнему узлу
  • Измените next из последнего узла на недавно созданный узел
struct node* newNode = new node();
newNode->data = value;
newNode->next = nullptr;

struct node *temp = head;
while (temp->next != nullptr)
{
    temp = temp->next;
}
temp->next = newNode;

Добавить в середину

  • Выделите память и сохраните данные для нового узла
  • Переход к узлу непосредственно перед требуемой позицией нового узла
  • Измените next указатели, чтобы добавить новый узел между ними
struct node *newNode = new node();
newNode->data = value;

struct node *temp = head;

for (int i=2; i < position; i++)
{
    if (temp->next != nullptr)
    {
        temp = temp->next;
    }
}
newNode->next = temp->next;
temp->next = newNode;

Как удалить узел из связанного списка

Вы можете удалить либо из начала, конца или из определенной позиции.

Удалить с начала

  • Настройте указатель head на второй узел
head = head->next;

Удалить с конца

  • Перейти ко второму последнему элементу
  • Изменить next указатель на nullptr
struct node* temp = head;
while (temp->next->next != nullptr)
{
    temp = temp->next;
}
temp->next = nullptr;

Удалить из середины

  • Переход к элементу до удаляемого элемента
  • Изменить next указатели, чтобы исключить узел из цепочки
struct node* temp = head;
for (int i = 2; i < position; ++i)
{
    if (temp->next != nullptr)
    {
        temp = temp->next;
    }
}

temp->next = temp->next->next;

Полная программа для операций со связанным списком

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

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

Также обратите внимание на то, как мы передаем адрес head как struct node headRef в функции insertAtFront и deleteFromFront. Эти две функции изменяют положение указателя head , поэтому нам нужно передать адрес указателя head** и изменить его значение внутри функции.

#include <iostream>

struct node
{
  int data;
  struct node* next {nullptr};
};

void display(struct node* head)
{
    struct node* temp = head;
    std::cout << std::endl << std::endl << "List elements are - " << std::endl;
    while(temp != nullptr)
    {
        std::cout << temp->data << " ---> ";
        temp = temp->next;
    }
}

void insertAtMiddle(struct node *head, int position, int value)
{
    struct node *newNode = new node();
    newNode->data = value;

    struct node *temp = head;

    for (int i=2; i < position; i++)
    {
        if (temp->next != nullptr)
        {
            temp = temp->next;
        }
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

void insertAtFront(struct node** headRef, int value)
{
    struct node* head = *headRef;

    struct node* newNode = new node();
    newNode->data = value;
    newNode->next = head;
    head = newNode;

    *headRef = head;
}

void insertAtEnd(struct node* head, int value)
{
    struct node* newNode = new node();
    newNode->data = value;
    newNode->next = nullptr;

    struct node *temp = head;
    while (temp->next != nullptr)
    {
        temp = temp->next;
    }
    temp->next = newNode;
}

void deleteFromFront(struct node** headRef)
{
    struct node* head =  *headRef;
    head = head->next;
    *headRef = head;
}

void deleteFromEnd(struct node* head)
{
    struct node* temp = head;
    while (temp->next->next != nullptr)
    {
      temp = temp->next;
    }
    temp->next = nullptr;
}

void deleteFromMiddle(struct node* head, int position)
{
    struct node* temp = head;
    for (int i = 2; i < position; ++i)
    {
        if (temp->next != nullptr)
        {
            temp = temp->next;
        }
    }

    temp->next = temp->next->next;
}

int main()
{
  /* Initialize nodes */
  struct node *head;
  struct node *one = new node();
  struct node *two = new node();
  struct node *three = new node();

  /* Assign data values */
  one->data = 1;
  two->data = 2;
  three->data = 3;

  /* Connect nodes */
  one->next = two;
  two->next = three;
  three->next = nullptr;

  /* Save address of first node in head */
  head = one;

  display(head); // 1 ---> 2 ---> 3 --->

  insertAtFront(&head, 4);
  display(head); // 4 ---> 1 ---> 2 ---> 3 --->

  deleteFromFront(&head);
  display(head); // 1 ---> 2 ---> 3 --->

  insertAtEnd(head, 5);
  display(head); // 1 ---> 2 ---> 3 ---> 5 --->

  deleteFromEnd(head);
  display(head); // 1 ---> 2 ---> 3 --->

  int position = 3;
  insertAtMiddle(head, position, 10);
  display(head); // 1 ---> 2 ---> 10 ---> 3 --->

  deleteFromMiddle(head, position);
  display(head); // 1 ---> 2 ---> 3 --->
}

Вывод программы будет следующим

List elements are - 
1 ---> 2 ---> 3 ---> 

List elements are - 
4 ---> 1 ---> 2 ---> 3 ---> 

List elements are - 
1 ---> 2 ---> 3 ---> 

List elements are - 
1 ---> 2 ---> 3 ---> 5 ---> 

List elements are - 
1 ---> 2 ---> 3 ---> 

List elements are - 
1 ---> 2 ---> 10 ---> 3 ---> 

List elements are - 
1 ---> 2 ---> 3 --->

Заключение

Также вы можете изучить более углублённо алгоритмы на курсе "Алгоритмы для разработчиков" от компании OTUS вы сможете более углублённо изучить как базовые алгоритмы, так и более сложные.

Курс предлагает следующее:

  • Понимание принципов работы разнообразных алгоритмов, структур данных
  • Умение использовать готовые алгоритмы и структуры данных и создавать свои под поставленную задачу
  • Владение техникой вычисления сложности алгоритмов
  • Освоение продвинутых структур данных: хэш-таблиц, графов, деревьев поиска и многих других
  • Умение решать алгебраические задачи и задачи динамического программирования

При этом на данном курсе предлагается изучение алгоритмов и структур данных с использованием таких языков программирования как Java, C++, Python.

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

Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Вам это нравится? Поделитесь в социальных сетях!

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
AD

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:50баллов,
  • Очки рейтинга-4
m
  • molni99
  • 26 октября 2024 г. 1:37

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:80баллов,
  • Очки рейтинга4
m
  • molni99
  • 26 октября 2024 г. 1:29

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:20баллов,
  • Очки рейтинга-10
Последние комментарии
ИМ
Игорь Максимов22 ноября 2024 г. 11:51
Django - Урок 017. Кастомизированная страница авторизации на Django Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii Legotckoi31 октября 2024 г. 14:37
Django - Урок 064. Как написать расширение для Python Markdown Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZE19 октября 2024 г. 8:19
Читалка fb3-файлов на Qt Creator Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь Максимов5 октября 2024 г. 7:51
Django - Урок 064. Как написать расширение для Python Markdown Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas55 июля 2024 г. 11:02
QML - Урок 016. База данных SQLite и работа с ней в QML Qt Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Сейчас обсуждают на форуме
m
moogo22 ноября 2024 г. 7:17
Mosquito Spray System Effective Mosquito Systems for Backyard | Eco-Friendly Misting Control Device & Repellent Spray - Moogo ; Upgrade your backyard with our mosquito-repellent device! Our misters conce…
Evgenii Legotckoi
Evgenii Legotckoi24 июня 2024 г. 15:11
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey115 ноября 2024 г. 6:04
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProject4 июня 2022 г. 3:49
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…

Следите за нами в социальных сетях