В C++ связанный список — это структура данных, используемая для хранения набора элементов. Каждый элемент, называемый узлом, содержит как данные, так и указатель на следующий узел в списке. Связанные списки обеспечивают динамическое распределение памяти и эффективные операции вставки и удаления. Вот некоторые распространенные методы, связанные со связанными списками в C++:

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

struct Node {
    int data;
    Node* next;
};

2. Вставка:

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

   void insertAtBeginning(Node head, int data) {
      Node* newNode = new Node();
      newNode->data = data;
      newNode->next = *head;
      *head = newNode;
   }

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

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

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

   void insertAtPosition(Node head, int data, int position) {
      if (position < 0)
          return;
      if (position == 0) {
          insertAtBeginning(head, data);
          return;
      }
      Node* newNode = new Node();
      newNode->data = data;
      Node* temp = *head;
      for (int i = 0; i < position - 1 && temp != nullptr; ++i) {
          temp = temp->next;
      }
      if (temp == nullptr)
          return;
      newNode->next = temp->next;
      temp->next = newNode;
   }

3. Удаление:

   • Удалить в начале: переместите указатель заголовка на следующий узел и удалите предыдущий узел.

   void deleteAtBeginning(Node head) {
      if (*head == nullptr)
          return;
      Node* temp = *head;
      *head = (*head)->next;
      delete temp;
   }

   • Удалить в конце: пройти по списку до предпоследнего узла, обновить его следующий указатель до нуля и удалить последний узел.

   void deleteAtEnd(Node head) {
      if (*head == nullptr)
          return;
      if ((*head)->next == nullptr) {
          delete *head;
          *head = nullptr;
          return;
      }
      Node* temp = *head;
      while (temp->next->next != nullptr) {
          temp = temp->next;
      }
      delete temp->next;
      temp->next = nullptr;
   }

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

   void deleteAtPosition(Node head, int position) {
      if (*head == nullptr)
          return;
      if (position == 0) {
          deleteAtBeginning(head);
          return;
      }
      Node* temp = *head;
      for (int i = 0; i < position - 1 && temp != nullptr; ++i) {
          temp = temp->next;
      }
      if (temp == nullptr || temp->next == nullptr)
          return;
      Node* nodeToDelete = temp->next;
      temp->next = temp->next->next;
      delete nodeToDelete;
   }

4. Обход: перебор связанного списка, начиная с заголовка, и выполнение операций над каждым узлом.

   void traverseLinkedList(Node* head) {
      Node* temp = head;
      while (temp != nullptr) {
          // Do something with temp->data
          temp = temp->next;
      }
   }

5. Поиск: просматривайте список и сравнивайте данные в каждом узле, пока не будет найдено совпадение или не будет достигнут конец списка.

   Node* search(Node* head, int value) {
      Node* temp = head;
      while (temp != nullptr) {
          if (temp->datamatches the value)
              return temp;
          temp = temp->next;
      }
      return nullptr;  // Value not found
   }

6. Длина: просмотрите список и подсчитайте количество узлов.

   int getLength(Node* head) {
      int count = 0;
      Node* temp = head;
      while (temp != nullptr) {
          count++;
          temp = temp->next;
      }
      return count;
   }

7. Реверс: обратный порядок узлов в связанном списке.

   void reverseLinkedList(Node head) {
      Node* prev = nullptr;
      Node* current = *head;
      Node* next = nullptr;
      while (current != nullptr) {
          next = current->next;
          current->next = prev;
          prev = current;
          current = next;
      }
      *head = prev;
   }

8. Отображение: печать элементов связанного списка.

   void displayLinkedList(Node* head) {
      Node* temp = head;
      while (temp != nullptr) {
          cout << temp->data << " ";
          temp = temp->next;
      }
      cout << endl;
   }

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