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

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

Начнем с того, что первым шагом нашего путешествия будет создание класса «Узел», который будет иметь две переменные-члены: закрытый ключ, в котором будут храниться данные, и указатель, который свяжет узел с другими узлами (следующий указатель сохраняет адрес следующего узла, с которым связан первый узел).

Перед объявлением класса мы добавляем объявление прекомпилятора #ifndef _NODE_H #define _NODE_H #endif с целью предотвращения многократного включения одного и того же заголовочного файла (вы также можете использовать #pragma Once в зависимости от вашего компилятора). ниже #define _NODE_H_ мы добавляем оператор template‹class Type›, чтобы иметь несколько типов данных в наших объектах узла. вот так выглядит наш заголовочный файл node.h:

Класс Node имеет закрытый ключ, который может содержать данные ‹Type› в соответствии с ООП (объектно-ориентированным программированием) парадигма инкапсуляцииn ,и общедоступный указатель, который инициализируется значением NULL (nullptr для C++11) во избежание проблем с памятью Узел *next{nullptr};” будет инициализировано значением NULL. если вы не знакомы с «C++11 {} — это способ инициализации переменных.

Все методы-члены являются общедоступными, Node.h включает в себя: два конструктора, один с константной ссылкой на тип данных параметра (рекомендую вам прочитать о функциях и преимуществах перехода по константным ссылкам), конструктор по умолчанию, геттер и сеттер для значения ключа и, наконец, деструктор. Теперь давайте определим методы в исходном файле Node.cpp.

В исходном файле мы можем найти конструктор "Node::Node(const Type &data)" (оператор разрешения области видимости "::"использует пространство имен Node.h для идентификации и указания содержимого и метода, принадлежащего этому файлуe) со значением параметра, которое присваивается переменной-члену (ключу), дополнительно конструктор без параметра вызывает конструктор с параметром, передавая значение NULL.

getter возвращает ссылку значения ключа и setter, который присваивает аргумент, переданный в функцию (const Type &reference), ключу собственного узла. Наконец, деструктор, который вызывается при уничтожении объекта, присваивает указатель рядом с nullptr, чтобы избежать висячего указателя.

Второй шаг — создать файлы LinkedList.cpp и LinkedList.h. В заголовочном файле LinkedList.h мы можем найти переменные-члены и прототипы методов (объявления).

Переменные-члены являются частными, два указателя узлов (голова и хвост), где голова является первым и началом связанного списка, а хвост является последним элементом. Оба назначены nullptr, чтобы избежать проблем с памятью. В качестве дополнительной функциональности мы добавим способ отслеживать длину (количество элементов или узлов) связанного списка, частное целое число, в котором будет храниться количество узлов в списке, инициализированном равным 0.

Методы-члены; у нас есть 2 конструктора, один без параметров, а другой со значением template‹class Type›,эти данные Type позволяют добавить любой тип данных, которые должны содержаться в списке Как я упоминал ранее. Следует отметить, что каждый связанный список должен содержать один и тот же тип данных, например, если список создается для содержания целых чисел, его элементы должны быть целыми числами и никакие другие типы данных не могут быть добавлены, мы должны обрабатывать это с блоками try and catch и созданием исключений, чтобы определение нашего списка стало более надежным для будущего тестирования.

Прежде чем попасть в список, я хотел бы объяснить концепцию обхода или итерации в связанном списке. Для итерации по связанному списку необходимо создать временной указатель, который будет инициализирован до указателя заголовка списка, а затем разыменовывать его с помощью оператора -› или (*) (читать об операторе разыменования), этот указатель будет обращаться к членам головного узла, чтобы получить доступ к * следующий член головы, а затем переназначается на следующий узел, этот процесс повторяется до тех пор, пока не будет достигнут хвост или цель.

Чтобы выполнить полный обход связанного списка, обычно используется цикл while для линейного связанного списка и цикл do-while для кругового связанного списка. Для начала указатель trav(traverser) будет инициализирован {this-›head}, затем будет выполняться итерация с оператором while(trav != nullptr), затем trav будет переназначен trav = trav-›next для перехода к следующему узлу.

Другие методы-члены класса LinkedList‹Type›:

  • append(const Type &data) добавляет новый узел ‹Тип данных› в конец списка (новый хвост). аргумент может быть любым типом данных в зависимости от типа данных, который содержит список, или любого Node‹Type›. Внутри функции ссылка &data обернута типом данных Node, который мы определили в начале статьи. Функция Node *temp‹Type› = new Node‹Type›{ data}; создает узел для переноса значения данных при ссылке на него (читайте об операторе new). возвращает логическое значение, если операция прошла успешно.

  • push(Type const &data) вставляет новый узел с данными, переданными в начало списка (новый заголовок), таким же образом он оборачивает данные в узел и назначает этот узел новым глава списка.

  • pop() удаляет последний узел списка. он вызывает деструктор “Node::~Node()” (читайте об операторе удаления). возвращает логическое значение, если операция прошла успешно.
  • pull(), который удаляет первый узел списка и также вызывает деструктор "Node::~Node()". возвращает логическое значение, если операция прошла успешно.

  • printList(), которая выводит список по порядку, вы можете распечатать список в обратном порядке, используя стек, добавляя каждый элемент в стек по мере его перемещения по списку. Хорошим личным проектом будет Smart Pointer для перебора списка и его печати.

Кроме того, определен метод для вставки нового узла по заданному индексу. Этот метод перегружен двумя разными параметрами. Точно так же, как было определено append(), вставки оборачивают данные «Тип» в узел, а затем добавляют их в список за линейное время.

метод deleteAt(int index) удаляет узел с заданным индексом, если индекс превышает длину списка, он возвращает 0 и останавливает процесс.

Наконец, есть 4 геттера для получения головы, хвоста и узла по заданному индексу (getHead(),getTail(), size(), иgetNodeAt(int index)). Эти методы возвращают ссылку на начало, хвост, длину (количество узлов) и узел с заданным индексом.

Родственный метод, мы собираемся реализовать перегрузку оператора индекса массива [] в наш связанный список со временем поиска O(n). C++ — это мощный язык, и многие вещи возможны, воспользовавшись этим, мы реализуем нашу собственную версию индексации в MyLinkedList‹Type›. объявление метода: "Type& operator[](const int index)", а его реализация показана на изображении ниже, вызывает getValueAtIndex(index):

Лучшая часть создания собственного связанного списка заключается в том, что вы можете добавить больше методов и протестировать их, научиться играть с этой структурой данных и выполнять упражнения типа интервью. Наконец, в качестве последнего метода деструктор должен выполнить итерацию по списку, удаляя и присваивая значение NULL каждому следующему указателю каждого узла, вызывая метод clear().

В заключение, создание собственного связанного списка поможет вам понять, как эта важная структура данных работает внутри, и вы сможете получать удовольствие от создания новых методов-членов и идей для улучшения вашего кода. C++ — сложный язык программирования, и, выполняя такие упражнения, вы можете проверьте и улучшите свои навыки работы с C++ и узнайте, какие возможности предлагает объектно-ориентированная функциональность C++ (шаблоны, виртуальные функции, перегрузка операторов, исключения, отношения объектов, динамическое приведение типов и т. д.).

В качестве рекомендации: попробуйте выполнить эти упражнения, чтобы подготовиться к собеседованиям в Google, Amazon, Facebook или Apple. Кроме того, внедрите новый класс интеллектуальных указателей, чтобы повысить надежность и улучшить управление памятью в своем списке. Используйте виртуальные функции для создания интерфейсов, а затем внедряйте их (наследование для C++) в различные типы связанных списков, которые вы можете создать, например, двухсвязный список и >Круговой двусвязный список.

Спасибо, это репозиторий со всем кодом.