No Image

Реализация связного списка c

СОДЕРЖАНИЕ
494 просмотров
10 марта 2020
    Переводы, 5 августа 2015 в 16:00

Первая структура данных, которую мы рассмотрим — связный список. На то есть две причины: первое — связный список используется практически везде — от ОС до игр, и второе — на его основе строится множество других структур данных.

Связный список

Основное назначение связного списка — предоставление механизма для хранения и доступа к произвольному количеству данных. Как следует из названия, это достигается связыванием данных вместе в список.

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

Как показано на рисунке, данные в массиве хранятся в непрерывном участке памяти, разделенном на ячейки определенного размера. Доступ к данным в ячейках осуществляется по ссылке на их расположение — индексу.

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

19 ноября 2019 – 10 января 2020, Гусев и онлайн, беcплатно

Тем не менее, иногда массив — не самая подходящая структура.

Предположим, что у нашей программы следующие требования:

  • Прочесть некоторое количество целых чисел из источника (метод NextValue ), пока не встретится число 0xFFFF .
  • Передать считанные числа в метод ProcessItems

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

У этого решения есть ряд проблем, но самая очевидная из них — что случится, если будет необходимо прочесть больше 20 значений? В данной реализации значения с 21 и далее просто проигнорируются. Можно выделить больше памяти — 200 или 2000 элементов. Можно дать пользователю возможность выбрать размер массива. Или выделить память под новый массив большего размера при заполнении старого и скопировать элементы. Но все эти решения усложняют код и бесполезно тратят память.

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

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

Обратите внимание: проблем, присущих первому варианту решения больше нет — мы не можем выделить недостаточно или, наоборот, слишком много памяти под массив.

Кроме того, из этого кода можно увидеть, что наш список будет принимать параметр типа и реализовывать интерфейс IEnumerable

Реализация класса LinkedList

Класс Node

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

В самом простом случае класс Node можно реализовать так:

Теперь мы можем создать примитивный связный список. Выделим память под три узла ( first , middle , last ) и соединим их последовательно:

Теперь у нас есть список из трех элементов, начиная с first и заканчивая last . Поле Next последнего узла имеет значение null , что показывает, что это последний элемент. С этим списком уже можно производить различные операции. Например, напечатать данные из каждого элемента:

Метод PrintList итерируется по элементам списка: печатает значение поля Value и переходит к следующему узлу по ссылке в поле Next .

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

Класс LinkedList

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

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

Поскольку мы используем платформу .NET, имеет смысл реализовать наш класс таким образом, чтобы его поведение было похоже на поведение встроенных коллекций. Самый простой способ сделать это — реализовать интерфейс ICollection . Заметьте, что мы реализуем ICollection , а не Ilist , поскольку интерфейс Ilist позволяет получать доступ к элементам по индексу. Несмотря на то, что произвольный доступ к элементам в целом полезен, его невозможно эффективно реализовать в связном списке.

Учитывая все вышесказанное, давайте набросаем примерный план класса, а затем заполним недостающие методы.

Метод Add

  • Поведение: Добавляет элемент в конец списка.
  • Сложность: O(1)

Добавление элемента в связный список производится в три этапа:

  1. Создать экземпляр класса LinkedListNode .
  2. Найти последний узел списка.
  3. Установить значение поля Next последнего узла списка так, чтобы оно указывало на созданный узел.

Основная сложность заключается в том, чтобы найти последний узел списка. Можно сделать это двумя способами. Первый — сохранять указатель на первый узел списка и перебирать узлы, пока не дойдем до последнего. В этом случае нам не требуется сохранять указатель на последний узел, что позволяет использовать меньше памяти (в зависимости от размера указателя на вашей платформе), но требует прохода по всему списку при каждом добавлении узла. Это значит, что метод Add займет O(n) времени.

Читайте также:  Recovery your pc needs to be repaired

Второй метод заключается в сохранении указателя на последний узел списка, и тогда при добавлении нового узла мы поменяем указатель так, чтобы он указывал на новый узел. Этот способ предпочтительней, поскольку выполняется за O(1) времени.

Первое, что нам необходимо сделать — добавить два приватных поля в класс LinkedList : ссылки на первый (head) и последний (tail) узлы.

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

Сначала мы создаем экземпляр класса LinkedListNode . Затем проверяем, является ли список пустым. Если список пуст, мы просто устанавливаем значения полей _head и _tail так, чтобы они указывали на новый узел. Этот узел в данном случае будет являться одновременно и первым, и последним в списке. Если список не пуст, узел добавляется в конец списка, а поле _tail теперь указывает на новый конец списка.

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

Метод Remove

  • Поведение: Удаляет первый элемент списка со значением, равным переданному. Возвращает true , если элемент был удален и false в противном случае.
  • Сложность: O(n)

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

После удаления узла поле Next узла со значением «2» будет указывать на узел со значением «4».

Основной алгоритм удаления элемента такой:

  1. Найти узел, который необходимо удалить.
  2. Изменить значение поля Next предыдущего узла так, чтобы оно указывало на узел, следующий за удаляемым.

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

  • Список может быть пустым, или значение, которое мы передаем в метод может не присутствовать в списке. В этом случает список останется без изменений.
  • Удаляемый узел может быть единственным в списке. В этом случае мы установим значения полей _head и _tail равными null .
  • Удаляемый узел будет в начале списка. В этом случае мы записываем в _head ссылку на следующий узел.
  • Удаляемый узел будет в середине списка.
  • Удаляемый узел будет в конце списка. В этом случае мы записываем в _tail ссылку на предпоследний узел, а в его поле Next записываем null .

Поле Count декрементируется при удалении узла.

Метод Contains

  • Поведение: Возвращает true или false в зависимости от того, присутствует ли искомый элемент в списке.
  • Сложность: O(n)

Метод Contains достаточно простой. Он просматривает каждый элемент списка, от первого до последнего, и возвращает true как только найдет узел, чье значение равно переданному параметру. Если такой узел не найден, и метод дошел до конца списка, то возвращается false .

Метод GetEnumerator

  • Поведение: Возвращает экземпляр IEnumerator , который позволяет итерироваться по элементам списка.
  • Сложность: Получение итератора — O(1). Проход по всем элементам — O(n).

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

Метод Clear

  • Поведение: Удаляет все элементы из списка.
  • Сложность: O(1)

Метод Clear просто устанавливает значения полей _head и _tail равными null . Поскольку C# — язык с автоматическим управлением памятью, нет необходимости явно удалять неиспользуемые узлы. Клиент, вызывающий метод, должен убедиться в корректном удалении значений узлов, если это необходимо.

Метод CopyTo

  • Поведение: Копирует содержимое списка в указанный массив, начиная с указанного индекса.
  • Сложность: O(n)

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

Метод Count

  • Поведение: Возвращает количество элементов списка. Возвращает 0, если список пустой.
  • Сложность: O(1)

Count — поле с публичным геттером и приватным сеттером. Изменение его значения осуществляется в методах Add , Remove и Clear .

Метод IsReadOnly

  • Поведение: Возвращает true , если список только для чтения.
  • Сложность: O(1)

Двусвязный список

Связный список, который мы только что создали, называется также «односвязным». Это значит, что между узлами только одна связь в единственном направлении от первого узла к последнему. Есть также достаточно распространенный вариант списка, который предоставляет доступ к обоим концам — двусвязный список.

Читайте также:  Почему не открываются видео на телефоне

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

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

Класс Node

Единственное изменение, которое надо внести в класс LinkedListNode — добавить поле со ссылкой на предыдущий узел.

Метод AddFirst

В то время, как односвязный список позволяет добавлять элементы только в конец, используя двусвязный список мы можем добавлять элементы как в начало, так и в конец, с помощью методов AddFirst и AddLast соответственно. Метод ICollection .Add будет вызывать AddLast для совместимости с односвязным списком.

  • Поведение: Добавляет переданный элемент в начало списка.
  • Сложность: O(1)

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

  1. Установить значение поля Next в новом узле так, чтобы оно указывало на бывший первый узел.
  2. Установить значение поля Previous в бывшем первом узле так, чтобы оно указывало на новый узел.
  3. Обновить поле _tail при необходимости и инкрементировать поле Count

Метод AddLast

  • Поведение: Добавляет переданный элемент в конец списка.
  • Сложность: O(1)

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

Как было сказано ранее, ICollection .Add просто зовет AddLast .

Метод RemoveFirst

Как и метод Add , Remove будет разделен на два метода, позволяющих удалять элементы из начала и из конца списка. Метод ICollection .Remove будет также удалять элементы из начала, но теперь будет еще обновлять поля Previous в тех узлах, где это необходимо.

  • Поведение: Удаляет первый элемент списка. Если список пуст, не делает ничего. Возвращает true , если элемент был удален и false в противном случае.
  • Сложность: O(1)

RemoveFirst устанавливает ссылку head на второй узел списка и обнуляет поле Previous этого узла, удаляя таким образом все ссылки на предыдущий первый узел. Если список был пуст или содержал только один элемент, то поля _head и _tail становятся равны null .

Метод RemoveLast

  • Поведение: Удаляет последний элемент списка. Если список пуст, не делает ничего. Возвращает true , если элемент был удален и false в противном случае.
  • Сложность: O(1)

RemoveLast устанавливает значение поля _tail так, чтобы оно указывало на предпоследний элемент списка и, таким образом, удаляет последний элемент. Если список был пустым, или содержал только один элемент, то поля _head и _tail становятся равны null .

Метод Remove

  • Поведение: Удаляет первый элемент списка со значением, равным переданному. Возвращает true , если элемент был удален и false в противном случае.
  • Сложность: O(n)

Метод ICollection .Remove() почти такой же, как и в односвязном списке. Единственное отличие — теперь нам необходимо поменять значение поля Previous при удалении узла. Для того, чтобы не повторять код, этот метод зовет RemoveFirst при удалении первого узла.

Зачем нужен двусвязный список?

Итак, мы можем добавлять элементы в начало списка и в его конец. Что нам это дает? В том виде, в котором он реализован сейчас, нет особых преимуществ перед обычным односвязным списком. Но если добавить геттеры для полей head и tail , пользователь нашего списка сможет реализовать множество различных алгоритмов.

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

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

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

Продолжение следует

На этом мы заканчиваем разбор связных списков. В следующий раз мы подробно разберем строение векторов (array list).

Связный список

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

Таким образом, если в массиве положение элементов определяется индексами, то в связном списке – указателями на следующий и (или) на предыдущий элемент.

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

Читайте также:  Автомобильные компрессоры отзывы рейтинг

Перед созданием списка нам надо определить класс узла, который будет представлять одиночный объект в списке:

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

Далее определим сам класс списка:

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

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

Если у нас не установлена переменная head (то есть список пуст), то устанавливаем head и tail. После добавления первого элемента они будут указывать на один и тот же объект.

Если же в списке есть как минимум один элемент, то устанавливаем свойство tail.Next – теперь оно хранит ссылку на новый узел. И переустанавливаем tail – теперь она ссылается на новый узел.

Сложность данного метода составляет O(1) . Графически это выглядит так:

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

Данный способ вполне рабочий и нередко встречается, однако необходимость перебора элементов для нахождения последнего увеличивает время на поиск и сложность алгоритма. Она равна O(n) .

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

Алгоритм удаления элемента представляет следующую последовательность шагов:

Поиск элемента в списке путем перебора всех элементов

Установка свойства Next у предыдущего узла (по отношению к удаляемому) на следующий узел по отношению к удаляемому.

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

Если же previous не равна null, то реализуются шаги выше описанного алгоритма.

Сложность такого алгоритма составляет O(n) . Графически удаление можно представить так:

Чтобы проверить наличие элемента, исползуется метод Contains:

Здесь опять же просто осуществляется перебор. Сложность алгоритма метода составляет O(n) .

И для того, чтобы список можно было бы перебрать во внешней прграмме с помощью цикла for-each, класс списка реализует интерфейс IEnumerable :

Реализация данного интерфейса не является неотъемлимой частью односвязных списков, однако предоставляет эффективный метод для перебора коллекции в цикле foreach. Иначе нам бы пришлось реализовать какие-то собственные конструкции по перебору списка.

Опубликовано shwan в 12.03.2018 12.03.2018

Связный список C# — Linked List C# представляет собой коллекцию связанных элементов, которые содержат в себе хранимые данные, а также ссылку на связанные с ним элементы (один или несколько). Основным преимуществом данной структуры данных перед обычным массивом является ее динамичность — возможность легко менять количество элементов. Давайте рассмотрим пример реализации на языке C# элементарного односвязного списка.

Архитектура Связного списка (Linked List)

Для начала необходимо упомянуть, что существует несколько видов связных списков. Вот наиболее часто используемые из них:

  • Односвязный список
  • Двусвязный список
  • Кольцевой список

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

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

Реализация Связного списка (Linked List) на языке C#

В качестве примера рассмотрим тривиальную реализацию односвязного списка.

Элемент списка

Рассмотрим класс элемента связного списка. Для того, чтобы сделать его более универсальным мы используем Универсальный параметр T. Это позволит динамически указывать тип данных при использовании списка.

Список элементов

Теперь рассмотрим сам класс связного списка. Для него мы также используем Универсальный (generic) тип T, а также реализуем интерфейс IEnumerable, чтобы в дальнейшем было удобно перебирать элементы списка с помощью цикла foreach.

Использование

Ну и наконец нам остается проверить работу нашего списка. Для этого создадим несколько элементов и проверим работу списка.

Заключение по теме Связный Список C#

Здесь представлена элементарная реализация данной динамической структуры данных. На практике она уже реализована намного лучше внутри платформы .NET в виде списка LinkedList , но для того, чтобы понять внутреннюю структуру лучше рассматривать более простые примеры. Исходный код доступен в репозитории github https://github.com/shwanoff/LinkedList

Также рекомендую изучить статью Список C# | List C# . А еще подписывайтесь на группу ВКонтакте, Telegram и YouTube-канал. Там еще больше полезного и интересного для программистов.

Комментировать
494 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock
detector