Связные списки

Связанный список - это базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит значение и ссылку на следующий(а может еще и на предыдущий)узел. Первый элемент списка - Head, последний - Tail, он ссылается на NULL. В связанном списке элементы линейно упорядочены, но порядок определяется не номерами, а указателями, входящими в состав элементов списка.

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

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

Связанные списки бывают нескольких видов:

Односторонне связанные. Узел помимо значения хранит указатель на следующий в цепочке узел
Двусторонне связанные. Узел помимо значения хранит указатели на следующий и предыдущий узлы
Кольцевые. Последний узел в списке хранит указатели на самый первый узел в списке
Упорядоченные. Все узлы списка расположены по возрастанию ключей

Преимущества связных списков:

Динамическое выделение памяти: Связные списки позволяют динамически выделять память для каждого элемента списка. Это означает, что связные списки могут расти и сжиматься по мере необходимости, без необходимости заранее определенного размера.
Простота вставки и удаления элементов: Вставка и удаление элементов в связном списке происходят за константное время $O (1)$ , если известно место вставки или удаления. Это делает связные списки эффективными структурами данных для операций вставки и удаления элементов в начале, конце и середине списка.
Гибкость: Связные списки могут содержать элементы различных типов и могут быть легко изменены и модифицированы. Это позволяет легко вставлять, удалять и перемещать элементы в списке.

Недостатки связных списков:

Неэффективный доступ по индексу: Доступ к элементу по индексу в связном списке требует просмотра списка от начала до нужного элемента. Это делает операцию доступа по индексу неэффективной и занимает время $O (n)$ , где $n$ — количество элементов в списке.
Дополнительное использование памяти: Каждый элемент связного списка требует дополнительной памяти для хранения указателя на следующий элемент. Это может привести к дополнительному использованию памяти по сравнению с другими структурами данных, такими как массивы. Размер указателя в c++ на всех новых системах (64-битная машина) имеет размер 8 байт (2 int'а). (это вызвано тем, что надо занумеровать всю память)
Сложность обхода в обратном направлении: Обход связного списка в обратном направлении (от конца к началу) требует наличия указателя на предыдущий элемент в каждом узле. Если такой указатель отсутствует, обход в обратном направлении становится сложным или невозможным.

Односторонний связный список

Давайте разберем реализацию одностороннего связанного списка.

Сперва нам понадобится создать структуру узла. Она будет иметь поля data типа int для хранения ключа и указатель next на тип Node. Подробнее про указатели тут

struct Node {
  int data;
  Node* next;
}

Следующим этапом будет добавление новых элементов в наш список.

void insert(int data) {
  Node* newNode =
      new Node(data);  // Создание нового узла с переданным значением data
  if (head == nullptr) {
    head = newNode;  // Если список пустой, устанавливаем голову списка на новый
                     // узел
  } else {
    Node* temp = head;  // Создание временного указателя, устанавливаем его на
                        // голову списка
    while (temp->next != nullptr) {
      temp = temp->next;  // Проходим по списку до последнего узла
    }
    temp->next = newNode;  // Устанавливаем указатель next последнего узла на
                           // новый узел, добавляя его в конец списка
  }
}

Следующим этапом будет поиск элементов в связном списке.

Node* search(Node* head, int key) {
  Node* current = head;  // Устанавливаем указатель current на голову списка
  while (current != nullptr) {  // Пока не достигнут конец списка
    if (current->data == key) {  // Если значение текущего узла равно ключу
      return current;  // Возвращаем указатель на текущий узел, так как элемент
                       // найден
    }
    current = current->next;  // Переходим к следующему узлу
  }
  return nullptr;  // Если элемент не найден, возвращаем nullptr
}

Теперь удалим элемент из связного списка. В этом примере мы используем функцию deleteNode, которая принимает указатель на голову списка head и ключ key, соответствующий элементу, который мы хотим удалить из списка.

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

Если элемент находится в середине или конце списка, мы используем два указателя temp и prev, чтобы пройти по списку и найти узел с заданным ключом. После нахождения узла, мы обновляем указатель next предыдущего узла, чтобы пропустить удаляемый узел, и освобождаем память.

void deleteNode(Node** head, int key) {
  Node* temp = *head;  // Устанавливаем указатель temp на голову списка
  Node* prev = nullptr;  // Инициализируем указатель prev как nullptr

  // Если голова списка содержит искомый элемент
  if (temp != nullptr && temp->data == key) {
    *head = temp->next;  // Обновляем голову списка на следующий узел
    delete temp;  // Освобождаем память, где хранился искомый элемент
    return;       // Возвращаемся из функции
  }

  // Поиск узла с заданным ключом
  while (temp != nullptr && temp->data != key) {
    prev = temp;        // Сохраняем текущий узел в prev
    temp = temp->next;  // Переходим к следующему узлу
  }

  // Если элемент не найден
  if (temp == nullptr) {
    return;  // Возвращаемся из функции
  }

  // Удаление узла
  prev->next = temp->next;  // Обновляем указатель next предыдущего узла, чтобы
                            // пропустить удаляемый узел
  delete temp;  // Освобождаем память, где хранился искомый элемент
}

Теперь напишем функцию по выводу списка.

void printList(Node* head) {
  Node* temp = head;  // Устанавливаем указатель temp на голову списка
  while (temp != nullptr) {  // Пока не достигнут конец списка
    std::cout << temp->data << " ";  // Выводим значение текущего узла
    temp = temp->next;  // Переходим к следующему узлу
  }
  std::cout << "\n";  // Печатаем перевод строки
}

Теперь мы реализуем работу списка.

#include <iostream>

struct Node {
  int data;
  Node* next;

  Node(int data) : data(data), next(nullptr) {}
};

struct my_linked_list {
 private:
  Node* head;

 public:
  my_linked_list() : head(nullptr) {}

  void push(int data) {
    Node* newNode = new Node(data);
    if (head == nullptr) {
      head = newNode;
    } else {
      Node* temp = head;
      while (temp->next != nullptr) {
        temp = temp->next;
      }
      temp->next = newNode;
    }
  }

  Node* search(int key) {
    Node* current = head;
    while (current != nullptr) {
      if (current->data == key) {
        return current;
      }
      current = current->next;
    }
    return nullptr;
  }

  void deleteNode(int key) {
    Node* current = head;
    Node* prev = nullptr;

    if (current != nullptr && current->data == key) {
      head = current->next;
      delete current;
      return;
    }
    while (current != nullptr && current->data != key) {
      prev = current;
      current = current->next;
    }
    if (current->next == nullptr) {
      return;
    }
    prev->next = current->next;
    delete current;
  }

  void printList() {
    Node* current = head;
    while (current != nullptr) {
      std::cout << current->data << " ";
      current = current->next;
    }
    std::cout << "\n";
  }
};

int main() {
  my_linked_list my_list;  // создаем экземпляр структуры
  for (int i = 0; i < 10; i++) {
    my_list.push(i);  // добавляем числа от 0 до 9
  }
  my_list.push(10);       // добавим цифру 10
  my_list.printList();    // выведем список
  my_list.deleteNode(5);  // удалим 5
  my_list.printList();    // выведем список
}

is-algo

Связные списки

Преимущества связных списков:

Недостатки связных списков:

Односторонний связный список