Что такое списки данных
Список
Связный список (англ. List) — структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.
Содержание
Односвязный список [ править ]
Простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.
Двусвязный список [ править ]
Также хранится указатель на предыдущий элемент списка, благодаря чему становится проще удалять и переставлять элементы.
XOR-связный список [ править ]
В некоторых случаях использование двусвязного списка в явном виде является нецелесообразным. В целях экономии памяти можно хранить только результат выполнения операции Xor над адресами предыдущего и следующего элементов списка. Таким образом, зная адрес предыдущего элемента, мы можем вычислить адрес следующего элемента.
Циклический список [ править ]
Первый элемент является следующим для последнего элемента списка.
Операции на списке [ править ]
Рассмотрим базовые операции на примере односвязного списка.
Вставка [ править ]
Очевиден случай, когда необходимо добавить элемент ( [math]newHead[/math] ) в голову списка. Установим в этом элементе ссылку на старую голову, и обновим указатель на голову.
Поиск [ править ]
Удаление [ править ]
Для того, чтобы удалить голову списка, переназначим указатель на голову на второй элемент списка, а голову удалим.
Удаление элемента после заданного ( [math]thisElement[/math] ) происходит следующим образом: изменим ссылку на следующий элемент на следующий за удаляемым, затем удалим нужный объект.
Поиск цикла в списке [ править ]
Для начала необходимо уметь определять — список циклический или нет. Воспользуемся алгоритмом Флойда «Черепаха и заяц». Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
Поиск длины хвоста в списке с циклом [ править ]
Наивные реализации [ править ]
Реализация за [math]O(n^2)[/math] [ править ]
Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от [math]pointMeeting[/math] вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит [math]pointMeeting[/math] снова, то точку окончания (начала) хвоста нашли.
Реализация за [math]O(n \log n)[/math] [ править ]
Эффективная реализация [ править ]
Доказательство корректности алгоритма [ править ]
[math]f_1(n) = L + (n-L) \bmod N[/math]
[math]f_2(n) = L + (2n-L) \bmod N[/math]
[math]Q = L + (1-k) N[/math]
Пусть [math]L = p N + M, 0 \leqslant M \lt N[/math]
[math]L \lt k N \leqslant L + N[/math]
[math]pN + M \lt kN \leqslant (p+1)N + M[/math] откуда [math]k = p + 1[/math]
Задача про обращение списка [ править ]
Для того, чтобы обратить список, необходимо пройти по всем элементам этого списка, и все указатели на следующий элемент заменить на предыдущий. Эта рекурсивная функция принимает указатель на голову списка и предыдущий элемент (при запуске указывать [math]NULL[/math] ), а возвращает указатель на новую голову списка.
Алгоритм корректен, поскольку значения элементов в списке не изменяются, а все указатели [math]next[/math] изменят свое направление, не нарушив связности самого списка.
Списки и словари в Python. Разница и смысл
Доброго времени суток, питонисты!
Сейчас постараюсь подробно разобрать списки и словари в Python, объясню смысл их использования, и разберём их различия, а в конце подведём итог.
Списки
Что такое список?
Список это вид переменной у которой сразу несколько значений. Значения могут быть разных типов, например в одном списке может быть как и int(целое число) так и float(число с плавающей точкой) и до кучи к ним ещё и string(строка, буквы). Все данные в списке упорядоченные индексацией.
Как сделать список?
Список в коде создаётся таким путём:
my_list = [данные, через, запятую]
Числа в список забивать нужно без кавычек, а строки с одинарными либо двойными, разницы нет. Но если у вас в строке есть двойные кавычки, то обозначать строку нужно одинарными кавычками, и наоборот. В противном случае, компилятор просто потеряется и выдаст ошибку. Числа с плавающей точкой пишите именно с точкой, хоть за ошибку считаться не будет, но большинство программистов используют именно точку. В списке может быть список, а в нём словарь и так далее…
Как работать с определённым элементом в списке?
Допустим мы хотим вывести на экран определённый элемент из списка. Возьмём 3-й. А запишем в коде мы это так:
В прочем работа с определённым элементом из списка идентична работе с переменной, поэтому мы её разбирать не будем.
Как работать с самим списком?
Существует множество функций по работе со списками. Их вы можете найти по ссылке: тык. Сейчас мы разберём поисковые методы.
Таблица поисковых методов
my_list.append(x)
Добавляет элемент в конец списка
list.extend(L)
Расширяет список my_list, добавляя в конец все элементы списка L
my_list.insert(i, x)
Вставляет на i-ый элемент значение x
my_list.remove(x)
Удаляет первый элемент в списке, имеющий значение x. ValueError, если такого элемента не существует
my_list.index(x, [start [, end]])
Возвращает положение первого элемента со значением x (при этом поиск ведется от start до end)
my_list.count(x)
Возвращает количество элементов со значением x
my_list.sort(Что такое списки данных)
Сортирует список на основе функции
my_list.reverse()
my_list.copy()
Поверхностная копия списка
my_list.clear()
Сохранение результата выполнения поискового метода в переменную выполняется следующим образом:
Если мы сортируем список и сохраняем новый список в переменную то
будет ошибкой. Правильнее будет сначала выполнить сортировку, а уже сортированный список сохранить в переменную
Словари
Что такое словарь?
Как создать словарь?
Словари в Python объявляются таким путём:
Как работать с определённым элементом словаря?
Вывести определённый элемент из словаря на экран можно вот так:
Сейчас мы вывели значение элемента в словаре с ключем ‘key1’.
Как работать с самим словарем?
Таблица методов для работы со словарями
my_dict.clear()
my_dict.copy()
Возращает копию словаря
my_dict.get(key[, default])
Возвращает значение ключа, но если его нет, не бросает исключение, а возвращает default (по умолчанию None)
my_dict.items()
Возвращает пары (ключ, значение)
my_dict.keys()
my_dict.pop(key[, default])
Удаляет ключ и возвращает значение. Если ключа нет, возвращает default (по умолчанию бросает исключение).
my_dict.popitem()
Удаляет пару (ключ, значение). Если словарь пуст, бросает исключение KeyError. Помните, что словари неупорядочены
my_dict.values()
Возвращает значения из словаря
Подведём итоги
Алгоритмы и структуры данных для начинающих: связный список
Первая структура данных, которую мы рассмотрим — связный список. На то есть две причины: первое — связный список используется практически везде — от ОС до игр, и второе — на его основе строится множество других структур данных.
Связный список
Основное назначение связного списка — предоставление механизма для хранения и доступа к произвольному количеству данных. Как следует из названия, это достигается связыванием данных вместе в список.
Прежде чем мы перейдем к рассмотрению связного списка, давайте вспомним, как хранятся данные в массиве.
Как показано на рисунке, данные в массиве хранятся в непрерывном участке памяти, разделенном на ячейки определенного размера. Доступ к данным в ячейках осуществляется по ссылке на их расположение — индексу.
27–29 декабря, Онлайн, Беcплатно
Это отличный способ хранить данные. Большинство языков программирования позволяют так или иначе выделить память в виде массива и оперировать его содержимым. Последовательное хранение данных увеличивает производительность (data locality), позволяет легко итерироваться по содержимому и получать доступ к произвольному элементу по индексу.
Тем не менее, иногда массив — не самая подходящая структура.
Предположим, что у нашей программы следующие требования:
Поскольку в требованиях указано, что считанные числа передаются в метод ProcessItems за один раз, очевидным решение будет массив целых чисел:
У этого решения есть ряд проблем, но самая очевидная из них — что случится, если будет необходимо прочесть больше 20 значений? В данной реализации значения с 21 и далее просто проигнорируются. Можно выделить больше памяти — 200 или 2000 элементов. Можно дать пользователю возможность выбрать размер массива. Или выделить память под новый массив большего размера при заполнении старого и скопировать элементы. Но все эти решения усложняют код и бесполезно тратят память.
Нам нужна коллекция, которая позволяет добавить произвольное число элементов и перебрать их в порядке добавления. Размер коллекции должен быть неограничен, а произвольный доступ нам не нужен. Нам нужен связный список.
Прежде чем перейти к его реализации, давайте посмотрим на то, как могло бы выглядеть решение нашей задачи.
Обратите внимание: проблем, присущих первому варианту решения больше нет — мы не можем выделить недостаточно или, наоборот, слишком много памяти под массив.
Кроме того, из этого кода можно увидеть, что наш список будет принимать параметр типа и реализовывать интерфейс IEnumerable
Реализация класса LinkedList
Класс Node
В основе связного списка лежит понятие узла, или элемента (Node). Узел — это контейнер, который позволяет хранить данные и получать следующий узел.
В самом простом случае класс Node можно реализовать так:
Класс LinkedList
Прежде чем реализовывать наш связный список, нужно понять, как мы будем с ним работать.
Ранее мы увидели, что коллекция должна поддерживать любой тип данных, а значит, нам нужно реализовать обобщенный интерфейс.
Учитывая все вышесказанное, давайте набросаем примерный план класса, а затем заполним недостающие методы.
Метод Add
Добавление элемента в связный список производится в три этапа:
Основная сложность заключается в том, чтобы найти последний узел списка. Можно сделать это двумя способами. Первый — сохранять указатель на первый узел списка и перебирать узлы, пока не дойдем до последнего. В этом случае нам не требуется сохранять указатель на последний узел, что позволяет использовать меньше памяти (в зависимости от размера указателя на вашей платформе), но требует прохода по всему списку при каждом добавлении узла. Это значит, что метод Add займет O(n) времени.
Второй метод заключается в сохранении указателя на последний узел списка, и тогда при добавлении нового узла мы поменяем указатель так, чтобы он указывал на новый узел. Этот способ предпочтительней, поскольку выполняется за O(1) времени.
Первое, что нам необходимо сделать — добавить два приватных поля в класс LinkedList : ссылки на первый (head) и последний (tail) узлы.
Теперь мы можем добавить метод, который выполняет три необходимых шага.
Метод Remove
После удаления узла поле Next узла со значением «2» будет указывать на узел со значением «4».
Основной алгоритм удаления элемента такой:
Как всегда, основная проблема кроется в мелочах. Вот некоторые из случаев, которые необходимо предусмотреть:
Поле Count декрементируется при удалении узла.
Метод Contains
Метод GetEnumerator
Метод Clear
Метод CopyTo
Метод CopyTo проходит по списку и копирует элементы в массив с помощью присваивания. Клиент, вызывающий метод должен убедиться, что массив имеет достаточный размер для того, чтобы вместить все элементы списка.
Метод Count
Метод IsReadOnly
Двусвязный список
Связный список, который мы только что создали, называется также «односвязным». Это значит, что между узлами только одна связь в единственном направлении от первого узла к последнему. Есть также достаточно распространенный вариант списка, который предоставляет доступ к обоим концам — двусвязный список.
Далее мы рассмотрим только отличия в реализации односвязного и двусвязного списка.
Класс Node
Единственное изменение, которое надо внести в класс LinkedListNode — добавить поле со ссылкой на предыдущий узел.
Метод AddFirst
При добавлении элемента в начало списка последовательность действий примерно такая же, как и при добавлении элемента в односвязный список.
Метод AddLast
Метод RemoveFirst
Метод RemoveLast
Метод Remove
Зачем нужен двусвязный список?
Так мы сможем итерироваться по списку вручную, в том числе от последнего элемента к первому.
В этом примере мы используем поля Tail и Previous для того, чтобы обойти список задом наперед.
Кроме того, двусвязный список позволяет легко реализовать двусвязную очередь, которая, в свою очередь, является строительным блоком для других структур данных. Мы вернемся к ней позже, в соответствующей части.
Продолжение следует
На этом мы заканчиваем разбор связных списков. В следующий раз мы подробно разберем массивы.
ТЕМА 4.4. СПИСКИ. ОБРАБОТКА, СОРТИРОВКА И ФИЛЬТРАЦИЯ ТАБЛИЧНЫХ ДАННЫХ. СТРУКТУРИРОВАНИЕ ТАБЛИЦ
Познакомиться с технологиями:
Оглавление
4.4.1. Понятие списка (базы данных)
Многие экономические задачи направлены на обработку больших таблиц, имеющих много столбцов и строк. Таблица данных называется списком, если она обладает следующими свойствами:
При таких условиях список можно считать однотабличной базой данных, поэтому при работе со списком применяют соответствующую терминологию:
Ячейки верхней строки с именами полей образуют область имен полей.
Рис. 1. Структурные элементы списка (базы данных Excel)
Данные всегда располагаются, начиная со следующей строки после области имен полей. Весь блок ячеек с данными называют областью данных.
Список содержит фиксированное количество полей (столбцов), определяющих структуру записи базы данных (строки).
Над записями списка можно выполнять различные операции обработки, команды вызова которых сгруппированы в меню Данные.
4.4.2. Сортировка данных в списке
Сортировка данных является базовой операцией любой таблицы и выполняется командой Данные/Сортировка с установкой необходимых параметров. Целью сортировки является упорядочивание данных. Сортировка осуществляется на том же листе.
В среде Microsoft Excel предусмотрено три уровня сортировки, которые определяются в диалоговом окне Сортировка диапазона (Рис. 2).
В том же окне устанавливается порядок сортировки в столбцах – по возрастанию или убыванию. При сортировке по возрастанию упорядочение идет:
Для столбцов, содержащих разные по формату данные, имеет место приоритет: числа, текст, логические значения, значения ошибок, пустые ячейки. Сортировка по убыванию использует обратный порядок (исключение – пустые ячейки, которые располагаются в конце списка).
Рис. 2. Параметры сортировки
Сортировка по нескольким уровням осуществляется в том случае, если в таблице имеются столбцы, содержащие повторяющиеся значения. Тогда сортировка 1-го уровня осуществляет, по сути, группировку записей с одинаковым значением поля. Сортировка 2-го уровня осуществляет упорядочение данных в группах, полученных после сортировки 1-го уровня. Сортировка 3-го уровня упорядочивает данные в группах, полученных после сортировки 2-го уровня.
При наличии заголовков столбцов (имен полей) их следует исключить из области, подлежащей сортировке. Для этого используется переключатель Идентифицировать поля по подписям.
Кнопка Параметры выводит диалоговое окно Параметры сортировки, в котором задаются дополнительные установки сортировки: с учетом регистра или без учета; по столбцам или по строкам; порядок сортировки – обычный или специальный, выбранный из предлагаемого списка. Этот список можно сформировать самостоятельно с помощью Сервис/Параметры/вкладка Списки.
4.4.3. Фильтрация
Фильтрация данных в списке – это отбор данных по заданному критерию (условию). Осуществляется эта операция с помощью команды Данные/Фильтр. Имеется две разновидности этой команды, задаваемых параметрами: Автофильтр и Расширенный фильтр.
Фильтрация данных может осуществляться с помощью специальной формы, которая вызывается командой Данные/Форма.
4.4.4. Автофильтрация
Команда Данные/Фильтр/Автофильтр для каждого столбца строит список значений, который используется для задания условий фильтрации (Рис. 3). В каждом столбце появляется кнопка списка, нажав которую можно ознакомиться со списком критериев отбора.
Рис. 3. Список с автофильтром
Для каждого столбца в списке критериев отбора предусматриваются следующие варианты:
Рис. 4. Наложение условия по списку
Условие для отбора записей по конкретным значениям в определенном столбце может состоять из двух самостоятельных частей, соединенных логической связкой И/ИЛИ (Рис. 5). Каждая часть условия включает один из операторов отношения:
Рис. 5. Задание условия фильтрации
Примеры условий
Для поля Код предмета можно сформировать условия:
отобрать все записи, которые содержат код предмета, начинающийся с буквы п
отобрать все записи, которые не содержат кода предмета п1
4.4.5. Расширенный фильтр
Инструмент Расширенный фильтр позволяет задать условия отбора для нескольких столбцов независимо друг от друга и осуществить фильтрацию записей. Фильтрация выполняется по всем условиям одновременно. Все записи, не прошедшие через фильтр, будут скрыты.
Расширенный фильтр позволяет задать условия отбора двух типов критериев:
Если критерий фильтрации формируется в нескольких столбцах, его называют множественным критерием.
Технология использования расширенного фильтра состоит из двух этапов:
Технология формирования области условий
Правила формирования Критерия сравнения
2-й способ. Множественный критерий сравнения – условия (точные значения полей) записаны в двух строках (Таблица 3). Номер группы, код предмета и оценка заданы как точные значения. На одной строке указаны оценка «4», на другой – «5». Связка “ИЛИ”.
Таблица 3. Задание множественного критерия. Связка “ИЛИ”
Номер группы
Код предмета
Оценка
Вычисляемый критерий представляет собой формулу в виде логического условия, которая возвращает логическое значение ИСТИНА или ЛОЖЬ. Формула обязательно содержит оператор отношения, который сравнивает некоторые вычисляемые выражения.
Имя столбца, содержащего формулу вычисляемого критерия, должно отличаться от имени столбца в списке.
Пример
Из списка (Рис. 3) выбрать записи о студентах группы 133, получивших оценку ниже общего среднего балла или получивших оценку 5. Пример вычисляемого критерия представлен в таблице (Таблица 4). Столбец Номер группы имеет такое же имя как и столбец в исходном списке, потому что для отбора группы используется критерий сравнения. Имя столбца Оценка1 отличается от имени столбца в исходном списке, т.к. здесь используется вычисляемый критерий.
Таблица 4. 1-й способ задания вычисляемого критерия
Номер группы
Оценка1
Рис. 9. Исходная таблица для автостуктурирования
По каждому виду начислений в строке Итого рассчитывается с помощью функции СУММ общая сумма по ячейкам столбца. Порядок следования исходных данных и результатов (итогов) – слева направо, сверху вниз, позволяет применить автоструктурирование таблицы (Рис. 10).
После ввода в таблицу исходных данных и формул курсор устанавливается в произвольную ячейку списка и выполняется команда Данные/Группа и Структура/Создать структуру. Все структурные части таблицы создаются автоматически.
Рис. 10. Таблица после автоструктурирования
Структурирование таблицы с автоматическим подведением итогов
В среде Excel существует инструмент структурирования с одновременным подведением итогов. Команда Данные/Итоги создает структуру таблицы и одновременно вставляет строки промежуточных и общих итогов для выбранных столбцов в соответствии с заданной функцией (Таблица 8).
Примечание. Для получения итогов по группам следует заранее упорядочить строки списка с помощью команды Данные/Сортировка.
Подведение итогов выполняется при изменении значений в столбце, который образует группы.
Перед подведением итогов надо выполнить сортировку по одному или нескольким полям списка.
Команда Данные/Итоги может выполняться для одного списка многократно. Созданные ранее промежуточные итоги могут как заменяться новыми, так и оставаться неизменными посредством установки или снятия флажка параметра Заменить текущие итоги (Рис. 11). Таким образом, имеется возможность подведения итогов различных уровней вложенности.
Таблица 8. Функции для подведения автоматических итогов
Операция
Значение в строке итогов по группе
Просто о списках, словарях и множествах или ТОП 5 структур данных
Привет. Ей! Не говорите “Да блин! Я знаю, чем отличается список от вектора, мне не нужна эта статья”. Прошу, загляните под кат и освежите свои знания. Я надеюсь, однако, что вы сможете почерпнуть из этой статьи намного больше и, некоторые, возможно, наконец-то разберутся, почему существует так много типов данных для коллекций объектов.
Введение
Так уж сложилось, что в программировании коллекции представляет много, нет ОЧЕНЬ МНОГО различных сущностей — списки, массивы, вектора, множества, стеки, очереди, ассоциативные массивы и у большинства из этих структур данных есть еще по несколько подвидов.
Должны же быть причины, чтобы для простого представления какой-либо совокупности объектов существовало настолько много различных вариаций.
Должны же быть отличия между списком и массивом? Между ассоциативным массивом и хеш-таблицей?
Коллекция
Для начала — самое скучное (да, я люблю такое). Что такое коллекция вообще?
Коллекция — структура данных (тип, класс, даже лучше сказать интерфейс), которая создана, чтобы содержать в себе некоторое количество объектов (в зависимости от языка и терминологии они должны быть одного типа или могут быть разных типов).
Различные типы коллекций могут быть статическими или динамическими, т.е. изменять свой размер или оставаться постоянными, могут быть упорядоченными (точнее учитывающими порядок элементов) и неупорядоченными (соответственно не учитывающими).
Над коллекциями предусмотрено несколько стандартных операций (сейчас мы поговорим о мутабельных, т.е. изменяемых коллекциях), таких как: получение размера, добавление элемента, удаление элемента, поиск (есть какой-либо элемент в коллекции или нет), их очень много.
Ладно, свой негласный долг я выполнил, теперь поехали!
1 Вектор (Vector, Array)
А вы чего ждали?
Вектор (он же одномерный массив) — упорядоченный набор элементов с произвольным доступом по числовому индексу. Что для нас важно в этом определении? Да ничего. Шучу, на самом деле нам важно почти каждое слово:
Доступ к элементам производится по числовому индексу (обычно начиная с 0-го индекса, хотя есть и исключения), обычно доступ к элементу коллекции по индексу записывается как myFavoriteCats[i] или blackKitties[5]. Причем для обозначения этого самого числа — индекса используют букву i.
А когда одной буквы не хватает приплетают сюда j и k.
Итак, далее мы понимаем, что доступ произвольный — значит мы можем обращаться к элементам под индексами 0, 42, 2014 и вобщем-то ожидаем, что операция будет сложности O(1), т.е. константной и независимо от того какой из элементов мы запросим он нам со скоростью света тут же вернется.
Далее — вектор — упорядоченная коллекция, что собственно понятно — у нас есть такие понятия как первый, последний элемент, для каждого конкретно взятого элемента мы также можем назвать предыдущий и следующий.
Релизация
Обычно вектор (как низкоуровневая структура) будет представлять из себя дескриптор, содержащий различную информацию, неотделимую от самой структуры (разумнее всего держать там только размер вектора) и указатель на первый элемент.
Такая реализация позволит за константное время получить доступ к произвольному элементу вектора по его индексу, а также позволит выполнять копирование, конкатенацию и другие простые операции на низком уровне.
И действительно, получить доступ к определенному элементу очень просто — прибавляем к указателю на первый элемент индекс (с некоторыми поправками на размер типа данных) и получаем указатель на нужный элемент! Осталось разыменовать и у нас в переменной нужная кошечка!
Ладно, вектор — классная структура, но и у него есть недостатки (а у кого их нет?!), например нельзя просто так взять и добавить в вектор новый элемент! Особенно втиснуть его в середину. Нельзя также сказать, что кошки с номерами 0, 1 и 4 у нас есть, а с номерами 2 и 3 — нет (раньше они были, но оказалось, что это собаки).
Можно представить себе вектор, как книжную полку с отделениями, в каждом из которых помещается ровно одна книга. Чтобы засунуть новый роман Донцовой между 10-ым и 11-ым томом Большой Совецкой Энциклопедии нужно сильно постараться и переложить все тома с 11-го по 65-ый тома (можно схитрить и поставить 11-ый том в конец, но я вам этого не говорил, да и мы в таком случае потеряем упорядоченность).
В моей памяти все именно так
Применение
В нашем случае вектор бы идеально подошел для топ-10 самых милых котят, т.к. добавлять и удалять элементы не нужно (только изменять), пропусков между 1-ым и 5-ым местом быть не должно, да и удобно обращаться по номеру.
Ладно. В любом случае вектор классный, мы просто посмотрим какие есть еще коллекции.
2 Список (List)
Первый том
Ух! Список задач на сегодня, список покупок в магазине. Список гостей на свадьбу… Так. Ближе к делу.
Мы уже знаем, что элементы вектора лежат акуратненько друг за другом, красиво и ровно. Это дает нам как преимущества так и недостатки.
Список в этом плане полностью противоположная вещь — его элементы могут быть разбросаны по памяти как угодно! Из-за этого мы теряем возможность быстро получить элемент по индексу, а также не можем быстро скопировать весь список, но получаем довольно приятную штуку — мы можем вставлять элементы за константное время в любое место! По слухам удаляются элементы из списка тоже за O(1).
Реализация
Хм. А как с формальным определением?
Список — упорядоченный набор элементов, для каждого из которых хранится указатель на следующий (или для двусвязного списка и на следующий и на предыдущий) элементы списка.
Для последнего элемента списка мы храним нулевой указатель (на диаграммах я буду использовать указатель на нулевую кошку (Null Cat), не пугайтесь).
Внимание! В каноничной реализации списка, для того, чтобы получить размер списка, необходимо обойти весь список — дойдя до нулевого указателя (линейное время — сложность O(n)) и хотя в некоторых реализациях размер кешируется в дескрипторе списка (или в первом элементе), не стоит на это полагаться.
Если бы я мог, я бы один элемент списка разместил на северном полюсе, а другой где-нибудь в окресностях Бетельгейзе
Применение
Список бы подошел для (внимание!) списка бездомных котят, отсортированных по возрасту (по возрастанию). Нам как-раз нужно часто добавлять и удалять элементы из списка (вы не подумайте ничего такого — котят забирают), да и чаще понадобятся первые элементы списка — я бы взял себе маленького пушистого котенка, а не 8-ми-летнего манула.
Ладно. Списки это вроде простая структура. Что есть еще?
3 Множество (Set)
Это Сет
Похожее понятие есть в математике, а точнее в теории множеств. Множество отличается и от вектора и от списка, хотя их реализация может быть похожа.
Множество — неупорядоченный набор элементов, без повторов. Ух. И все? Ни тебе произвольного доступа, ничего! Зачем такое нужно?
Как мы знаем в векторе можно быстро получить элемент по индексу, в списке можно быстро добавить или удалить элемент, а что с множеством?
В множестве можно быстро проверить, есть какой-либо элемент внутри, или его нет. Скажем если бы я хотел узнать, находится ли конкретная кошка в моем списке любимых, то и для списка и для вектора мне пришлось бы перебрать (в худжем случае) все элементы!
Реализация
В множестве, т.к. оно неупорядочено можно сортировать элементы при добавлении и в случае чего устроить бинарный поиск. Хм. Вот ведь парадокс, коллекция неупорядоченная, а внутри все будет по-порядку. Тут важно понять, что если вы добавите новый элемент в множество, не факт, что он пойдет в конец.
На самом деле, работая с множеством вообще нельзя полагаться на какой-либо порядок элементов, он может быть любым — именно поэтому множество и неупорядоченная коллекция.
Стоит отметить, что множество может быть реализовано множеством различных способов, например можно использовать хеширование, для еще более быстрого поиска элементов, поэтому подробно реализацию я рассматривать не буду. Скажу лишь, что можно схитрить и использовать наши знания по спискам.
Вообще есть еще упорядоченные множества, множества с повторами (мультимножество), и вероятно должно быть упорядоченное мультимножество.
Теория множеств дается проще, если брать множество котят
Применение
Множество идеально подойдет для списка любимых котят, потому что их множество. Ха! Шучу.
Но оно действительно подойдет, потому-что такую коллекцию не нужно сортировать (упорядоченность не важна) и мы легко сможем проверить, находится ли какой-нибудь конкретный кот в этом множестве (скажем у меня 100 котят и любимых я кормлю креветками).
Ну ладно. Множества тоже хороши, но неужели есть что-то еще?
4 Словарь (Associative Array, Map, Dictionary)
Признайтесь, это лучше, чем просто словарь
Словарь (он же ассоциативный массив) — это тот-же вектор, но с небольшими отличиями. В качестве индекса (который в словаре будет называться ключ) могут выступать не только числа, но и любые другие типы данных (даже другие коллекции!). Также допустимы пропуски, если мы все-таки будем использовать в качестве ключа целое число, например у нас может быть элемент связанный с ключем 5, но при этом отсутствовать элемент связанный с ключем 4.
Что все это значит на практике? Всего-лишь, то, что в квадратных скобках для ображения к элементу по “индексу” мы можем указывать произвольный тип, например allMyCats[“Murka”].
Реализация
Невооруженным видно, что можно просто завести массив (или список) пар (Ключ, Значение) и добавить специальную функцию, которая будет пробегать по этому списку и возвращать определенное значение по связанному с ним ключу.
Мы также не можем сказать какая пара первая, какая последняя и что раньше “Murka” или “Borka”, поэтому словарь считается неупорядоченной структурой.
Опять-же с каждым ключем может быть связано лишь одно значение, поэтому для приведенного примера с именами кошек словарь в чистом виде подходит слабо.
Реализация, как и в случае со множеством, может быть совершенно различной, можно упорядочить пары по ключу и использовать для получения элемента бинарный поиск (в таком случае элементы должны быть упорядочеваемыми). Опять-же можно реализовать словарь с помощью хеширования ключа, что довольно часто используется со строками.
Применение
Самый правдоподобный и грамотный способ — использовать словарь вместе со списком, где ключем словаря будет строка — имя кошки, а значением — список кошек с таким именем. Это позволит быстро найти всех кошек по имени Мурка и выбрать из них ту, которая в данный момент нужна.
Примерно так выглядит в памяти std::map >
И у меня для вас новость — типы коллекций закончились. Ну все. Вообще больше нет. Совсем.
5 Стек (Stack)
Еще один кот и будет Stack Overflow
Ха! Я вас обманул (всмысле пошутил)! Есть еще пара структур данных, которые представляют коллекции.
Итак стек — коллекция с необычным доступом, точнее с необычными правилами относительно того, как могут быть добавлены и удалены элементы.
Все просто — добавляемый элемент, называемый “последним”, первый выбывает из из стека.
Стек очень нужен и полезен в программировании. Например с помощью стека осуществляется вложенный вызов процедур — в стек сохраняются адрес возврата и аргументы вызванной функции.
Реализация
В высокоуровневой реализации ничего особенно интересного нет — указатель на список и элементы добавляются в начало этого списка, и удаляются с него-же.
В низкоуровневой реализации (точнее то, как он реализован в современных архитектурах) есть интересные моменты.
Стек там является небольшим зарезервированным участком памяти и совместно с ним хранится два указателя — на начало стека (где лежит первый доавленный элемент) и конец стека — где лежит последний добавленный.
Если в стек поместить слишком много данных программа завершится со всем знакомой ошибкой — Stack Overflow, это значит, что указатель на конец стека превысил верхний допустимый предел.
Также может случиться обратная ситуация (Stack Underflow), если попытаться забрать из стека больше чем в нем есть, но в высокоуровневых языках она не встречается (понятно почему — нам не дают напрямую работать со стеком).
Если кому интересно как это все работает — изучение ассемблера для какой-нибудь популярной архитектуры, вроде i386, может вам помочь.
Применение
Можно было-бы описать в этом месте стек из бедных котят высотой с гору, но на самом деле в высокоуровневых языках стек редко необходим, часто хватает рекурсии, которая использует стек неявно. Я не стал прикладывать надуманный пример (и не смог придумать нормальный, простите), поэтому переходим к следующему пункту.
Разное
На самом деле есть еще куча коллекций, таких как очередь, двусторонняя очередь (дек), двусвязанный список, кольцевое множество, очереди с приоритетом.
Есть деревья (да их целый лес!) и графы.
Есть вероятностные структуры данных, такие как вероятностное множество и список с пропусками.
Я очень хочу про все это написать, но времени и места на хабре не всегда мало.
Однако есть множество (или вектор) вещей, относящихся к теме, которые я хотел бы упомянуть хоть вскользь, да просит меня любопытный читатель и пойдет читать умную книгу.
Строки
В первую очередь то, как реализованы строки в некоторых языках может показаться странным. Самое простое и эффективное решение это наверное решение C — строка это набор символов, с нулевым символом в конце, что позволяет обходиться без дескриптора.
В C++ std::string уже больше походит на вектор.
Ну а в старом паскале дескриптор (точнее всего-лишь длина) хранится в нулевом элементе массива.
В Haskell String — это список символов ([Char]), из чего вытекает, что получение длины строки имеет сложность O(n). Зато их очень удобно оббегать рекурсивно.
В общем случае, строка — это упорядоченный набор символов и не более. Какой именно тип коллекции будет использован — не важно (ну я бы не советовал использовать множество, ха!).
Очередь (Queue)
Очередь очень похожа на стек и в тоже время является его противоположностью — первым мы получим обратно не тот элемент, что мы добавили последним, а тот, что “стоит в очереди” дольше всех. Очередь очень удобная структура, но несмотря, на то, что принцип ее работы схож со стеком, в эффективной реализации есть небольшое отличие.
Для стека мы могли схитрить и выделить приемлемый по размеру участок памяти, в случае чего его расширяя, потому-что стек то уменьшается, то увеличивается, т.к. элементы и добавляются и удаляются “с одного конца”. Если же мы представим работу очереди, то она будет “ползти в памяти” — начало будет постоянно сдвигаться вверх, поэтому трюк, который применим для стека, будет работать хуже и тут уже намного лучше будет использовать двусвязный список (и не забудьте хранить указатели на первый и последний элементы).
Еще можете попробовать реализвать очередь на двух стеках, но это тоже менее эффективно.
Также есть дек (двусторонняя очередь — deque). В ней можно добавлять элементы как в конец, так и в начало. И забирать их тоже и с конца и с начала.
Заключение
Ух. Я начинаю повторяться
Я совсем не упомянул, про комбинирование различных коллекций, благодаря которым образуются матрицы, таблицы. Также я не затронул деревья, кольцевое множество, почти ничего не написал про очереди, очень мало информации по хешированию (я таки отделался парой слов от этой темы) и другим методам оптимизации.
Однако я думаю статья исполнит свою роль — просто и понятно изложит основы структур данных для читателей разной степени подготовленности. И я буду рад продолжить и осветить множество (или очередь, ха!) других тем в таком-же ключе.
Спасибо тем, кто смог дочитать аж до этих строк (как они это выдержали?).