Структура данных связного списка в C++

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

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

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

На следующей схеме показана структура односвязного списка:

Структура односвязного списка

Как показано выше, первый узел связанного списка называется “head” (голова), а последний узел называется “Tail» (хвост). Как вы можете видеть, последний узел связанного списка будет иметь свой следующий указатель как null (ноль), поскольку на него не будет указан какой-либо адрес памяти.

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

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

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

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

Операции

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

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

Читать также:  Константы в С++

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

Вставка

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

Следующее, что мы должны учитывать, это место, куда должен быть добавлен новый элемент данных.

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

1) В начало связного списка

Связный список показан ниже 2->4->6->8->10. Если мы хотим добавить новый узел 1 в качестве первого узла списка, то заголовок, указывающий на узел 2, теперь будет указывать на 1, а следующий указатель узла 1 будет иметь адрес памяти узла 2, как показано на схеме ниже:

В начало связного списка

Таким образом, новый связный список становится 1->2->4->6->8->10.

2) После заданного узла

Допустим, указан узел, и мы должны добавить новый узел после данного узла. В приведенном ниже связном списке a->b-> c-> d -> e, если мы хотим добавить узел f после узла c, тогда связный список будет выглядеть следующим образом:

После заданного узла

Таким образом, на приведенной выше схеме мы проверяем, присутствует ли данный узел. Если он присутствует, мы создаем новый узел f. Затем мы указываем следующий указатель узла c, чтобы указать на новый узел f. Следующий указатель узла f теперь указывает на узел d.

3) В конце связного списка

В третьем случае мы добавляем новый узел в конец связного списка. Допустим, что у нас есть тот же связный список a-> b-> c-> d-> e, и нам нужно добавить узел f в конец списка. После добавления узла связный список будет выглядеть так, как показано ниже:

В конце связного списка

Таким образом, мы создаем новый узел f. Затем указатель хвоста, указывающий на null, указывает на f, а следующий указатель узла f указывает на null. Мы реализовали все три типа функций вставки в приведенной ниже программе на C ++.

В C ++ мы можем объявить связный список как структуру или как класс. Объявление связного списка как структуры является традиционным объявлением в стиле C. Связный список как класс используется в современном C ++, в основном при использовании стандартной библиотеки шаблонов.

Читать также:  Функции классификации и преобразования символов С++

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

Вывод данных:

Окончательный связный список:
30–>20–>50–>10–>40–> нулевой

Далее мы реализуем операцию вставки связного списка в Java. На языке Java связный список реализован как класс. Приведенная ниже программа похожа по логике на программу на C ++, единственное отличие состоит в том, что мы используем в ней класс для связного списка.

Вывод данных:

Окончательный связный список:
10–>20–>30–>40–>50–> null

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

2) Удаление

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

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

Вывод данных:

Созданный связный список
10–>8–>6–>4–>2–> NULL
Связный список после удаления головного узла
8–>6–>4–>2–> NULL
Связный список после удаления последнего узла
8–>6–> 4–> NULL

Далее приведена реализация Java для удаления узлов из связного списка. Логика реализации та же, что используется в программе на C ++. Единственное отличие заключается в том, что связный список объявляется как класс:

Вывод данных:

Созданный связный список :
9–>7–>5–>3–>1–> null
Связный список после удаления головного узла :
7–>5–>3–>1–> null
Связный список после удаления последнего узла :
7–>5–> 3–> null

Подсчитайте количество узлов

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

Читать также:  Ссылки в С++

Сохранение счетчика и его увеличение по мере прохождения каждого узла даст нам подсчет количества узлов, присутствующих в связном списке.

Массивы и связные списки

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

Массивы Связные списки
Массивы имеют фиксированный размер Размер связного списка является динамическим
Вставка нового элемента занимает много времени Вставка / удаление проще
Разрешен произвольный доступ Произвольный доступ невозможен
Элементы находятся в смежном расположении Элементы имеют несмежное расположение
Для следующего указателя не требуется дополнительного места Для следующего указателя требуется дополнительное пространство памяти

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

Вот некоторые примеры применения связных списков:

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

Итог

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

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

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

С Уважением, МониторБанк

Добавить комментарий