No Image

Тип данных list это односвязный список

СОДЕРЖАНИЕ
885 просмотров
10 марта 2020

Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка. [1] Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера [2] , а порядок обхода списка всегда явно задаётся его внутренними связями.

Содержание

Виды связных списков [ править | править код ]

Линейный связный список [ править | править код ]

Односвязный список (однонаправленный связный список) [ править | править код ]

Линейный однонаправленный список — это структура данных, состоящая из элементов одного типа, связанных между собой последовательно посредством указателей. Каждый элемент списка имеет указатель на следующий элемент. Последний элемент списка указывает на NULL. Элемент, на который нет указателя, является первым (головным) элементом списка. Здесь ссылка в каждом узле указывает на следующий узел в списке. В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента, опираясь на содержимое текущего узла, невозможно.

В информатике линейный список обычно определяется как абстрактный тип данных (АТД), формализующий понятие упорядоченной коллекции данных. На практике линейные списки обычно реализуются при помощи массивов и связных списков. Иногда термин «список» неформально используется также как синоним понятия «связный список». К примеру, АТД нетипизированного изменяемого списка может быть определён как набор из конструктора и основных операций:

  • Операция, проверяющая список на пустоту.
  • Три операции добавления объекта в список (в начало, конец или внутрь после любого (n-го) элемента списка);
  • Операция, вычисляющая первый (головной) элемент списка;
  • Операция доступа к списку, состоящему из всех элементов исходного списка, кроме первого.

Характеристики [ править | править код ]

  • Длина списка. Количество элементов в списке.
  • Списки могут быть типизированными или нетипизированными. Если список типизирован, то тип его элементов задан, и все его элементы должны иметь типы, совместимые с заданным типом элементов списка. Чаще списки типизированы.
  • Список может быть сортированным или несортированным.
  • В зависимости от реализации может быть возможен произвольный доступ к элементам списка.

Односвязный список в языках программирования [ править | править код ]

применение односвязного списка:

Двусвязный список (двунаправленный связный список) [ править | править код ]

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

XOR-связный список [ править | править код ]

Кольцевой связный список [ править | править код ]

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

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

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

Список с пропусками [ править | править код ]

Развёрнутый связный список [ править | править код ]

Достоинства [ править | править код ]

  • эффективное (за константное время) добавление и удаление элементов
  • размер ограничен только объёмом памяти компьютера и разрядностью указателей
  • динамическое добавление и удаление элементов

Недостатки [ править | править код ]

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

  • сложность прямого доступа к элементу, а именно определения физического адреса по его индексу (порядковому номеру) в списке
  • на поля-указатели (указатели на следующий и предыдущий элемент) расходуется дополнительная память (в массивах, например, указатели не нужны)
  • некоторые операции со списками медленнее, чем с массивами, так как к произвольному элементу списка можно обратиться, только пройдя все предшествующие ему элементы
  • соседние элементы списка могут быть распределены в памяти нелокально, что снизит эффективность кэширования данных в процессоре
  • над связными списками, по сравнению с массивами, гораздо труднее (хоть и возможно) производить параллельные векторные операции, такие, как вычисление суммы: накладные расходы на перебор элементов снижают эффективность распараллеливания
    Переводы, 5 августа 2015 в 16:00

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

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

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

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

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

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

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

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

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

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

Поскольку в требованиях указано, что считанные числа передаются в метод 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) времени.

Второй метод заключается в сохранении указателя на последний узел списка, и тогда при добавлении нового узла мы поменяем указатель так, чтобы он указывал на новый узел. Этот способ предпочтительней, поскольку выполняется за 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 , пользователь нашего списка сможет реализовать множество различных алгоритмов.

Читайте также:  Программа для чтения flac

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

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

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

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

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

Введение. Основные операции

О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на следующий элемент. Последний элемент списка ссылается на NULL.

Для нас односвязный список полезен тем, что

  • 1) Он очень просто устроен и все алгоритмы интуитивно понятны
  • 2) Односвязный список – хорошее упражнение для работы с указателями
  • 3) Его очень просто визаулизировать, это позволяет "в картинках" объяснить алгоритм
  • 4) Несмотря на свою простоту, односвязные списки часто используются в программировании, так что это не пустое упражнение.
  • 5) Эта структуру данных можно определить рекурсивно, и она часто используется в рекурсивных алгоритмах.

Для простоты рассмотрим односвязный список, который хранит целочисленное значение.

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

Чтобы не писать каждый раз struct мы определили новый тип.
Теперь наша задача написать функцию, которая бы собирала список из значений, которые мы ей передаём. Стандартное имя функции – push, она должна получать в качестве аргумента значение, которое вставит в список. Новое значение будет вставляться в начало списка. Каждый новый элемент списка мы должны создавать на куче. Следовательно, нам будет удобно иметь один указатель на первый элемент списка.

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

  • 1) Выделить под него память.
  • 2) Задать ему значение
  • 3) Сделать так, чтобы он ссылался на предыдущий элемент (или на NULL, если его не было)
  • 4) Перекинуть указатель head на новый узел.

1) Создаём новый узел

2) Присваиваем ему значение

3) Присваиваем указателю tmp адрес предыдущего узла

4) Присваиваем указателю head адрес нового узла

5) После выхода из функции переменная tmp будет уничтожена. Получим список, в который будет вставлен новый элемент.

Так как указатель head изменяется, то необходимо передавать указатель на указатель.

Теперь напишем функцию pop: она удаляет элемент, на который указывает head и возвращает его значение.

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

Уже после этого можно удалить первый элемент и вернуть его значение

Не забываем, что необходимо проверить на NULL голову.

Таким образом, мы реализовали две операции push и pop, которые позволяют теперь использовать односвязный список как стек. Теперь добавим ещё две операции – pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.

Для дальнейшего разговора необходимо реализовать функции getLast, которая возвращает указатель на последний элемент списка, и nth, которая возвращает указатель на n-й элемент списка.

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

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

Для нахождение последнего элемента будем передирать друг за другом элементы до тех пор, пока указатель next одного из элементов не станет равным NULL

Теперь добавим ещё две операции – pushBack (её ещё принято называть shift или enqueue), которая добавляет новый элемент в конец списка, и функцию popBack (unshift, или dequeue), которая удаляет последний элемент списка и возвращает его значение.

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

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

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

Удаление последнего элемента и вставка в конец имеют сложность O(n).

Можно написать алгоритм проще. Будем использовать два указателя. Один – текущий узел, второй – предыдущий. Тогда можно обойтись без вызова функции getLastButOne:

Теперь напишем функцию insert, которая вставляет на n-е место новое значение. Для вставки, сначала нужно будет пройти до нужного узла, потом создать новый элемент и поменять указатели. Если мы вставляем в конец, то указатель next нового узла будет указывать на NULL, иначе на следующий элемент

Покажем на рисунке последовательность действий

После этого делаем так, чтобы новый элемент ссылался на следующий после n-го

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

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